모듈로

컴퓨팅과 수학에서 모듈로 연산(modulo operation)은 한 숫자를 다른 숫자로 나누었을 때의 나머지 또는 부호가 있는 나머지를 반환한다. 이때 나누는 수를 연산의 모듈러스(modulus)라고 부른다.

두 양수 a와 n이 주어졌을 때, a 모듈로 n(종종 a mod n으로 축약함)은 a를 n으로 나눈 유클리드 나눗셈의 나머지이며, 여기서 a는 피제수, n은 제수이다.

예를 들어, "5 mod 2"의 결과는 1이다. 왜냐하면 5를 2로 나누면 몫이 2이고 나머지가 1이기 때문이다. 반면 "9 mod 3"의 결과는 0인데, 이는 9를 3으로 나누면 몫이 3이고 나머지가 0이기 때문이다.

일반적으로 a와 n 모두 정수일 때 연산이 수행되지만, 오늘날 많은 컴퓨팅 시스템은 다른 유형의 숫자 피연산자도 허용한다. n에 대한 정수 모듈로 연산의 결과 범위는 0부터 n − 1까지이다. a가 정수라고 가정할 때, a mod 1은 항상 0이다.

a 또는 n 중 정확히 하나만 음수일 경우, 기본적인 정의는 적용되지 않으며 프로그래밍 언어마다 이러한 값들을 어떻게 정의하는지가 다르다.

정의의 변형

수학에서 모듈로 연산의 결과는 동치류이며, 해당 류의 모든 원소는 대표원으로 선택될 수 있다. 하지만 보통은 그 류에 속하는 가장 작은 음수가 아닌 정수, 즉 유클리드 나눗셈의 나머지인 최소 양의 나머지(least positive residue)를 대표원으로 사용한다. 그러나 다른 관례도 가능하다. 컴퓨터와 계산기는 숫자를 저장하고 표현하는 다양한 방법을 가지고 있으므로, 모듈로 연산의 정의는 사용하는 프로그래밍 언어나 기반 하드웨어에 따라 달라진다.

거의 모든 컴퓨팅 시스템에서, a를 $n\neq 0$으로 나눈 몫 q와 나머지 r은 다음 조건을 만족한다.

${\begin{aligned}&q\in \mathbb {Z} \\&a=nq+r\quad (n\neq 0)\\&|r|<|n|\end{aligned}}$

(1)

나머지가 0이 아닐 경우 부호의 모호성이 여전히 남는다. 나머지를 음수 또는 양수 중 하나로 선택할 수 있는데, 이 선택이 식 (1)을 만족시키기 위해 사용해야 하는 두 연속된 몫 중 무엇인지를 결정한다. 수론에서는 항상 양의 나머지를 선택하지만, 컴퓨팅에서 프로그래밍 언어들은 언어 자체의 특성과 a 또는 n의 부호에 따라 선택한다. 예를 들어, 표준 파스칼과 ALGOL 68은 제수가 음수일 때도 양의 나머지(또는 0)를 반환하며, C90과 같은 일부 프로그래밍 언어는 n이나 a 중 하나가 음수일 때 그 동작을 구현 정의에 맡긴다(자세한 내용은 § 프로그래밍 언어별 모듈로 연산 아래의 표 참조). 일부 시스템은 a 모듈로 0을 정의하지 않지만, 어떤 시스템은 이를 a로 정의하기도 한다.

• 

      몫 (q)과      나머지 (r). 피제수 (a)에 대한 함수로 표현, 절단 나눗셈(truncated division) 사용

  많은 구현체는 절단 나눗셈을 사용하며, 여기서 몫은 다음과 같이 정의된다. $$q=\operatorname {trunc} \left({\frac {a}{n}}\right)$$ 여기서 $\operatorname {trunc}$는 정수 부분 함수(0 방향으로 반올림)이다. 따라서 식 (1)에 따르면, 나머지는 피제수 a와 같은 부호를 가지며 다음과 같이 2|n| − 1개의 값을 가질 수 있다. $$r=a-n\operatorname {trunc} \left({\frac {a}{n}}\right)$$

