2. 최대공약수, 유클리드 알고리즘, 최소공배수, 디오판토스 방정식

2. 최대공약수, 유클리드알고리즘, 최소공배수, 디오판토스 방정식

$a,\,b\in\mathbb{Z}$에 대하여 $b$가 $a$의 배수($a$가 $b$의 약수)라는 것은 적당한 $c\in\mathbb{Z}$가 존재하여 $b=ca$가 성립하는 것이다. 이것을 기호로 $a|b$로 나타낸다.

$a,\,b,\,c\in\mathbb{Z}$에 대하여 다음 성질들이 성립한다.

(a) $a|0,\,1|a,\,a|a$

(b) $a|1$일 필요충분조건은 $a=\pm1$

(c) $a|b$이고 $c|d$이면, $ac|bd$

(d) $a|b$이고 $b|c$이면, $a|c$

(e) $a|b$이고 $b|a$이면, $a=\pm b$

(f) $a|b$이고 $b\neq0$이면, $|a|\leq|b|$

(g) $a|b$이고 $a|c$이면, 임의의 $x,\,y\in\mathbb{Z}$에 대하여 $a|(bx+cy)$

(g)의 증명: $a|b$, $a|c$이므로 적당한 $r,\,s\in\mathbb{Z}$가 존재해서 $b=ar$, $c=as$이고, $bx+cy=arx+cas=a(rx+cs)$이므로 $a|(bx+cy)$이다.

$a,\,b,\,d\in\mathbb{Z}$에 대하여 $d|a$이고 $d|b$이면, $d$를 $a$와 $b$의 공약수(common divisor)라 하고, $a^{2}+b^{2}\neq0$($a,\,b$중 적어도 하나는 $0$이 아님)일 때, $a$와 $b$의 최대공약수를 $\text{gcd}(a,\,b)=d$로 나타내는데 이때 다음의 두 성질들이 성립한다.

(a) $d|a$이고 $d|b$

(b) $c|a$이고 $c|b$이면, $d\leq c$

예를들어 $30$과 $-12$의 최대공약수는 $6$이므로 $\text{gcd}(30,\,-12)=6$이고, $\text{gcd}(0,\,0)$은 정의되지 않는다. 한편 $\text{gcd}(a,\,0)=|a|$로 정의한다.

$a,\,b\in\mathbb{Z}\,(a^{2}+b^{2}\neq0)$이면, 적당한 $x,\,y\in\mathbb{Z}$에 대하여 $\text{gcd}(a,\,b)=ax+by$이다.

증명: $$S=\{au+bv\,|\,au+bv\geq0,\,u,\,v\in\mathbb{Z}\}$$ 라 하자. $u=a(\neq0),\,v=0$이라 하면, $au+bv=a^{2}>0$이므로 $S\neq\phi$이고, 정수의 정렬성으로부터 $S$의 최소원소 $d$가 존재하고 $d\in S$이므로, $u,\,v\in\mathbb{Z}$가 존재해서 $d=au+bv$이다. $d=\text{gcd}(a,\,b)$가 성립함을 보이자.

$d|a$, $d|b$이므로, 나눗셈 알고리즘으로부터 $q,\,r\in\mathbb{Z}\,(0\leq r<d)$가 존재해서 $a=qd+r$이다. 여기서 $r=0$임을 보이자. $r>0$이라 하면 $$r=a-dq=a-(au+bv)q=(1-uq)a+(-vq)b\in S$$ 가 되는데 이는 $d$가 $S$의 최소원소라는 사실에 모순이므로 $r=0$이어야 한다.

$c|a$, $c|b$라 하자. $d=au+bv$이므로 $c|d$이고 따라서 $|c|\leq|d|=d$이다. 따라서 $d=\text{gcd}(a,\,b)$이다.

이 정리로부터 다음의 결과를 얻는다: $a,\,b\in\mathbb{Z}\,(a^{2}+b^{2}=0)$이면, $T=\{ax+by\,|\,x,\,y\in\mathbb{Z}\}$는 $d=\text{gcd}(a,\,b)$의 배수들의 집합이다.

증명: $d|ax+by$이므로, $ax+by$는 $d$의 배수이고 $T\subset\{cd|\,c\in\mathbb{Z}\}$이다. $d=ax_{0}+by_{0}$일 때 $nd=a(nx_{0})+b(ny_{0})$이므로 $\{cd\,|\,c\in\mathbb{Z}\subset T\}$이다. 그러므로 $T=\{cd\,|\,c\in\mathbb{Z}\}$이다.     

