10주차 1차시

이번주면 정수론은 끝난다. 다음주에는 지금 배우는 내용을 바로 써먹을 수 있는 암호를 공부한다.

$a|bc,~\gcd(a,~b)=1 \Rightarrow a|c$

$a$가 $bc$를 나눈다. 그런데 $a$와 $b$의 최대공약수가 $1$이라면 $a$는 $b$를 나누지 못한다. 따라서 $a$가 $c$를 나눠야만 한다. 직관적으로는 당연하지만 한번 증명해 보자.

증명

$a|bc$이므로 $bc=ka$를 만족하는 정수 $k$가 존재한다. 또한 $\gcd(a,~b)=1$이므로 $ax+by=1$을 만족하는 정수 $x,~y$가 존재한다. 

 

$ax+by=1$의 양변에 $c$를 곱하면 $acx+bcy=acx+kay=a(cx+ky)=c$이다. $c=k'a$ 꼴로 나타낼 수 있으므로 $a$가 $c$를 나누고, $a|c$이다. 증명 끝!

$\gcd(a,~b)=d \Rightarrow a=a_{0}d,~b=b_{0}d,~\gcd(a_{0},~b_{0})=1$

당연하지 않나? $\gcd(a_{0},~b_{0}) \ne 1$이라면 애초에 $d$가 $a$와 $b$의 최대공약수가 아니었던 거다. 그래도 한번 증명해 보자.

증명

$\gcd(a,~b)=d$이므로 $ax+by=d$를 만족하는 정수 $x,~y$가 존재한다. 또한 $d|a$이고 $d|b$이다.

 

$ax+by=d$에 $a=a_{0}d,~b=b_{0}d$를 대입하면 $a_{0}dx+b_{0}dy=d(a_{0}x+b_{0}y)=d$이다. 양변을 $d$로 나누면 $a_{0}x+b_{0}y=1$이다. 따라서 지난 시간에 증명한 Theorem에 의해 $\gcd(a_{0},~b_{0})=1$이다.

$\gcd(a,b)=1,~gcd(a,c)=1 \rightarrow \gcd(a,bc)=1$

$ax+by=1$을 만족하는 정수 $x,y$가 존재하고, $aw+cz=1$을 만족하는 정수 $w,z$가 존재한다. 두 식을 곱하여 정리하면 $a(axw+cxz+byw)+bc(yz)=1$이다. $as+(bc)t=1$을 만족하는 두 정수 $s=axw+cxz+byw,~t=yz$가 존재하므로 $\gcd(a,bc)=1$이다.

최대공약수의 두 정의는 동치이다.

즉, 다음의 두 정의가 같다.

 

• 직관적인 정의: 약수 중 가장 큰 수
• ``이전의 정의``
  
  • $d|a,~~d|b$
  • 모든 가능한 $c$에 대해 $c|a$이고 $c|b$이면 $c|d$
  • $d \ge 0$

증명

유클리드 알고리즘을 이용하여 $\gcd(a,b)=d$이면 $ax+by=d$임을 만족하는 정수 $x,~y$가 존재함을 보였다. 여기서 구한 $d$는 직관적인 정의로 구한 최대공약수이다. 이제 이 $d$가 ``이전의 정의``를 만족함을 보이자.

 

$\gcd(a,b)=d$이므로 $a=a_{0}d$, $b=b_{0}d$, $\gcd(a_{0},b_{0})=1$을 만족하는 두 정수 $a_{0},~b_{0}$가 존재한다. 어떤 정수 $c$에 대해 $c|a$이고 $c|b$라면, $a=cl$과 $b=ck$를 만족하는 정수 $l,~k$가 존재한다. 이것을 $ax+by=d$에 대입하면 $clx+cky=c(lx+ky)=d$를 얻는다. $ct=d$를 만족하는 정수 $t=lx+ky$가 존재하므로 $c|d$이다. 따라서 모든 가능한 $c$에 대해 $c|a$이고 $c|b$이면 $c|d$가 성립한다. 증명 끝!

 

따라서 $a$와 $b$의 공약수 집합은 $d$의 약수 집합과 같다는 점을 알 수 있다.

확장

3개 이상의 정수에 대해 최대공약수를 생각할 수 있다. ``이전의 정의``와 같은 방법으로 생각하면 된다.

최소공배수 (Least Common Multiple)

두 정수 $a,~b$에 대해 $a$와 $b$의 최소공배수 $l$은 다음과 같이 정의된다.

 