• 

  바닥 나눗셈(floored division)을 사용한 몫과 나머지

  도널드 커누스는 바닥 나눗셈을 권장하며, 여기서 몫은 다음과 같이 정의된다. $$q=\left\lfloor {\frac {a}{n}}\right\rfloor$$ 여기서 $\lfloor \,\rfloor$는 바닥 함수(내림)이다. 따라서 식 (1)에 따르면, 나머지는 제수 n과 같은 부호를 가진다. $$r=a-n\left\lfloor {\frac {a}{n}}\right\rfloor$$

• 

  유클리드 나눗셈(Euclidean division)을 사용한 몫과 나머지

  Raymond T. Boute는 유클리드 나눗셈을 권장하며, 여기서 음수가 아닌 나머지 $r\in \{0,1,2...\}$는 다음과 같이 정의된다. $$r:=a-nq\ \mathrm {such\ that} \ {\color {red}{0\leq r}}<|n|.$$ (강조 추가됨.) 이 정의하에서 몫 $q$에 대해 다음과 같이 말할 수 있다. $${\begin{aligned}q&={\frac {a-r}{n}}\in \mathbb {Z} \\&={\text{sgn}}(n)\cdot {\frac {a-r}{|n|}}\\&={\text{sgn}}(n)\cdot \left({\frac {a}{|n|}}-{\frac {r}{|n|}}\right)\\&={\text{sgn}}(n)\cdot \left\lfloor {\frac {a}{\left|n\right|}}\right\rfloor \end{aligned}}$$ 여기서 sgn은 부호함수, $\lfloor \,\rfloor$는 바닥 함수(내림), 그리고 ${\frac {a}{|n|}}\in \mathbb {Q}$, ${\frac {r}{|n|}}\in \mathbb {Q}$는 유리수이다.

  동등하게, 몫 $q\in \mathbb {Z}$를 다음과 같이 정의할 수도 있다. $$q:=\operatorname {sgn}(n)\left\lfloor {\frac {a}{\left|n\right|}}\right\rfloor ={\begin{cases}\left\lfloor {\frac {a}{n}}\right\rfloor &{\text{if }}n>0\\\left\lceil {\frac {a}{n}}\right\rceil &{\text{if }}n<0\\\end{cases}}$$ 여기서 $\lceil \,\rceil$는 천장 함수(올림)이다. 따라서 식 (1)에 따르면, 나머지 $r$은 음수가 아니다. $$r=a-nq=a-|n|\left\lfloor {\frac {a}{\left|n\right|}}\right\rfloor$$

• 

  반올림 나눗셈을 사용한 몫과 나머지

  Common Lisp와 IEEE 754는 반올림 나눗셈을 사용하며, 여기서 몫은 다음과 같이 정의된다. $$q=\operatorname {round} \left({\frac {a}{n}}\right)$$ 여기서 round는 반올림 함수(짝수 쪽으로 반올림)이다. 따라서 식 (1)에 따르면, 나머지는 $-{\frac {n}{2}}$와 ${\frac {n}{2}}$ 사이에 위치하며, 그 부호는 이 경계 내에 들어가기 위해 0의 어느 쪽에 떨어지는지에 따라 결정된다. $$r=a-n\operatorname {round} \left({\frac {a}{n}}\right)$$

• 

  올림 나눗셈을 사용한 몫과 나머지

  Common Lisp는 또한 올림 나눗셈을 사용하며, 여기서 몫은 다음과 같이 정의된다. $$q=\left\lceil {\frac {a}{n}}\right\rceil$$ 여기서 ⌈⌉는 천장 함수(올림)이다. 따라서 식 (1)에 따르면, 나머지는 제수의 반대 부호를 가진다. $$r=a-n\left\lceil {\frac {a}{n}}\right\rceil$$

