모듈러 연산 (Modular arithmetic) $a \equiv b \pmod{n}$은 다음과 같은 뜻입니다.
$a + mn = b$를 만족시키는 정수 $m$가 존재하면 $$ a \equiv b \pmod{n} $$ 라 표기한다.프로그래밍에서의 모듈러 연산 (나머지 연산 / 통상적으로 % 연산) 과 정수론에서의 mod 연산 은 거의 비슷하지만 약간은 다릅니다.
101 % 10 == 1 이지만, 수학에서는 $101 \equiv 11 \pmod{10}$로 표기할 수도 있고,
0. 기본 전제 - $a \equiv b \pmod{n}$, $a_{1} \equiv b_{1} \pmod{n}$, $a_{2} \equiv b_{2} \pmod{n}$, $k$는 임의의 모든 정수 , $\phi(n)$은 오일러 토션트 함수
$a \equiv b \pmod{n}$이므로 어떤 정수 $m$이 존재하여 $a + mn = b$이다.
1. $a + k \equiv b + k \pmod{n}$
1번 성질 증명
$a + mn = b$의 양변에 $k$를 더하면 $a + k + mn = b + k$에서 $(a + k) + mn = (b + k)$이므로, $a + k \equiv b + k \pmod{n}$이다.
3. $ka \equiv kb \pmod{kn}$
4. $a_{1} \pm a_{2} \equiv b_{1} \pm b_{2} \pmod{n}$
5. $a_{1} a_{2} \equiv b_{1} b_{2} \pmod{n}$
6. $a^{k} \equiv b^{k} \pmod{n}$ (단, 이때의 $k$는 음이 아닌 모든 정수 $k$)
7. $p(a) \equiv p(b) \pmod{n}$ (단, $p(x)$는 모든 계수가 정수인 다항식)
8. 소수 $p$와 서로소 인 $a$에 대해 $a^{p - 1} \equiv 1 \pmod{p}$ ( 페르마의 소정리 )
9. $n$이 소수일 때만 $(n - 1)! \equiv -1 \pmod{n}$ ( 윌슨의 정리 , $n!$은 팩토리얼 기호)
10. $a^{c} \equiv a^{d} \pmod{n}$ (단, $c \equiv d \pmod{\phi (n)}$, $a$와 $n$은 서로소) ( 오일러의 정리 )
11. $a^{\phi(n)} \equiv a^{2\phi(n)} \pmod{n}$ ($a$와 $n$은 모든 임의의 자연수 / 서로소 조건 없음) (오일러의 정리의 확장)
12. $p$가 $5$ 이상의 소수일 때만 $\binom{2p - 1}{p - 1} \equiv 1 \pmod{p^{3}}$ ( 볼첸홈의 정리 )