선형 디오판토스 방정식
간단히 말하면 부정방정식 중 정수해만을 구하는 방정식을 말한다. 디오판토스 방정식에는 여러 형태가 있지만 유클리드 호제법과 베주 항등식에 나오는 식과 유사한 ax+by=c를 선형 디오판토스 방정식(Linear Diophantine equation)이라 부른다. c=gcd(a,b)면 베주 항등식이 된다.
정리: a,b∈N이라고 하자. 그러면 gcd(a,b)=ax+by를 만족하는 정수 x,y∈Z가 존재한다.
베주 항등식의 해는 유일하지 않으며 확장된 유클리드 호제법으로 구할 수 있다.
해가 존재하는 지 증명
S=ax+by | x,y∈Z라 정의하고 집합 S가 다음 세개의 성질을 만족함을 증명하자.
a,b ∈S
a=a⋅1+b⋅0∈S, b=a⋅0+b⋅1∈S
u∈S⟹u⋅t∈S, ∀t∈Z
u∈S이면 ∃ x1,y1∈Z s.t.u=ax1+by1이며 u⋅t=t(ax1+by1)=a(tx1)+b(ty1)∈S
u1,u2∈S⟹u1±u2∈S
u1,u2∈S라 하면 u1=ax1+by1, u2=ax2+by2를 만족하는 정수 x1,x2,y1,y2가 존재한다.
u1±u2=ax1+by1± (ax2+by2)=a(x1±x2)+b(y1±y2)∈S
따라서 a=bq+r, 0≤r<b에 대하여 a,b∈S이므로 a−bq=r∈S이다. r=0인 경우 gcd(a,b)=b이고 r≠0이면 b=rq1+r1, 0≤r1<r로 표현할 수 있고 b,r∈S이므로 r1=b−rq1이 되어 S의 원소가 된다. 이를 마지막까지 반복하면 rn=gcd(a,b)∈S가 되어 gcd(a,b)=ax+by를 만족하는 정수 x, y가 존재하며 유클리드 알고리즘의 증명도 할 수 있다.
선형 디오판토스 방정식의 일반해
그렇다면 베주 항등식이 아니라 선형 디오판토스 방정식 ax+by=c에 대해 (x,y)의 해를 구해보자. 이전 포스팅과 위에서 베주 항등식 ax+by=gcd(a,b)=d에 대해 성립하게 만드는 x, y가 반드시 존재하고 ax+by로 표현되는 모든 정수는 d의 배수임을 확인하였다.
즉, 앞서 베주 항등식을 토대로 ax+by=c의 해가 존재 유무와 c는 gcd(a,b)의 배수라는 조건은 서로 필요충분조건임을 확인하였다. 선형 디오판토스 방정식의 특수해가 존재하고 우변이 a와 b의 최대공약수의 배수임을 알아냈으니 일반해를 표현해보자.
(x,y)가 임의의 해라고 가정하면 ax0+by0=ax+by이고 이를 정리하면 a(x−x0)=−b(y−y0)이다. 여기서 양변을 gcd(a,b)=d로 나누면 ad(x−x0)=−bd(y−y0)인데 gcd(ad,bd)=1이므로 ad|y−y0이다. 따라서 적당한 정수 kx에 대해 정리하면 adkx=−(y−y0)이고 정리하면 y=y0−adkx이다. 마찬가지로 x에 대해 정리하면 x=x0+bdky를 얻는다. 따라서 d=gcd(a,b)이므로 ax+by=c의 정수해 (x,y)는 특수해 x0,y0에 대해 [(x0+bdk,y0−adk),k∈Z]로 표현할 수 있다.
확장 유클리드 호제법
확장 유클리드 호제법은 유클리드 호제법을 역으로 계산하여 ax+by=c를 만족하는 (x,y)쌍을 구하는 알고리즘이다.
먼저 x,y의 점화식을 도출하기 위해 이전의 유클리드 호제법 과정을 다시 작성해보자.
a=bq+r2
b=r2q2+r3
r2=r3q3+r4
⋯
rn=rn+1qn+2와 같이 전개가 되어 결국 마지막에 남는 값이 최대공약수가 되고 이것을 참고하면 아래와 같은 조건이 생긴다.
rn+2=rn−rn+1qn+2, axn+byn=rn
=axn+byn−(axn+1+byn+1)qn+2
=a(xn−xn+1qn+2)+b(yn−yn+1qn+2)
⟹(xn+2,yn+2)=(xn−xn+1qn+2,yn−yn+1qn+2)
위와 같이 점화식을 도출하였고 유클리드 호제법의 결과에 따라 gcd(a,b)=rn+2라 하자. 그리고 점화식의 초항이 필요한데 유클리드 호제법의 전개식을 보면 a와 b에 대해서도 r과 같이 해석할 수 있으므로 r0=a, r1=b라 하면 a=ax0+by0에서 (x0,y0)=(1,0)이고 b=ax1+by1에서 (x1,y1)=(0,1)이다. x, y에 대해 점화식과 초항을 구하였으므로 차례대로 계산하면 된다. 아래 예시를 구해보자.
예제
두 수 710, 68의 최대공약수를 구하고 gcd(710,68)=710x+68y를 만족하는 정수 x, y를 구하여라.
유클리드 호제법을 사용하면 gcd(710,68)은 금방 아래와 같이 구할 수 있다.
710=68⋅10+30
68=30⋅2+8
30=8⋅3+6
8=6⋅1+2
6=2⋅3으로 gcd(710,68)=2를 구하였다.
이제 이걸 다시 역산하면 x, y값이 아래와 같이 나온다.
2=8−6⟸2=8−6
=4⋅8−30⟸6=30−8⋅3
=68⋅4−30⋅9⟸8=68−30⋅2
=710⋅(−9)+68⋅94⟸30=710−68⋅10
∴x=−9, y=94
정수해가 구해졌으므로 위의 베주항등식의 일반해에 대입하면 다른 해를 구할 수 있다. 위에서 구한 일반해에 대입하면 (x,y)는 각각 (−9+682k,94−7102k)로 k가 어떤 정수건 다른 해를 만들 수 있다. 예를 들어 1을 대입 시 (25,-261)이 나오는데 문제에 제시된 수식에 대입하면 710⋅25+68⋅(−261)=2가 성립한다.
정리: a,b∈N에 대하여, gcd(a,b)=1과 ∃x,y∈Zs.t. ax+by=1은 필요충분관계이다.
앞서 베주 항등식을 통해 증명하였으므로 생략하겠다.
정리: ax+by=1이면 gcd(a,b)=gcd(a,y)=gcd(x,b)=gcd(x,y)=1이 성립한다.
정수해를 갖는 조건이라면 베주 항등식에 따라 우변은 gcd(a,b)의 배수여야 하므로 gcd(a,b)=1이다. 그리고 a, b와 똑같은 관점으로 다른 미지수에도 적용 가능하므로 제시된 조건을 만족한다.
정리: a,b∈N에 대해 gcd(a,b)=d⇒gcd(ad,bd)=1
정리: a,m,n∈N라 하면, gcd(a,mn)=1⟺gcd(a,m)=1이고 gcd(a,n)=1이다.
필요충분조건임을 증명하기 위해 제시된 명제와 그 역이 성립함을 증명하자.
gcd(a,mn)=1일 때 ax+mny=1을 만족하는 정수 x, y가 존재한다. a(x)+m(ny)=1로 보면 gcd(a,m)=1이며 a(x)+n(my)=1로 보면 gcd(a,n)=1이다.
역으로 gcd(a,m)=gcd(a,n)=1이라 하자. 그럼 ax0+my0=1과 ax1+ny1=1을 만족시키는 정수 x0,x1,y0,y1이 존재한다.
1=ax0+my0(ax1+ny1)=ax0+amx1y0+mny0y1
=a(x0+mx1y0)+mn(y0y1)=1
∴gcd(a,mn)=1
정리: a,b,S∈N이라 하자. a|S, b|S, gcd(a,b)=1이면 ab|S이다.
a|S, b|S에 따라 적당한 정수 x, y에 대해 ax=by=S이다. 그렇다면 a|by가 성립하고 gcd(a,b)=1에 따라 a|y이다. 그리고 적당한 정수 z가 존재하여 az=y이고 S=b⋅az=abz가 되어 ab|S를 만족한다.
작성에 도움이 된 자료
- KMO 수학경시 정수론, 장환수학, 임장환 저
'Math > Number theory' 카테고리의 다른 글
정수론 | 소수와 합성수 (0) | 2020.03.09 |
---|---|
정수론 | 약수와 배수 유형문제 (0) | 2020.03.06 |
정수론 | 유클리드 호제법, 베주 항등식 (0) | 2020.02.22 |
정수론 | 양의 정수의 약수개수와 약수의 총합 (0) | 2020.02.19 |
정수론 | 약수와 배수 (0) | 2020.02.15 |