피제수와 제수가 모두 양수이면 절단, 바닥, 유클리드 정의가 일치한다. 피제수가 양수이고 제수가 음수이면 절단 정의와 유클리드 정의가 일치한다. 피제수가 음수이고 제수가 양수이면 바닥 정의와 유클리드 정의가 일치한다. 피제수와 제수가 모두 음수이면 절단 정의와 바닥 정의가 일치한다.

그러나 절단 나눗셈은 항등식 $({-a})/b={-(a/b)}=a/({-b})$을 만족한다.

표기법

일부 계산기에는 mod() 함수 버튼이 있으며, 많은 프로그래밍 언어도 예를 들어 mod(a, n)과 같이 유사한 함수를 가지고 있다. 일부 언어는 a % n이나 a mod n과 같이 모듈로 또는 나머지 연산자로서 "%", "mod", "Mod"를 사용하는 표현식을 지원하기도 한다.

유사한 함수가 없는 환경에서는 위에 언급된 세 가지 정의 중 하나를 사용할 수 있다.

일반적인 오류

모듈로 연산의 결과가 피제수의 부호를 따르는 경우(절단 정의), 놀라운 실수를 초래할 수 있다.

예를 들어, 정수가 홀수인지 테스트하기 위해 나머지가 2로 나누었을 때 1과 같은지 확인하려는 경우를 생각해보자.

bool is_odd(int n) {
    return n % 2 == 1;
}

하지만 모듈로 결과가 피제수의 부호를 따르는 언어에서는 n(피제수)이 음수이면서 홀수일 때 n mod 2가 -1을 반환하여 함수가 거짓(false)을 반환하므로 이는 잘못된 코드이다.

올바른 대안 중 하나는 나머지가 0이 아님을 테스트하는 것이다(나머지 0은 부호에 상관없이 같기 때문이다).

bool is_odd(int n) {
    return n % 2 != 0;
}

또는 비트 산술을 사용한다.

bool is_odd(int n) {
    return n & 1;
}

성능 문제

모듈로 연산은 매번 나머지를 구하는 나눗셈을 계산하도록 구현될 수 있다. 특수한 경우, 일부 하드웨어에서는 더 빠른 대안이 존재한다. 예를 들어, 2의 거듭제곱의 모듈로는 (x가 양의 정수라고 가정하거나 비절단 정의를 사용하는 경우) 비트 AND 연산으로 표현할 수 있다.

x % 2n == x & (2n - 1)

예:

x % 2 == x & 1

x % 4 == x & 3

x % 8 == x & 7

비트 연산을 모듈로 연산보다 효율적으로 수행하는 기기 및 소프트웨어에서는 이러한 대안적 형식이 더 빠른 계산 결과를 낼 수 있다.

컴파일러 최적화는 expression % constant 형태의 표현식에서 constant가 2의 거듭제곱인 경우 이를 자동으로 expression & (constant-1)로 구현하여, 프로그래머가 성능 저하 없이 더 명확한 코드를 작성할 수 있게 한다. 이 간단한 최적화는 모듈로 연산의 결과가 피제수의 부호를 따르는 언어(C 언어 포함)에서는 (피제수가 부호 없는 정수 유형이 아닌 경우) 불가능하다. 왜냐하면 피제수가 음수이면 모듈로는 음수가 되지만 expression & (constant-1)은 항상 양수이기 때문이다. 이러한 언어의 경우, 비트 OR, NOT, AND 연산을 사용하여 x % 2n == x < 0 ? x | ~(2n - 1) : x & (2n - 1)와 같이 작성해야 한다.

일반적인 상수-모듈로 연산에 대해서도 상수-제수 최적화를 사용하여 나눗셈을 먼저 계산하는 방식의 최적화가 존재한다.

성질 (항등식)

 모듈러 산술 § 성질 문서를 참고하십시오.

일부 모듈로 연산은 다른 수학 연산과 유사하게 인수분해되거나 확장될 수 있다. 이는 디피-헬먼 키 교환과 같은 암호학 증명에서 유용할 수 있다. 곱셈, 나눗셈, 거듭제곱과 관련된 성질은 일반적으로 a와 n이 정수여야 함을 전제로 한다.

