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판, 김응태, 박승안, 경문사