1차 Diophantine equation 해 존재 조건과 증명

디오판토스 방정식이란

부정방정식에서 정수해만을 고려한 방정식을 말한다

 

ax + by = c라는 indeterminate equation이 주어져 있을 때

정수해 (x , y)쌍이 존재할 필요충분조건은 다음과 같다.

 

d | c

 

증명

다음 두 가지를 증명하면 된다

1 ) ax + by = c 의 정수해 x1와 y1가 존재하면 d | c이다.

 

2 ) d | c 이면 ax + by = c 의 정수쌍 x와 y가 존재한다.

 

1) 증명

 

Z는 정수의 집합이다

 

d를 gcd(a,b)로 정의하고

aZ + bZ 집합을 {ax + by | x,y는 Z의 원소} 이라고 정의하면

aZ + bZ = dZ를 만족한다.

 

그러면 당연히 ax + by = c에 대하여

c 는 dZ의 원소이므로

d|c를 만족한다.

 

 

2) 증명

d | c에서 다음을 만족시키는 적당한 정수 k가 존재한다.

c = d * k (k는 정수)

 

부정방정식 ax + by = d * k에 대하여

ax + by = d를 존재하는 정수쌍 x와 y가 반드시 존재하며, 이를 x1, y1이라고 해보자

ax1 + by1 = d이므로

a(x1 * k) + b(y1 * k) = d * k이다

 

따라서 ax + by = d * k를 만족하는 정수쌍 x와 y는 다음과 같이 존재한다.

x = k * x1

y = k * y1

 

따라서 ax + by = c의 정수해가 존재할 필요충분조건은 d | c이다