• 항등원:
  • (a mod n) mod n = a mod n.
  • 모든 양의 정수 x에 대하여 n^x mod n = 0.
  • p가 b의 약수가 아닌 소수인 경우, 페르마의 소정리에 의해 ab^p−1 mod p = a mod p.
• 역원:
  • [(−a mod n) + (a mod n)] mod n = 0.
  • b⁻¹ mod n은 모듈러 역원을 의미하며, 이는 b와 n이 서로소일 때만 정의된다. 즉, 좌변이 정의될 때 [(b⁻¹ mod n)(b mod n)] mod n = 1.
• 분배법칙:
  • (a + b) mod n = [(a mod n) + (b mod n)] mod n.
  • ab mod n = [(a mod n)(b mod n)] mod n.
• 나눗셈 (정의): 우변이 정의될 때(즉, b와 n이 서로소일 때), ⁠a/b⁠ mod n = [(a mod n)(b⁻¹ mod n)] mod n. 정의되지 않을 때는 부정이다.
• 역곱셈: [(ab mod n)(b⁻¹ mod n)] mod n = a mod n.

프로그래밍 언어별 모듈로 연산

여러 프로그래밍 언어에서의 모듈로 연산자

언어	연산자	정수	부동소수점	정의
ABAP	MOD	예	예	유클리드
액션스크립트	%	예	예	절단
에이다	mod	예	아니요	바닥
	rem	예	아니요	절단
ALGOL 68	÷×, ÷*, %×, %*, mod	예	아니요	유클리드
AMPL	mod	예	아니요	절단
APL	|	예	예	바닥
애플스크립트	mod	예	예	절단
AutoLISP	rem	예	예	절단
AWK	%	예	예	절단 (C의 fmod와 동일)
베이직	Mod	예	아니요	구현체마다 다름
Bc	%	예	예	절단
C C++	%, div	예	아니요	절단
	fmod (C) std::fmod (C++)	아니요	예	절단
	remainder (C) std::remainder (C++)	아니요	예	반올림
C 샤프	%	예	예	절단
	Math.IEEERemainder	아니요	예	반올림
클라이온	%	예	아니요	절단
클린	rem	예	아니요	절단
클로저	mod	예	아니요	바닥
	rem	예	아니요	절단
코볼	FUNCTION MOD	예	아니요	바닥
	FUNCTION REM	예	예	절단
커피스크립트	%	예	아니요	절단 (자바스크립트와 동일)
	%%	예	아니요	바닥
ColdFusion	%, MOD	예	아니요	절단
공통 중간 언어	rem (부호 있는 경우)	예	예	절단
	rem.un (부호 없는 경우)	예	아니요	빈칸
커먼 리스프	mod	예	예	바닥
	rem	예	예	절단
크리스탈	%, modulo	예	예	바닥
	remainder	예	예	절단
CSS	mod()	예	예	바닥
	rem()	예	예	절단
D	%	예	예	절단
다트	%	예	예	유클리드
	remainder()	예	예	절단
Dc	%	예	예	절단
에펠	\\	예	아니요	절단
Elixir	rem/2	예	아니요	절단
	Integer.mod/2	예	아니요	바닥
Elm	modBy	예	아니요	바닥
	remainderBy	예	아니요	절단
얼랭	rem	예	아니요	절단
	math:fmod/2	아니요	예	절단 (C와 동일)
유포리아	remainder	예	예	절단
	mod	예	예	바닥
