정수론 | 선형 합동식, 중국인의 나머지 정리

선형 합동식 (Linear Congruences)

정의: 미지수 $x$에 대하여 $ax\equiv b \pmod{m}$으로 표현되는 식

정리: 선형 합동식이 해를 갖기 위한 필요충분조건

$a\not\equiv 0 \pmod{m}$이고 $d=\gcd(a,m)$이라 하자. 선형 합동식 $ax\equiv b \pmod{m}$이 해를 갖기 위한 필요충분조건은 $d|b$이다. 만약 $d|b$를 만족하여 해를 갖게 된 선형 합동식의 특수해가 $x_0$이라면 일반해는 $x\equiv x_0+\cfrac{m}{d}\cdot t \pmod{m}, [t=0,1,\cdots,d-1]$이 성립하여 $m$을 법으로 하는 $d$ 개의 해를 갖는다.

[증명]

$x_0$가 $ax\equiv b\pmod{m}$의 해라고 하면 $ax_0\equiv b\pmod{m}$이다. 그러므로 $ax_0-b=mz$를 만족하는 정수 $z$가 존재한다. 식을 변형하면 $ax_0-mz=b$가 되고 디오판토스 방정식의 형태가 되어 변형된 식이 해를 갖기 위한 필요충분조건은 $d|b$가 된다. 그리고 디오판토스의 일반해 집합 $S$를 $\{x_0+\cfrac{m}{d}\cdot t|t\in Z\}$라 표현할 수 있다. 그리고 임의의 두 정수 $t_1,\ t_2$에 대해 $x_0+\cfrac{m}{d}\cdot t_1\equiv x_0+\cfrac{m}{d}\cdot t_2\pmod{m}$이라 하면 $\cfrac{m}{d}\cdot t_1\equiv\cfrac{m}{d}\cdot t_2\pmod{m}$이 된다. 앞의 계수를 소거하면 $t_1\equiv t_2 \pmod{\cfrac{m}{gcd(\cfrac{m}{d},m)}}$이 되고 분모가 결국 $\cfrac{m}{d}$가 되어 $\cfrac{m}{(\cfrac{m}{d})}=d$임을 알 수 있다. 따라서 $t_1\equiv t_2 \pmod{d}$가 되어 법 $t$에 대한 기약 잉여계의 원소라고 해도 일반성을 잃지 않는다. 즉, 모든 해는 $d$를 법으로 하는 합동이 아닌 $d$ 개의 원소와 대응된다.

정리: $\gcd(a,m)=1$이면 선형 합동식 $ax\equiv b \pmod{m}$은 유일한 해를 갖는다.

앞의 정리에 따라 $m$을 법으로 한 $gcd(a,m)$ 개의 해를 갖는다고 하였으므로 디오판토스 방정식의 경우와 유사하게 $\gcd(a,m)=1$이면 그 해는 유일하다.

예제: $7x-4y=13$의 양의 정수해를 모두 구하여라.

$7x=4y+13$이므로 $4y\equiv-13\equiv 1 \equiv 8\pmod{7}$이다. $y\equiv 2 \pmod{7}$이므로 임의의 정수 $k$에 대해 $y=7k+2$라고 표현할 수 있다. 대입하여 정리하면 $7x-4(7k+2)=13$은 $7x=28k+21$이고 $x=4k+3$이 된다. 즉, $(x,y)= (4k+3,7k+2)$이다.

중국인의 나머지 정리 (Chinese Remainder Theorem)

중국인의 나머지 정리란

$r$ 개의 양의 정수 $n_1,\cdots,n_r$이 각각 서로소라고 하자. $i\ne j$이면 $\gcd(n_i,n_j)=1$을 만족한다. 그러면 $r$ 개의 연립 선형 합동식 $x\equiv a_1 \pmod{n_1}$, $x\equiv a_2 \pmod{n_2}$ $\cdots$ $x\equiv a_r \pmod{n_r}$은 $n_1n_2\cdots n_r$을 법으로 하는 유일한 해를 갖는다.

[증명]

$n=n_1\cdot n_2\cdots n_r$이라 하자. 그리고 $k=1,2, \cdots , r$에 대하여 $N_k=\cfrac{n}{n_k}=n_1\cdot n_2 \cdots n_{k-1}\cdot n_{k+1}\cdots n_r$이라고 가정하자. $i\ne j$이면 $\gcd(n_i,n_j)=1$이므로 $\gcd(N_k,n_k)=1$이다. 따라서, 선형 합동식의 유일해 조건에 따라 $N_kx\equiv1 \pmod{n_k}$는 유일한 해를 갖는다. 그 해를 $x_k$라 하면 $N_kx_k \equiv 1\pmod{n_k}$가 되고 각 선형 방정식에 대해서 $N_1x_1\equiv 1 \pmod{n_1} \cdots N_rx_r\equiv 1 \pmod{n_r}$은 유일해를 갖는다. 그렇다면 $\bar{x}=a_1N_1x_1+\cdots +a_kN_kx_k+\cdots + a_rN_rx_r\equiv a_kN_kx_k \pmod{n_k}$가 되어 $r$개의 연립 선형 합동식의 해가 된다. ($\because n_1\cdots n_{k-1},n_{k+1},\cdots n_r$에 대한 선형 합동식이 모두 0이 되어 소거되므로)

