10주차 2차시

Complete Residue System $Z_{6}=\{0,1,2,3,4,5\}$에서, $5 \times 5=1 \mod 6$이므로 $5$의 역원은 $5$이다. 그런데 $2$와 곱해서 $1$이 되는 수, 즉 $2$의 역원은 존재하지 않는다. 따라서 Complete Residue System에서는 곱셈이 잘 정의되지 않는다. 곱셈이 잘 정의되지 않는다는 말은 역원 또는 항등원이 존재하지 않는다는 말과 같다.

 

우리는 곱셈과 나눗셈이 잘 정의되는 Residue System을 원한다.

Reduced Residue System $Z_{m}^{*}=\{a|\gcd(a,m)=1,~0 \le a < m\}$

$Z_{m}^{*}$에서 곱셈이 잘 정의된다는 것을 증명한다.

$\forall a \in Z_{m}^{*},~\exists ~x ~~ax=1 \mod m$

$\gcd(a,m)=1$이므로 유클리드 알고리즘으로부터 $ax+my=1$을 만족하는 정수 $x,~y$가 존재한다. 이항하면 $ax=-ym+1$이므로 $ax$를 $m$으로 나눈 나머지가 $1$이다. 즉 $ax=1 \mod m$이다. $x$의 값을 정확히 알 수는 없지만 어쨌든 곱셈의 역원이 존재한다.

$(ab)c=a(bc) \mod m$ (곱셈의 결합법칙) 증명

$a=q_{1}m+a_{1},~b=q_{2}m+b_{1},~c=q_{3}m+c_{1}$이라 하면 $(ab)c=((q_{1}m+a_{1})(q_{2}m+b_{1}))(q_{3}m+c_{1})=(q_{1}q_{2}m^{2}+aq_{2}m+bq_{1}m+a_{1}b_{1})(q_{3}m+c_{1})$이고, $a(bc)=(q_{1}m+a_{1})((q_{2}m+b_{1})(q_{3}m+c_{1}))=(q_{1}m+a_{1})(q_{2}q_{3}m^{2}+bq_{3}+cq_{2}m+bc)$이다. 두 식을 전개해서 정리하면 양변이 같음을 알 수 있다. 양변이 같으므로 양변을 $m$으로 나눈 나머지도 같다. 따라서 $(ab)c=a(bc) \mod m$이다.

 

사실 $Z_{m}^{*}$에서는 덧셈과 뺄셈이 잘 정의되지 않는다.

Real Number System

Residue System이 어색할 수도 있으므로, 실수 집합에서 이야기해 보자.

 

실수란 무엇인가? 사실 실수라는 말 자체가 정의된 것은 아니다. 대신 실수 집합에서 성립하는 성질을 ``Axiom``, 즉 공리라고 하여 공리가 성립할 때 실수 집합에서 어떤 일이 일어나는지 관찰한다. 

 

예를 들어 $a,b \in R \rightarrow a+b \in R$은 공리이다. $a \in R \rightarrow -a \in R$도 공리이다. 이런 공리가 모두 성립한다고 생각하다 보면 더 복잡한 성질을 이끌어낼 수 있다. 

 

물론 아무거나 다 공리로 놓을 수는 없다. 예를 들어 서로 다른 역원이 2개 존재하는 System은 생각할 수 없다. 역원이 존재한다면 반드시 하나만 존재한다는 사실을 증명할 수 있기 때문이다. "내 시스템에서는 역원이 2개 존재해!"라고 우길 수는 있어도, 그 시스템에서 의미있는 사실을 이끌어낼 수는 없을 것이다.

다시 돌아와서

$m$이 소수일 때 $Z_{m}^{*}$는 어떻게 될까? $1 \le i < m$인 모든 $i$에 대해 $\gcd(i,m)=1$이므로 $Z_{m}^{*}=\{1,2,3,\cdots,m-1\}$이다. 즉 $Z_{m}=Z_{m}^{*} \cup \{0\}$이므로 $Z_{m}$에서 모든 사칙연산이 잘 정의된다. $0$의 곱셈의 역원은 실수 집합에서도 존재하지 않으므로 생각할 필요가 없다.

 

소수 $m$의 Residue System은 사칙연산이 잘 정의되므로 매우 유용하다. 조금만 더 공부하면 $Z_{m}$을 가지고 실제로 암호를 만들 수 있다.

오일러의 정리

$a \in Z_{m}^{*}$에 대해 $a^{1}, a^{2}, a^{3}, \cdots~ \mod m$는 모두 $Z_{m}^{*}$의 원소이다. $Z_{m}^{*}$는 유한하므로 $a$의 제곱을 계속 계산하다 보면 비둘기집의 원리에 의해 언젠가는 $a^{i}=a^{j} \mod m$를 만족한다. $i<j$라 놓으면 $a^{i}=a^{i} \times a^{j-i} \mod m$이므로 $1=a^{j-i} \mod m$이다. $Z_{m}^{*}$이 나눗셈에 대해 닫혀있기 때문에 양변을 $a^{i}$로 나눠도 등식이 성립한다.

 