F 샤프	%	예	예	절단 (C#과 동일)
	Math.IEEERemainder	아니요	예	반올림
팩터	mod	예	예	절단
	rem	예	예	유클리드
파일메이커	Mod	예	아니요	바닥
포스	mod	예	아니요	구현 정의
	fm/mod	예	아니요	바닥
	sm/rem	예	아니요	절단
포트란	mod	예	예	절단
	modulo	예	예	바닥
프링크	%, mod	예	예	바닥
Full BASIC	MOD	예	예	바닥
	REMAINDER	예	예	절단
GLSL	%	예	아니요	정의되지 않음
	mod	아니요	예	바닥
GameMaker Studio (GML)	mod, %	예	아니요	절단
고도 (GDScript)	%	예	아니요	절단
	posmod	예	아니요	유클리드
	fmod	아니요	예	절단
	fposmod	아니요	예	유클리드
Go	%	예	아니요	절단
	math.Mod	아니요	예	절단
	big.Int.Mod	예	아니요	유클리드
	big.Int.Rem	예	아니요	절단
아파치 그루비	%	예	아니요	절단
하스켈	mod	예	아니요	바닥
	rem	예	아니요	절단
	Data.Fixed.mod' (글래스고 하스켈 컴파일러)	아니요	예	바닥
Haxe	%	예	예	절단
HLSL	%	예	예	정의되지 않음
J	|	예	아니요	바닥
자바	%	예	예	절단
	Integer.remainderUnsigned, Long.remainderUnsigned	예	아니요	빈칸
	Math.ceilMod, StrictMath.ceilMod	예	아니요	천장
	Math.floorMod, StrictMath.floorMod	예	아니요	바닥
	Math.IEEEremainder, StrictMath.IEEEremainder	아니요	예	반올림
	a.mod(b) (BigInteger)	예	아니요	유클리드
	a.remainder(b) (BigInteger)	예	아니요	절단
	a.remainder(b), a.remainder(b, mathContext) (BigDecimal)	아니요	예	절단
자바스크립트 타입스크립트	%	예	예	절단
줄리아	mod	예	예	바닥
	%, rem	예	예	절단
코틀린	%, rem	예	예	절단
	mod	예	예	바닥
콘셸	%	예	아니요	절단 (POSIX sh와 동일)
	fmod	아니요	예	절단
LabVIEW	mod	예	예	절단
리브레오피스	MOD	예	예	바닥
로고	MODULO	예	아니요	바닥
	REMAINDER	예	아니요	절단
루아 5	%	예	예	바닥
루아 4	mod(x,y)	예	예	절단
Liberty BASIC	MOD	예	아니요	절단
매스캐드	mod(x,y)	예	아니요	바닥
메이플	e mod m (기본값), modp(e, m)	예	아니요	유클리드
	mods(e, m)	예	아니요	반올림
	frem(e, m)	예	예	반올림
Mathematica	Mod[a, b]	예	예	바닥
매트랩	mod	예	예	바닥
	rem	예	예	절단
맥시마	mod	예	아니요	바닥
	remainder	예	아니요	절단
마야 (MEL)	%	예	아니요	절단
	fmod	아니요	예	절단 (C와 동일)
마이크로소프트 엑셀	MOD	예	예	바닥
미니탭	MOD	예	아니요	바닥
모듈라-2	MOD	예	아니요	바닥
	REM	예	아니요	절단
MUMPS	#	예	아니요	바닥
넷와이드 어셈블러 (NASM, NASMX)	%, div (부호 없는 경우)	예	아니요	빈칸
	%% (부호 있는 경우)	예	아니요	구현 정의
님	mod	예	예	절단
	floorMod	예	예	바닥
오베론	MOD	예	아니요	바닥과 유사
오브젝티브-C	%	예	아니요	절단 (C99와 동일)
오브젝트 파스칼, 델파이	mod	예	아니요	절단
OCaml	mod	예	아니요	절단
	mod_float	아니요	예	절단
Occam	\	예	아니요	절단
파스칼 (ISO-7185 및 -10206)	mod	예	아니요	유클리드와 유사
펄	%	예	아니요	바닥
	POSIX::fmod	아니요	예	절단 (C와 동일)
PHP	%	예	아니요	절단
	fmod	아니요	예	절단
PIC 베이직 Pro	\\	예	아니요	절단
PL/I	mod	예	아니요	바닥 (ANSI PL/I)
파워셸	%	예	아니요	절단
프로그래밍 코드 (PRC (Palm OS))	MATH.OP - 'MOD; (\)'	예	아니요	정의되지 않음
Progress	modulo	예	아니요	절단
프롤로그	mod	예	아니요	바닥
	rem	예	아니요	절단
퓨어베이직	%	예	아니요	절단
	Mod(x,y)	아니요	예	절단
퓨어스크립트	`mod`	예	아니요	유클리드
퓨어 데이터	%	예	아니요	절단 (C와 동일)
	mod	예	아니요	바닥
파이썬	%	예	예	바닥
	math.fmod	아니요	예	절단
	math.remainder	아니요	예	반올림
Q 샤프	%	예	아니요	절단
R	%%	예	예	바닥
래킷	modulo	예	일부	바닥
	remainder	예	일부	절단
라쿠	%	아니요	예	바닥
RealBasic	MOD	예	아니요	절단
Reason	mod	예	아니요	절단
REXX	//	예	예	절단
RPG	%REM	예	아니요	절단
루비	%, modulo()	예	예	바닥
	remainder()	예	예	절단
러스트	%	예	예	절단
	rem_euclid()	예	예	유클리드
SAS 언어	MOD	예	아니요	절단
스칼라	%	예	예	절단
스킴	modulo	예	아니요	바닥
	remainder	예	아니요	절단
스킴 R6RS	mod	예	아니요	유클리드
	mod0	예	아니요	반올림
	flmod	아니요	예	유클리드
	flmod0	아니요	예	반올림
스크래치	mod	예	예	바닥
Seed7	mod	예	예	바닥
	rem	예	예	절단
SenseTalk	modulo	예	아니요	바닥
	rem	예	아니요	절단
sh (POSIX) (배시, mksh 등 포함)	%	예	아니요	절단 (C와 동일)
스몰토크	\\	예	예	바닥
	rem:	예	예	절단
스냅!	mod	예	아니요	바닥
Spin	//	예	아니요	바닥
솔리디티	%	예	아니요	절단
SQL (SQL:1999)	mod(x,y)	예	아니요	절단
SQL (SQL:2011)	%	예	아니요	절단
표준 ML	mod	예	아니요	바닥
	Int.rem	예	아니요	절단
	Real.rem	아니요	예	절단
Stata	mod(x,y)	예	아니요	유클리드
스위프트	%	예	아니요	절단
	remainder(dividingBy:)	아니요	예	반올림
	truncatingRemainder(dividingBy:)	아니요	예	절단
Tcl	expr a % n, ::tcl::mathop::% a n	예	아니요	바닥
	expr fmod(a, n), ::tcl::mathfunc::fmod a n	아니요	예	절단 (C와 동일)
Tcsh	%	예	아니요	절단
토크	%	예	아니요	절단
튜링	mod	예	아니요	바닥
베릴로그 (2001)	%	예	아니요	절단
VHDL	mod	예	아니요	바닥
	rem	예	아니요	절단
VimL	%	예	아니요	절단
비주얼 베이직 닷넷	Mod	예	아니요	절단
웹어셈블리	i32.rem_u, i64.rem_u (부호 없는 경우)	예	아니요	빈칸
	i32.rem_s, i64.rem_s (부호 있는 경우)	예	아니요	절단
x86 어셈블리어	DIV (부호 없는 경우)	예	아니요	빈칸
	IDIV (부호 있는 경우)	예	아니요	절단
	FPREM	아니요	예	절단
	FPREM1	아니요	예	반올림
XBase++	%	예	예	절단
	Mod()	예	예	바닥
Zig	%, @rem	예	예	절단
	@mod	예	예	바닥
Z3 정리 증명기	div, mod	예	아니요	유클리드

또한, 많은 컴퓨터 시스템은 몫과 나머지를 동시에 생성하는 divmod 기능을 제공한다. 예로는 x86 아키텍처의 DIV 및 IDIV 명령어, C 언어의 div() 함수, 파이썬의 divmod() 함수 등이 있다.

일반화

오프셋 모듈로

때때로 a 모듈로 n의 결과를 0과 n − 1 사이가 아닌, 특정 숫자 d와 d + n − 1 사이로 두는 것이 유용할 때가 있다. 이 경우 d를 오프셋이라 하며, 특히 d = 1인 경우가 흔하다.

이 연산에 대한 표준 표기법은 없는 것으로 보이나, 잠정적으로 a mod_d n으로 표기하자. 다음과 같이 정의할 수 있다. x = a mod_d n은 d ≤ x ≤ d + n − 1이고 x mod n = a mod n일 때만 성립한다. 분명히 일반적인 모듈로 연산은 오프셋이 0인 경우에 해당한다: a mod n = a mod₀ n.

오프셋이 있는 모듈로 연산은 바닥 함수와 다음과 같이 관련된다. $$a\operatorname {mod} _{d}n=a-n\left\lfloor {\frac {a-d}{n}}\right\rfloor .$$

이를 확인하기 위해 ${\textstyle x=a-n\left\lfloor {\frac {a-d}{n}}\right\rfloor }$라고 하자. 먼저 x mod n = a mod n임을 보이겠다. 모든 정수 b에 대해 (a + bn) mod n = a mod n이 성립하므로, $b=-\!\left\lfloor {\frac {a-d}{n}}\right\rfloor$인 경우에도 성립한다. 즉, $x{\bmod {n}}=\left(a-n\left\lfloor {\frac {a-d}{n}}\right\rfloor \right)\!{\bmod {n}}=a{\bmod {n}}$이다. 이제 d ≤ x ≤ d + n − 1임을 보이면 된다. a − d = kn + r을 만족하고 0 ≤ r ≤ n − 1인 정수 k와 r을 잡자( 유클리드 나눗셈 참조). 그러면 $\left\lfloor {\frac {a-d}{n}}\right\rfloor =k$이므로, $x=a-n\left\lfloor {\frac {a-d}{n}}\right\rfloor =a-nk=d+r$이다. 0 ≤ r ≤ n − 1에서 양변에 d를 더하면 d ≤ d + r ≤ d + n − 1을 얻는다. x = d + r이므로 증명이 끝났다.

오프셋이 있는 모듈로 a mod_d n은 Mathematica에서 Mod[a, n, d]로 구현되어 있다.

절단을 사용한 다른 모듈로 정의 구현

커누스의 바닥 나눗셈과 유클리드 나눗셈의 수학적 우아함에도 불구하고, 프로그래밍 언어에서는 절단 기반 나눗셈을 사용하는 모듈로를 훨씬 더 흔하게 찾아볼 수 있다. Leijen은 절단 정수 나눗셈이 주어졌을 때 두 가지 나눗셈을 계산하기 위한 다음 알고리즘을 제공한다.

/* C의 ldiv() 스타일을 사용한 유클리드 및 바닥 divmod */
typedef struct {
  /* 이 구조체는 C stdlib.h의 일부이지만 명확성을 위해 여기에 재현함 */
  long int quot;
  long int rem;
} ldiv_t;

/* 유클리드 나눗셈 */
inline ldiv_t ldivE(long numer, long denom) {
  /* C99와 C++11 언어는 이 둘을 모두 절단으로 정의한다. */
  long q = numer / denom;
  long r = numer % denom;
  if (r < 0) {
    if (denom > 0) {
      q = q - 1;
      r = r + denom;
    } else {
      q = q + 1;
      r = r - denom;
    }
  }
  return (ldiv_t){.quot = q, .rem = r};
}

/* 바닥 나눗셈 */
inline ldiv_t ldivF(long numer, long denom) {
  long q = numer / denom;
  long r = numer % denom;
  if ((r > 0 && denom < 0) || (r < 0 && denom > 0)) {
    q = q - 1;
    r = r + denom;
  }
  return (ldiv_t){.quot = q, .rem = r};
}

두 경우 모두 나머지는 몫과 독립적으로 계산될 수 있지만 그 반대는 불가능하다. 논리적 분기 조건이 동일하므로 화면 공간을 절약하기 위해 연산들을 하나로 결합하였다.

같이 보기

• 바퀴 (각도)

각주

내용주

외부 링크

• Different kinds of integer division
• Modulorama, animation of a cyclic representation of multiplication tables (explanation in French)