시계에서 13시를 1시라 부르듯이, 나머지만 보고 계산하는 산술을 합동식이라 한다. 가우스가 도입한 이 표기는 정수론의 문제를 간결하게 만들고, 요일 계산, 검사 숫자(바코드, 주민번호), 암호에 쓰인다.
핵심 개념
- $n\mid a-b$이면 $a\equiv b\pmod n$ ($a$와 $b$는 법 $n$에 대해 합동)
- 합동은 덧셈, 뺄셈, 곱셈, 거듭제곱을 보존한다.
- 일차합동식 $ax\equiv b\pmod n$은 $d=\gcd(a,n)$이 $b$를 나눌 때만 해가 있고, 그때 법 $n$에 대해 $d$개의 해가 있다.
핵심 정리
$a\equiv b$, $c\equiv d\pmod n$이면 $a+c\equiv b+d$, $ac\equiv bd$, $a^k\equiv b^k\pmod n$이다. 단, 나눗셈은 조심해야 한다: $ac\equiv bc\pmod n$이고 $\gcd(c,n)=1$일 때만 $a\equiv b$이다.
증명 보기
$a=b+nk$, $c=d+nl$이라 하자.
- $a+c=(b+d)+n(k+l)$이므로 $a+c\equiv b+d$
- $ac=bd+n(bl+dk+nkl)$이므로 $ac\equiv bd$
- 곱셈을 반복하면 $a^k\equiv b^k$
나눗셈: $n\mid(a-b)c$이고 $\gcd(c,n)=1$이면, 유클리드 보조정리를 일반화한 성질(베주 항등식 $cx+ny=1$의 양변에 $a-b$를 곱함)에 의해 $n\mid a-b$이다. $\gcd(c,n)>1$이면 성립하지 않는다: $2\cdot3\equiv2\cdot0\pmod6$이지만 $3\not\equiv0$이다. $\blacksquare$
예제
- $2^{100}$을 $7$로 나눈 나머지: $2^3=8\equiv1$이므로 $2^{100}=(2^3)^{33}\cdot2\equiv2$
- 오늘이 월요일이면 $100$일 뒤는 $100\equiv2\pmod7$이므로 수요일
- $3x\equiv4\pmod7$: $3$의 역원은 $5$ ($15\equiv1$)이므로 $x\equiv20\equiv6$
확인 문제
$4x\equiv6\pmod{10}$을 푸시오.
풀이 보기
$\gcd(4,10)=2$이고 $2\mid6$이므로 해가 $2$개 있다. 양변과 법을 $2$로 나누면 $2x\equiv3\pmod5$이고, $2$의 역원은 $3$이므로 $x\equiv9\equiv4\pmod5$이다. 법 $10$으로는 $x\equiv4$ 또는 $9$이다. (확인: $16\equiv6$, $36\equiv6$)
정리
- 합동은 덧셈·곱셈·거듭제곱을 보존한다.
- 나눗셈은 서로소일 때만, 일반적으로는 역원을 곱한다.