정수 $a,\,b\in\mathbb{Z}\,(a^{2}+b^{2}\neq0)$에 대하여 $\text{gcd}(a,\,b)=1$이면, $a,\,b$를 서로소(relatively prime)라고 한다.

$a,\,b\in\mathbb{Z}\,(a^{2}+b^{2}\neq0)$에 대하여 $x,\,y\in\mathbb{Z}$가 존재해서 $ax+by=1$일 필요충분조건은 $a,\,b$가 서로소인 것이다.

증명:

$(\Leftarrow)$: 서로소의 정의로부터 자명하다.

$(\Rightarrow)$: $ax+by=1$이고 $d=\text{gcd}(a,\,b)$이면, $d|1$이고 따라서 $d=1$이다.

$\text{gcd}(a,\,b)=d$이면, $\displaystyle\text{gcd}\left(\frac{a}{d},\,\frac{b}{d}\right)=1$이다.

증명: 적당한 $x,\,y\in\mathbb{Z}$에 대하여 $d=ax+by$이므로 $\displaystyle1=\frac{a}{d}x+\frac{b}{d}y$이고 따라서 $\displaystyle\text{gcd}\left(\frac{a}{d},\,\frac{b}{d}\right)=1$이다.

$a|c$이고 $b|c$, $\text{gcd}(a,\,b)=1$이면, $ab|c$이다.

증명: 적당한 $r,\,s\in\mathbb{Z}$에 대하여 $c=ar$, $c=bs$이고, 적당한 $x,\,y\in\mathbb{Z}$에 대하여 $ax+by=1$이므로 $$c=c\cdot1=c(ax+by)=acx+bcy=absx+bary=ab(sx+ry)$$ 이고 따라서 $ab|c$이다.

