2. 최대공약수, 유클리드알고리즘, 최소공배수, 디오판토스 방정식
a,b∈Z에 대하여 b가 a의 배수(a가 b의 약수)라는 것은 적당한 c∈Z가 존재하여 b=ca가 성립하는 것이다. 이것을 기호로 a|b로 나타낸다.
a,b,c∈Z에 대하여 다음 성질들이 성립한다.
(a) a|0,1|a,a|a
(b) a|1일 필요충분조건은 a=±1
(c) a|b이고 c|d이면, ac|bd
(d) a|b이고 b|c이면, a|c
(e) a|b이고 b|a이면, a=±b
(f) a|b이고 b≠0이면, |a|≤|b|
(g) a|b이고 a|c이면, 임의의 x,y∈Z에 대하여 a|(bx+cy)
(g)의 증명: a|b, a|c이므로 적당한 r,s∈Z가 존재해서 b=ar, c=as이고, bx+cy=arx+cas=a(rx+cs)이므로 a|(bx+cy)이다.
a,b,d∈Z에 대하여 d|a이고 d|b이면, d를 a와 b의 공약수(common divisor)라 하고, a2+b2≠0(a,b중 적어도 하나는 0이 아님)일 때, a와 b의 최대공약수를 gcd(a,b)=d로 나타내는데 이때 다음의 두 성질들이 성립한다.
(a) d|a이고 d|b
(b) c|a이고 c|b이면, d≤c
예를들어 30과 −12의 최대공약수는 6이므로 gcd(30,−12)=6이고, gcd(0,0)은 정의되지 않는다. 한편 gcd(a,0)=|a|로 정의한다.
a,b∈Z(a2+b2≠0)이면, 적당한 x,y∈Z에 대하여 gcd(a,b)=ax+by이다.
증명:S={au+bv|au+bv≥0,u,v∈Z}라 하자. u=a(≠0),v=0이라 하면, au+bv=a2>0이므로 S≠ϕ이고, 정수의 정렬성으로부터 S의 최소원소 d가 존재하고 d∈S이므로, u,v∈Z가 존재해서 d=au+bv이다. d=gcd(a,b)가 성립함을 보이자.
d|a, d|b이므로, 나눗셈 알고리즘으로부터 q,r∈Z(0≤r<d)가 존재해서 a=qd+r이다. 여기서 r=0임을 보이자. r>0이라 하면r=a−dq=a−(au+bv)q=(1−uq)a+(−vq)b∈S가 되는데 이는 d가 S의 최소원소라는 사실에 모순이므로 r=0이어야 한다.
c|a, c|b라 하자. d=au+bv이므로 c|d이고 따라서 |c|≤|d|=d이다. 따라서 d=gcd(a,b)이다.
이 정리로부터 다음의 결과를 얻는다: a,b∈Z(a2+b2=0)이면, T={ax+by|x,y∈Z}는 d=gcd(a,b)의 배수들의 집합이다.
증명: d|ax+by이므로, ax+by는 d의 배수이고 T⊂{cd|c∈Z}이다. d=ax0+by0일 때 nd=a(nx0)+b(ny0)이므로 {cd|c∈Z⊂T}이다. 그러므로 T={cd|c∈Z}이다.
정수 a,b∈Z(a2+b2≠0)에 대하여 gcd(a,b)=1이면, a,b를 서로소(relatively prime)라고 한다.
a,b∈Z(a2+b2≠0)에 대하여 x,y∈Z가 존재해서 ax+by=1일 필요충분조건은 a,b가 서로소인 것이다.
증명:
(⇐): 서로소의 정의로부터 자명하다.
(⇒): ax+by=1이고 d=gcd(a,b)이면, d|1이고 따라서 d=1이다.
gcd(a,b)=d이면, gcd(ad,bd)=1이다.
증명: 적당한 x,y∈Z에 대하여 d=ax+by이므로 1=adx+bdy이고 따라서 gcd(ad,bd)=1이다.
a|c이고 b|c, gcd(a,b)=1이면, ab|c이다.
증명: 적당한 r,s∈Z에 대하여 c=ar, c=bs이고, 적당한 x,y∈Z에 대하여 ax+by=1이므로c=c⋅1=c(ax+by)=acx+bcy=absx+bary=ab(sx+ry)이고 따라서 ab|c이다.
유클리드의 보조정리(Euclid's lemma)
a|bc이고 gcd(a,b)=1이면, a|c이다.
증명: 적당한 r∈Z에 대하여 bc=ar이고, 적당한 x,y∈Z에 대하여 ax+by=1이므로 따라서c=c⋅1=c(ax+by)=acx+bcy=acx+ary=a(cx+ry)이고 a|c이다.
a,b∈Z(a2+b2≠0)이라 하자. d>0에 대하여 d=gcd(a,b)일 필요충분조건은 다음의 두 조건이 성립하는 것이다.
(a) d|a이고 d|b
(b) c|a이고 c|b이면, c|d
증명:
(⇒): d=gcd(a,b)라 하면, (a)는 자명하고, 적당한 x,y∈Z에 대하여 d=ax+by이므로, c|d이다.
(⇐): (a), (b)가 성립한다고 가정하자. d≠0이므로 c|d이고 따라서 |c|≤d이다.
보조정리: a=bq+r이면, gcd(a,b)=gcd(b,r)이다.
증명: d=gcd(a,b)라 하면, d|a, d|b이므로 d|(a−qb)이고 d|r이므로 d는 b와 r의 공약수이다.
반대로 crk b와 r의 공약수이면, c|(qb+r)이고 c|a이므로 c는 a,b의 공약수이고 c≤d이다. 따라서 d=gcd(a,b)=gcd(b,r)이다.
유클리드 알고리즘(Euclidean Algorithm)
① a,b∈Z라 하자. gcd(a,b)=gcd(|a|,|b|)이므로, a≥b>0이라고 할 수 있다.
② a=q1b+r1(0≤r1<b)
③ r1=0이면, b|a이므로 gcd(a,b)=b이고,
r1≠0이면, b를 r1으로 나누어 식 b=q2r1+r2(0≤r2<r1)을 얻는다.
④ r2=0이면, 중지하고, 그렇지 않으면(r2≠0), r1=q3r2+r3(0≤r3<r2)을 얻는다.
이 과정을 반복하여 ri=0이 될때까지 시행한다.
유클리드 알고리즘의 과정은 전 단계의 보조정리에 근거해서 진행된다.
유클리드 알고리즘을 이용하여 gcd(12378,3054)를 구하자.12378=4⋅3054+1623054=18⋅162+138162=1⋅138+24138=5⋅24+1824=1⋅18+618=3⋅6+0이므로 따라서 gcd(12378,3054)=6이다.
앞에서 d=gcd(a,b)일 때, 적당한 x,y∈Z에 대하여 d=ax+by가 성립한다고 증명했다. 유클리드 알고리즘을 이용하여 최대공약수를 구하는 과정을 거꾸로 거슬러가면, x,y를 구할 수 있다. gcd(12378,3054)=12378x+3054y를 만족하는 x,y를 구하자.6=24−1⋅18=24−1(138−524)=6⋅24−138=6(162−138)−138=6⋅162−7⋅138=6⋅162−7(3054−18⋅162)=132⋅162−7⋅3054=132(12378−4⋅3054)−7⋅3054=132⋅12378−535⋅3054=132⋅12378+(−535)3054이므로 x=132,y=−535이다.
gcd(a,b)=d이고 k>0이면, gcd(ka,kb)=kd이다.
증명: 유클리드 알고리즘으로부터a=q1b+r1(0≤r1<b)b=q2r1+r2(0≤r2<r1)⋮rn−2=qnrn−1+rn(0≤rn<rn−1)rn−1=qn+1rn+0이므로 rn=gcd(a,b)이고ka=q1kb+kr1(0≤kr1<kb)kb=q2kr1+kr2(0≤kr2<kr1)⋮krn−2=qnkrn−1+krn(0≤krn<krn−1)krn−1=qn+1krn+0이므로 따라서 gcd(ka,kb)=kd이다.
위 사실로부터 d=gcd(a,b)이고 a=dr, b=ds이면, gcd(r,s)=1이 성립한다.
a,b∈Z(a2+b2≠0)에 대하여 a,b의 최소공배수(least common multiple) m은 다음의 두 성질들을 만족한다.
(a) a|m이고 b|m
(b) a|c이고 b|c(c>0)이면, m≤c이다.
a와 b의 최소공배수를 m=lcm(a,b)로 나타낸다.
a,b∈N에 대하여 ab=gcd(a,b)lcm(a,b)이다.
증명: d=gcd(a,b), 적당한 r,s∈Z에 대하여 a=dr,b=ds라 하자. m=abd이면, m=as=rb이고, m은 a와 b의 공배수이다.
c>0, a|c, b|c라 하자. 적당한 u,v∈Z에 대하여 d=au+bv이므로cm=dcab=(au+bv)cab=(cb)u+(ca)v∈Z이고 따라서 m|c이므로 m≤c, 즉 m=lcm(a,b)이다.
위의 결과로부터 a,b∈N에 대하여 lcm(a,b)=ab일 필요충분조건은 gcd(a,b)=1임을 알 수 있다.
디오판토스 방정식(The Diophantine equation)
디오판토스는 이집트에서 태어난 그리스 수학자로 그의 묘비에 자신의 생애를 방정식 문제로 기록했다.
신의 축복으로 태어난 그는 인생의 16을 소년으로 보냈다. 그리고 다시 인생의 112이 지난 뒤에는 얼굴에 수염이 자라기 시작했다. 다시 17이 지난 뒤 그는 아름다운 여인을 맞이하여 화촉을 밝혔으며, 결혼한 지 5년만에 귀한 아들을 얻었다. 아! 그러나 그의 가엾은 아들은 아버지의 반 밖에 살지 못했다. 아들을 먼저 보내고 깊은 슬픔에 빠진 그는 그 뒤 4년간 정수론에 몰입하여 스스로를 달래다가 일생을 마쳤다. 이 문구는 디오판토스 묘비에 기록된 것이고 디오판토스의 나이를 x라고 하면 다음의 방정식으로부터16x+112x+17x+5+x2+4=xx=84라는 결과를 얻는다. 즉 디오판토스는 84세까지 살았음을 알 수 있다. |
다시 본문으로 돌아와서 ax+by=c형태의 정수계수 1차방정식을 디오판토스 방정식이라고 한다.
(1) 디오판토스 방정식 ax+by=c가 해를 가질 필요충분조건은 gcd(a,b)|c이다.
(2) (x0,y0)가 디오판토스 방정식 ax+by=c의 특수해이면, 일반해는 다음과 같다.x=x0+bdt,y=y0−adt(t∈Z)(1)의 증명: d=gcd(a,b)=ax+by형태로 나타낼 수 있으므로 디오판토스 방정식이 해를 가질 필요충분이 d|c라는 것은 분명하다.
(2)의 증명: (x,y)를 또 다른 해라고 하자. 그러면 ax0+by0=ax+by이므로 a(x0−x)=b(y−y0)이고, a=dr,b=ds, gcd(r,s)=1이므로 r(x0−x)=s(y0−y)이고 이는 r|y0−y이 성립함을 뜻하고 따라서 y0−y=rt이다. 그러면 x−x0=st이고 따라서{x=x0+bdty=y0−adt이다.
디오판토스 방정식 172x+20y=1000의 해를 구하자.172=8⋅20+1220=1⋅12+8121⋅8+48=4⋅2+0이므로 gcd(a,b)=4이고, 4|1000이므로 디오판토스 방정식의 해는 존재한다.4=12−8=12−(20−12)=2⋅12−20=2(172−8⋅20)−20=2⋅172+(−17)20이므로 1000=250⋅4=500⋅172+(−4250)20이고 여기서 특수해가 x0=500,y0=−4250이라는 것을 알 수 있다. 따라서 일반해는x=500+204t=500+5ty=−4250−1724t=−4250−43t이다.
참고자료:
Elementary Number Theory 7th edition, Burton, McGraw-Hill
정수론 8판, 김응태, 박승안, 경문사
'대수학 > 정수론' 카테고리의 다른 글
6. 페르마의 (작은)정리, 윌슨의 정리 (0) | 2018.11.06 |
---|---|
5. 중국인의 나머지정리, 선형연립합동식 (0) | 2018.11.05 |
4. 정수의 2, 10진 표현, 일차합동식 (0) | 2018.11.02 |
3. 소수와 그 분포, 합동 (0) | 2018.10.30 |
1. 정수의 기본성질 (0) | 2018.10.25 |