합동식

시계에서 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$개의 해가 있다.
0부터 11까지 적힌 시계에서 9에서 5칸 가면 2
법 12의 덧셈은 시계 위의 계산이다

핵심 정리

$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$)

정리

  • 합동은 덧셈·곱셈·거듭제곱을 보존한다.
  • 나눗셈은 서로소일 때만, 일반적으로는 역원을 곱한다.
알림: 보호된 콘텐츠입니다.