앞서 구한 연립 선형 합동식의 해가 유일해임을 증명하기 위해 $\bar{x}'$이 또 다른 해라고 가정하자. 그러면 $\bar{x}\equiv a_k \equiv \bar{x}'\pmod{n_k},\ k=1,2,3\cdots, r$이다. 즉, $n_k|\bar{x}-\bar{x}'$으로 달리 표현할 수 있다. $k$의 가지수는 $1,2,3\cdots, r$이고 $\gcd(n_i,n_k)=1$이므로 $n_1\cdot n_2\cdots n_r|\bar{x}-\bar{x}'$이다. 따라서, $\bar{x}\equiv \bar{x}' \pmod{n}$이 되어 서로 합동임을 확인할 수 있다.

예제: 선형 합동식 $17x\equiv 9 \pmod{276}$의 해를 구하여라.

$276=3\cdot4\cdot23$으로 $17x\equiv9\pmod{3}$, $17x\equiv9 \pmod{4}$, $17x\equiv 9 \pmod{23}$의 세 연립 선형 합동식의 해를 구하면 된다. 맞게 소거를 하면 $x\equiv 0 \pmod{3}$, $x\equiv 1 \pmod{4}$, $17x\equiv 9 \pmod{23}$이다. $x=3k$라 가정하고 두 번째 식에 대입하면 $3k\equiv 1 \pmod{4}$이다. 앞의 계수를 소거하기 위해 식을 변형하면 $k\equiv 3 \pmod{4}$이다. $k=4s+3,\ x=12s+9$으로 가정하여 세 번쨰 식에 대입을 하면 $17(12s+9)\equiv 9 \pmod{23}$이 된다. 좌변을 정리하면 $204s\equiv -144 \pmod{23}$이고 소거하면 $20s\equiv -6 \pmod{23}$인데 좌변에 $23s$를 빼고 정리하면 $3s\equiv 6 \pmod{23}$이 된다. 즉, $s=23t+2$로 치환할 수 있다. 따라서 $x=12(23t+2)+9$가 되어 $276t+33$이다. 따라서 $x\equiv 33 \pmod{276}$이 문제의 답이 된다.

중국인의 나머지 정리 사용법

• $667^{937} \pmod{2537}$

위 문제의 값을 구한다고 하자. $2537$은 두 소수 $43, 59$의 곱이다. $667^{937}$을 각각으로 나눈 나머지는 $r_1, r_2$라 하면 구하고자 하는 값은 연립합동식 $667^{937}\equiv r_1 \pmod{43}$, $667^937\equiv r_2 \pmod{59}$의 $43\cdot 59$를 법으로 하는 유일해이다.

먼저 $r_1$을 구하자. 오일러의 정리에 따라 $667^{42}\equiv 1 \pmod{43}$이므로 $667^{937} \equiv 667^{13} \pmod{43}$이다. $667\equiv 22 \pmod{43}$이므로 $667^{13}\equiv 2^{13} \cdot 11^{13} \equiv 2\cdot 11^7 \pmod{43}$이다. ($\because 2^2\cdot 11 \equiv 1 \pmod{43}$) 따라서, $r_1$은 2이다.

마찬가지로 오일러의 정리에 의해 $667^{58} \equiv 1 \pmod{59}$이므로 $667^{937}\equiv 667^9 \pmod{59}$이고 $667\equiv 18 \pmod{59}$에 따라 $r_2 = 667^{937}\equiv 18^9\equiv 38 \pmod{59}$이다.

연립합동식을 만족하기 위해 $667^{937}\equiv 59a_1+43a_2 \pmod{43\cdot59}$로 표현할 수 있다. $59a_1+43a_2\equiv 59a_1+0 \pmod{43}$이고 $59a_1+43a_2\equiv 0+43a_2\pmod{59}$를 확인할 수 있으므로 $59a_1\equiv 2 \pmod{43}$, $43a_2 \equiv 38 \pmod{59}$를 만족시키는 $a_1$, $a_2$를 구하면 된다. 식을 달리 표현하면 $59(59^{-1}\cdot2)\equiv 2 \pmod{43}$, $43(43^{-1}\cdot38)\equiv 38 \pmod{59}$로 볼 수 있다.

합동식 곱셈의 역원 구하기

$\gcd(p,q)=1$일 때, $p^{-1} \pmod{q}$의 값은 디오판토스 방정식 $px+qy=1$이 있을 때 $x$의 값이다. 즉, $px\equiv 1 \pmod{q} (\because qy\equiv 0 \pmod{q})$

$\gcd(59,43)=1$이므로 $59x+43y=1$의 특수해를 구하면 된다. 특수해를 구하는 방법은 확장 유클리드 알고리즘을 사용하여 역으로 추적하면 된다. 구해보면 $1=11-2\cdot5=3\cdot11-2\cdot16=3\cdot43-8\cdot16=11\cdot43-8\cdot59$이므로 $x=-8\equiv 35$, $y=11$이다. 구하고자 하는 값은 $59(59^{-1}\cdot2)+43(43^{-1}\cdot38)$이므로 $59\cdot35\cdot2+43\cdot11\cdot38=4130+17974\pmod{2537}$이 되어 $1808$이다.

작성에 도움이 된 자료

• KMO 수학경시 정수론, 장환수학, 임장환 저