그러면 등식이 성립하도록 하는 $i,~j$를 구할 수 있을까? 오일러의 정리에서 그 답을 찾을 수 있다.

 

• $a \in Z_{m}^{*} \rightarrow a^{\varphi(m)}=1 \mod m~(\varphi(m)=|Z_{m}^{*}|)$

예를 들어 $Z_{15}^{*}=\{1,2,4,7,8,11,13,14\}$의 각 원소를 $|Z_{15}^{*}|=8$제곱하면 모두 1이 나온다. 물론 $4$제곱만 해도 1이 나오지만, 적어도 $|Z_{m}^{*}|$제곱하면 무조건 1이 나온다는 사실은 분명하다.

증명

$Z_{m}^{*}=\{a_{1},a_{2}, \cdots, a_{k}\}$라 하면 $\varphi(m)=k$이다. $a=a_{i}~(1 \le i \le k)$라 하면 $aZ_{m}^{*}=\{aa_{1},aa_{2},\cdots,aa_{k}\} \subset Z_{m}^{*}$이다. $Z_{m}^{*}$이 곱셈에 대해 닫혀있으므로 $aa_{j} \in Z_{m}^{*}$이다. 그런데 $i \ne j$이면 $aa{i} \ne aa_{j} \mod m$이므로 $aZ_{m}^{*}$의 모든 원소는 서로 다르고, 따라서 $aZ_{m}^{*}=Z_{m}^{*}$이다.

 

따라서 $aa_{1} \times aa_{2} \times \cdots aa_{k}=a_{1} \times a_{2} \times \cdots \times a_{k} \mod m$이다. 좌변은 $aZ_{m}^{*}$의 원소를 모두 곱한 것이고, 우변은 $Z_{m}^{*}$의 원소를 모두 곱한 것이다. 두 집합이 같으므로 두 집합의 모든 원소를 곱해도 같다.

 

좌변을 정리하면 $a^{k} \times a_{1} \times a_{2} \times \cdots \times a_{k}=a_{1} \times a_{2} \times \cdots a_{k} \mod m$이고, 따라서 $a^{k}=1 \mod m$이다.

페르마의 정리

페르마의 정리는 오일러의 정리의 특수한 경우이다.

 

• $p$가 소수이고 $a \in Z_{p}^{*}$일 때 $a^{p-1}=1 \mod p$이다.

특수한 경우이므로 증명은 더 쉽다. 여기서는 생략.

중국인의 나머지 정리

중국인이는 말이 붙은 이유는 이 정리가 실제로 중국의 수학책에 쓰여 있었기 때문이다.

 

$m_{1},m_{2},\cdots,m_{r}$이 모두 서로소라고 하자. 이때 $m=m_{1}m_{2}\cdots m_{k}$로 정의한다.

이때 임의의 $c_{i} \in Z_{m_{i}}~(0 \le c_{i} < m_{i})$에 대해 $x=c_{i} \mod m_{i}$를 만족하는 $x$가 존재한다. 또한 그러한 $x$를 계산할 수 있다.

증명

$M_{i}=\frac{m}{m_{i}},~N_{i}=(M_{i})^{-1} \mod m$(곱셈의 역원)이라 하면 $x=\sum_{i=1}^{r}c_{i}M_{i}N_{i} \mod m$이다. 즉 $x=c_{1}M_{1}N_{1}+c_{2}M_{2}N_{2}+\cdots+c_{r}M_{r}N_{r}$이다.

 

정말로 그러한가? $x \mod m_{i}$를 계산해 보자. $M_{j}~(j \ne i)$에는 모두 $m_{i}$가 곱해져 있다. 따라서 $x \mod m_{i}=c_{i}M_{i}N_{i} \mod m$인데 $M_{i}N_{i}=1 \mod m$이므로 $x \mod m_{i}=c_{i} \mod m$이다. 이 식으로부터 $x = c_{i} \mod m$을 얻을 수 있다.

응용

$x=c_{i} \mod m_{i},~y=d_{i} \mod m_{i}~(i=1,2,\cdots,r)$이라 하면 $x+y=c_{i}+d_{i} \mod m_{i}$이고, $x \times y=c_{i} \times d_{i} \mod m$이다.

 

중국인의 나머지 정리를 이용하여 큰 수의 곱셈을 빠르게 계산할 수 있다. 곱하고자 하는 $x$와 $y$를 각각 $c_{i}$와 $d_{i}$로 쪼갠 다음 $c_{i} \times d_{i} \mod m_{i}$를 구하고, 이것을 이용하여 역으로 $x \times y$를 계산할 수 있다.

 

정수론을 마무리한다. 다음 시간에는 실제로 사용되는 암호에 대해 알아보자.