유클리드의 보조정리(Euclid's lemma)

$a|bc$이고 $\text{gcd}(a,\,b)=1$이면, $a|c$이다.

증명: 적당한 $r\in\mathbb{Z}$에 대하여 $bc=ar$이고, 적당한 $x,\,y\in\mathbb{Z}$에 대하여 $ax+by=1$이므로 따라서 $$c=c\cdot1=c(ax+by)=acx+bcy=acx+ary=a(cx+ry)$$ 이고 $a|c$이다.

$a,\,b\in\mathbb{Z}\,(a^{2}+b^{2}\neq0)$이라 하자. $d>0$에 대하여 $d=\text{gcd}(a,\,b)$일 필요충분조건은 다음의 두 조건이 성립하는 것이다.

(a) $d|a$이고 $d|b$

(b) $c|a$이고 $c|b$이면, $c|d$

증명: 

$(\Rightarrow)$: $d=\text{gcd}(a,\,b)$라 하면, (a)는 자명하고, 적당한 $x,\,y\in\mathbb{Z}$에 대하여 $d=ax+by$이므로, $c|d$이다.

$(\Leftarrow)$: (a), (b)가 성립한다고 가정하자. $d\neq0$이므로 $c|d$이고 따라서 $|c|\leq d$이다.

보조정리: $a=bq+r$이면, $\text{gcd}(a,\,b)=\text{gcd}(b,\,r)$이다.

증명: $d=\text{gcd}(a,\,b)$라 하면, $d|a$, $d|b$이므로 $d|(a-qb)$이고 $d|r$이므로 $d$는 $b$와 $r$의 공약수이다.

반대로 $c$rk $b$와 $r$의 공약수이면, $c|(qb+r)$이고 $c|a$이므로 $c$는 $a,\,b$의 공약수이고 $c\leq d$이다. 따라서 $d=\text{gcd}(a,\,b)=\text{gcd}(b,\,r)$이다.

유클리드 알고리즘(Euclidean Algorithm)

① $a,\,b\in\mathbb{Z}$라 하자. $\text{gcd}(a,\,b)=\text{gcd}(|a|,\,|b|)$이므로, $a\geq b>0$이라고 할 수 있다. 

② $a=q_{1}b+r_{1}\,(0\leq r_{1}<b)$

③ $r_{1}=0$이면, $b|a$이므로 $\text{gcd}(a,\,b)=b$이고,

    $r_{1}\neq0$이면, $b$를 $r_{1}$으로 나누어 식 $b=q_{2}r_{1}+r_{2}\,(0\leq r_{2}<r_{1})$을 얻는다. 

④ $r_{2}=0$이면, 중지하고, 그렇지 않으면($r_{2}\neq0$), $r_{1}=q_{3}r_{2}+r_{3}\,(0\leq r_{3}<r_{2})$을 얻는다.

이 과정을 반복하여 $r_{i}=0$이 될때까지 시행한다.

유클리드 알고리즘의 과정은 전 단계의 보조정리에 근거해서 진행된다.

유클리드 알고리즘을 이용하여 $\text{gcd}(12378,\,3054)$를 구하자. $$\begin{align*}12378&=4\cdot3054+162\\3054&=18\cdot162+138\\162&=1\cdot138+24\\138&=5\cdot24+18\\24&=1\cdot18+6\\18&=3\cdot6+0\end{align*}$$ 이므로 따라서 $\text{gcd}(12378,\,3054)=6$이다.

앞에서 $d=\text{gcd}(a,\,b)$일 때, 적당한 $x,\,y\in\mathbb{Z}$에 대하여 $d=ax+by$가 성립한다고 증명했다. 유클리드 알고리즘을 이용하여 최대공약수를 구하는 과정을 거꾸로 거슬러가면, $x,\,y$를 구할 수 있다. $\text{gcd}(12378,\,3054)=12378x+3054y$를 만족하는 $x,\,y$를 구하자. $$\begin{align*}6&=24-1\cdot18\\&=24-1(138-524)\\&=6\cdot24-138\\&=6(162-138)-138\\&=6\cdot162-7\cdot138\\&=6\cdot162-7(3054-18\cdot162)\\&=132\cdot162-7\cdot3054\\&=132(12378-4\cdot3054)-7\cdot3054\\&=132\cdot12378-535\cdot3054\\&=132\cdot12378+(-535)3054\end{align*}$$ 이므로 $x=132,\,y=-535$이다.

$\text{gcd}(a,\,b)=d$이고 $k>0$이면, $\text{gcd}(ka,\,kb)=kd$이다.

증명: 유클리드 알고리즘으로부터 $$\begin{align*}a&=q_{1}b+r_{1}\,(0\leq r_{1}<b)\\ b&=q_{2}r_{1}+r_{2}\,(0\leq r_{2}<r_{1})\\ \vdots\\ r_{n-2}&=q_{n}r_{n-1}+r_{n}\,(0\leq r_{n}<r_{n-1})\\ r_{n-1}&=q_{n+1}r_{n}+0\end{align*}\\$$ 이므로 $r_{n}=\text{gcd}(a,\,b)$이고 $$\begin{align*}ka&=q_{1}kb+kr_{1}\,(0\leq kr_{1}<kb)\\kb&=q_{2}kr_{1}+kr_{2}\,(0\leq kr_{2}<kr_{1})\\ \vdots\\kr_{n-2}&=q_{n}kr_{n-1}+kr_{n}\,(0\leq kr_{n}<kr_{n-1})\\kr_{n-1}&=q_{n+1}kr_{n}+0\end{align*}$$ 이므로 따라서 $\text{gcd}(ka,\,kb)=kd$이다.

위 사실로부터 $d=\text{gcd}(a,\,b)$이고 $a=dr$, $b=ds$이면, $\text{gcd}(r,\,s)=1$이 성립한다.

$a,\,b\in\mathbb{Z}\,(a^{2}+b^{2}\neq0)$에 대하여 $a,\,b$의 최소공배수(least common multiple) $m$은 다음의 두 성질들을 만족한다.

(a) $a|m$이고 $b|m$

(b) $a|c$이고 $b|c\,(c>0)$이면, $m\leq c$이다.

$a$와 $b$의 최소공배수를 $m=\text{lcm}(a,\,b)$로 나타낸다.

$a,\,b\in\mathbb{N}$에 대하여 $ab=\text{gcd}(a,\,b)\text{lcm}(a,\,b)$이다.

증명: $d=\text{gcd}(a,\,b)$, 적당한 $r,\,s\in\mathbb{Z}$에 대하여 $a=dr,\,b=ds$라 하자. $\displaystyle m=\frac{ab}{d}$이면, $m=as=rb$이고, $m$은 $a$와 $b$의 공배수이다.

$c>0$, $a|c$, $b|c$라 하자. 적당한 $u,\,v\in\mathbb{Z}$에 대하여 $d=au+bv$이므로 $$\frac{c}{m}=\frac{dc}{ab}=\frac{(au+bv)c}{ab}=\left(\frac{c}{b}\right)u+\left(\frac{c}{a}\right)v\in\mathbb{Z}$$ 이고 따라서 $m|c$이므로 $m\leq c$, 즉 $m=\text{lcm}(a,\,b)$이다.

위의 결과로부터 $a,\,b\in\mathbb{N}$에 대하여 $\text{lcm}(a,\,b)=ab$일 필요충분조건은 $\text{gcd}(a,\,b)=1$임을 알 수 있다.

디오판토스 방정식(The Diophantine equation)

디오판토스는 이집트에서 태어난 그리스 수학자로 그의 묘비에 자신의 생애를 방정식 문제로 기록했다.

신의 축복으로 태어난 그는 인생의 $\displaystyle\frac{1}{6}$을 소년으로 보냈다. 그리고 다시 인생의 $\displaystyle\frac{1}{12}$이 지난 뒤에는 얼굴에 수염이 자라기 시작했다. 다시 $\displaystyle\frac{1}{7}$이 지난 뒤 그는 아름다운 여인을 맞이하여 화촉을 밝혔으며, 결혼한 지 5년만에 귀한 아들을 얻었다. 아! 그러나 그의 가엾은 아들은 아버지의 반 밖에 살지 못했다. 아들을 먼저 보내고 깊은 슬픔에 빠진 그는 그 뒤 4년간 정수론에 몰입하여 스스로를 달래다가 일생을 마쳤다. 이 문구는 디오판토스 묘비에 기록된 것이고 디오판토스의 나이를 $x$라고 하면 다음의 방정식으로부터 $$\frac{1}{6}x+\frac{1}{12}x+\frac{1}{7}x+5+\frac{x}{2}+4=x$$ $x=84$라는 결과를 얻는다. 즉 디오판토스는 84세까지 살았음을 알 수 있다.

다시 본문으로 돌아와서 $ax+by=c$형태의 정수계수 1차방정식을 디오판토스 방정식이라고 한다.

(1) 디오판토스 방정식 $ax+by=c$가 해를 가질 필요충분조건은 $\text{gcd}(a,\,b)|c$이다.

(2) $(x_{0},\,y_{0})$가 디오판토스 방정식 $ax+by=c$의 특수해이면, 일반해는 다음과 같다. $$x=x_{0}+\frac{b}{d}t,\,y=y_{0}-\frac{a}{d}t\,(t\in\mathbb{Z})$$ (1)의 증명: $d=\text{gcd}(a,\,b)=ax+by$형태로 나타낼 수 있으므로 디오판토스 방정식이 해를 가질 필요충분이 $d|c$라는 것은 분명하다.

(2)의 증명: $(x,\,y)$를 또 다른 해라고 하자. 그러면 $ax_{0}+by_{0}=ax+by$이므로 $a(x_{0}-x)=b(y-y_{0})$이고, $a=dr,\,b=ds$, $\text{gcd}(r,\,s)=1$이므로 $r(x_{0}-x)=s(y_{0}-y)$이고 이는 $r|y_{0}-y$이 성립함을 뜻하고 따라서 $y_{0}-y=rt$이다. 그러면 $x-x_{0}=st$이고 따라서 $$\begin{cases}\displaystyle x=x_{0}+\frac{b}{d}t&\\ \displaystyle y=y_{0}-\frac{a}{d}t&\end{cases}$$ 이다.

디오판토스 방정식 $172x+20y=1000$의 해를 구하자. $$\begin{align*}172&=8\cdot20+12\\20&=1\cdot12+8\\12&1\cdot8+4\\8&=4\cdot2+0\end{align*}$$ 이므로 $\text{gcd}(a,\,b)=4$이고, $4|1000$이므로 디오판토스 방정식의 해는 존재한다. $$\begin{align*}4&=12-8\\&=12-(20-12)\\&=2\cdot12-20\\&=2(172-8\cdot20)-20\\&=2\cdot172+(-17)20\end{align*}$$ 이므로 $1000=250\cdot4=500\cdot172+(-4250)20$이고 여기서 특수해가 $x_{0}=500,\,y_{0}=-4250$이라는 것을 알 수 있다. 따라서 일반해는 $$\begin{align*}x&=500+\frac{20}{4}t=500+5t\\y&=-4250-\frac{172}{4}t=-4250-43t\end{align*}$$ 이다.

참고자료:

Elementary Number Theory 7th edition, Burton, McGraw-Hill

정수론 8판, 김응태, 박승안, 경문사