모듈러 연산
- 나머지를 구하는 연산이다.
- A \mod B = C 라고 적는다.
- 12 \mod 5 = 2
유클리드 호제법
- 두 수의 최대공약수를 쉽게 알아내는 방법이다.
핵심은 다음 한 줄이다.
\gcd(a,\ b) = \gcd(b,\ a \bmod b)
a = qb + r이라 두면 a와 b의 공약수는 r = a - qb도 나누고, 거꾸로 b와 r의 공약수는 a = qb + r도 나눈다. 즉 두 쌍의 공약수 집합이 같으므로 최대공약수도 같다.
나머지는 매번 작아지고 음이 아니므로 언젠가 0이 된다. 그때의 나눈 수가 답이다.
\gcd(a,\ 0) = a
예를 들어 \gcd(1071,\ 462)는
1071 = 2\cdot462 + 147,\quad 462 = 3\cdot147 + 21,\quad 147 = 7\cdot21 + 0
이므로 \gcd = 21이다. 나머지가 적어도 절반씩 줄어들어 시간복잡도는 O(\log \min(a,b))다.
python
def gcd(a, b):
while b:
a, b = b, a % b
return a
최소공배수는 여기서 바로 나온다.
\operatorname{lcm}(a,\ b) = \frac{a \cdot b}{\gcd(a,\ b)}
두 수 a,b \in \mathbb Z이고, r = a \mod b 이라고 한다.
이때, r(0 \leq r \leq b) 이고, a \geq b이다.
합동식
a와 b를 m으로 나눈 나머지가 같을 때 m을 법으로 합동이라 하고 다음처럼 적는다.
a \equiv b \pmod m \iff m \mid (a - b)
나머지가 같다는 말과 차가 m의 배수라는 말이 같다는 것이 출발점이다.
덧셈과 곱셈이 그대로 통한다. a \equiv b, c \equiv d \pmod m이면
a + c \equiv b + d,\qquad a - c \equiv b - d,\qquad ac \equiv bd \pmod m
이다. 그래서 큰 수를 다룰 때 중간중간 나머지를 취해도 결과가 같다 — 이것이 프로그래밍에서 합동식을 쓰는 이유다.
나눗셈은 그대로 통하지 않는다. ac \equiv bc \pmod m이라고 해서 a \equiv b인 것은 아니다. 정확히는
ac \equiv bc \pmod m \implies a \equiv b \!\!\pmod{\frac{m}{\gcd(c,\ m)}}
이고, c와 m이 서로소일 때만 법이 그대로 남아 양변에서 c를 지울 수 있다. 예를 들어 2\cdot3 \equiv 2\cdot0 \pmod 6이지만 3 \not\equiv 0 \pmod 6이다.