Bezout's Identity(베주 항등식) 증명 완벽 이해

오늘은 Bezout's Identity의 증명을 완벽하게 이해 하는 시간을 가져 보겠습니다.

 

베주의 항등식이란?

베주의 항등식의 내용은 다음과 같습니다.

저번에 방정식의 정수해만을 고려하는 부정 방정식의 해법인

1차 Diopantine Equation에 관하여 포스팅을 한 바 있습니다.

 

 

해당 방정식의 정수쌍 (x,y)의 해가 존재할 필요충분조건에 관한 증명을 할 때

Bezout's Identity가 사용이 되었습니다.

 

ax + by = gcd(a,b)

라는 형태의 방정식이 있을 때,

이를 만족시키는 정수쌍 x,y가 반드시 존재한다는 정리입니다.

 

증명을 해보도록 하겠습니다.

 

 

베주의 항등식 증명

"위 식을 만족시키는 정수쌍 x와 y가 존재한다"와 같은

어떤 대상에 대한 존재성을 증명하고자 할 때에는 집합을 사용하는 경우가 많습니다.

 

집합 S를 다음과 같이 정의해 보도록 하죠

 

 

여기서 a,b,x,y는 모두 정수이고,

ax + by > 0을 만족하는 정수쌍 a,b,x,y가 반드시 존재합니다.

그러면 S는 Empty Set이 아닌 것이 되므로,

정렬원리(Well-ordering principle)에 의하여 집합 S는 최소 원소를 가집니다.

 

이 가장 작은 원소를 k라고 해 봅시다.그리고 ax + by = k를 만족하는 정수쌍 x와 y를 각각 x0, y0라고 해 봅시다.그러면 다음과 같은 식이 만들어 집니다.

 

 

ax0 + by0 = k

 

k는 자연수 이므로나눗셈 정리에 의하여

 

a = k * q + r (0 <= r <k)를 만족하는 정수 q와 r이 반드시 존재합니다이 식을 r에 대하여 정리하면r = a-k*q  = a-(ax0 + by0)q  = a(1-x0) + b(y0q)

 

모양을 보아하니,이 r이라는 수는(0<=r < k) 분면 S의 원소처럼 생겼습니다.

 

여기서 r > 0이라고 가정해 보겠습니다.

그러면 당연히 r은 S의 원소가 됩니다.

그런데 여기서 하나 모순점이 발생합니다.

r은 S의 원소이지만, 위 식에서 0 <= r < k라고 되어 있죠.

r < k라는 부분에서

집합 S의 최소원소는 k가 되어야 하는데

r > 0 이라고 가정을 했을 때에는 집합 S의 최소원소가 r이 되면서 모순이 발생합니다. (Proof by contradiction)

 

 

따라서 r > 0 이라는 가정은 거짓이 되고

r = 0이기 때문에

a = k * q에 의하여

k | a라는 결과가 도출됩니다.

 

 

마찬가지로 b에 대해서도 위와 같은 단계로 정리하면

k | b라는 결과를 도출할 수 있습니다.

 

 

그리고 c | a, c | b를 만족하는 자연수 c가 있다고 해 봅시다.

그러면 모든 정수 x와 y에 대하여 c | ax + by도 성립하게 되고

c | axo + by0 = k도 성립하게 됩니다.

 

 

 

최대공약수의 정의에 의하여

k라는 수는 a와 b의 최대공약수가 됩니다.

 

 

ax + by = gcd(a,b)를 만족하는 정수쌍 x와 y가 존재한다는 사실을 증명하였습니다.