• $a|l,~b|l$
• 모든 가능한 $c$에 대해 $a|c$이고 $b|c$이면 $l|c$
• $l \ge 0$

다음의 명제는 모두 동치이다.

 

• $a$와 $b$는 서로소이다.
• $\gcd(a,~b)=1$
• $lcm(a,~b)=ab$
• 어떤 $x$와 $y$에 대해 $ax+by=1$

최소공배수와 최대공약수의 관계

정수 $a$와 $b$에 대해 $\gcd(a,b)=d$라고 하면 다음이 성립한다.

 

• $a=a_{0}d,~b=b_{0}d$
• $lcm(a,b)=a_{0}b_{0}d$
• $a|t,~b|t,~\gcd(a,b)=d \rightarrow a_{0}b_{0}d|t~~(a=a_{0}d,~b=b_{0}d)$
• $ab=lcm(a,b)\gcd(a,b)$

마지막 식이 성립함을 증명해 보자. 세번째 식에서 $ap=t,~bq=t$를 만족하는 정수 $p$와 $q$가 존재하고,  $a_{0}x+b_{0}y=1$를 만족하는 정수 $x,~y$가 존재한다. 이 등식의 양변에 $t$를 곱하면 $a_{0}xt+b_{0}yt=a_{0}xbq+b_{0}yap=a_{0}xb_{0}dq+b_{0}ya_{0}dp=a_{0}b_{0}d(xq+yp)=t$이므로 $a_{0}b_{0}d|t$가 성립한다.

나머지 연산 (Modular Arithmetic)

흔히 모듈러라고도 불리는 나머지 연산은 나눗셈의 결과에서 나머지만 취하는 연산을 뜻한다. 예를 들어 $8 \mod 6=2$이다. $b= a \mod m$의 정의는 다음과 같다.

 

• $b=a \mod m \Leftrightarrow m|(b-a)$
• 또는 $a$와 $b$를 $m$으로 나눈 나머지가 같다
• 또는 (항상 성립하는 것은 아니지만) $a$를 $b$로 나눈 나머지가 $m$이다

그런데 가끔 $mod $ 연산자가 $8 \mod 6 = 2$과 같이 나머지 그 자체를 의미하기도 한다. 즉 $mod$가 식 왼쪽에 올때와 오른쪽에 올 때의 의미가 다르다.

동등성의 관계 (Equivalence Relation)

다음이 성립한다.

• $a=a \mod m$
• $a=b \mod m$이면 $b=a \mod m$
• $a=b \mod m$이고 $b=c \mod m$이면 $a=c \mod m$

모듈러 보존

• $a=b \mod m$이고 $c=d \mod m$이면 다음이 성립한다.
  • $a+c=b+d \mod m$
  • $a-c=b-d \mod m$
  • $ac=bd \mod m$
• $a=b \mod m$일 때, 상수 $k$에 대해 다음이 성립한다.
  • $a+k=b+k \mod m$: 명제의 역이 성립한다. 아래의 두 명제는 역이 성립하지 않는다.
  • $ak=bk \mod m$
  • $a^{k}=b^{k} \mod m$

완전잉여계 (Complete Residue System)

완전잉여계 $Z_{m}=\{0,1,\cdots,m-1\}$이다. 즉 $m$으로 나눴을 때 나머지로 가능한 수만 생각하자는 것이다. 완전잉여계에서는 덧셈과 뺄셈이 잘 정의된다. 연산의 결과에 항상 $m$으로 나눈 나머지를 취하면 된다.

$ka=kb \mod m$이고 $\gcd(k,m)=1$이면 $a=b \mod m$

매우 중요한 정리이다.

증명

$ka=kb \mod m$이므로 $ka-kb=cm$을 만족하는 정수 $c$가 존재한다. 또 $\gcd(k,m)=1$이므로 $kx+my=1$을 만족하는 정수 $x,~y$가 존재한다.

 

양변에 $x$를 곱하면 $kxa-kxb=cmx=(1-my)a-(1-my)b=a-b-amy+bmy$이다. 식을 정리하면 $a-b=amy-bmy+cmx=m(ay-by+cx)$이므로 $a=b \mod m$이다.

Reduced Residue System

$Z_{m}^{*}=\{a|\gcd(a,m)=1\}$로 정의하면 곱셈이 잘 정의되는 잉여계를 얻을 수 있다. $Z_{m}^{*}$에는 $0$이 포함되지 않는다. 

 

곱셈이 잘 정의되므로 나눗셈도 잘 정의되지 않을까? 그 얘기는 다음 시간에 하도록 하자.