베주 항등식

$\vert a \vert$+$\vert b \vert$>0 , a ∈ $\mathbb{Z}$, b∈ $\mathbb{Z}$ 일때, gcd(a,b)=d (d는 a,b의 최대공약수) 라면 아래 세가지 명제가 성립한다.

1. ax + by = d를 만족하는 정수 x,y가 존재

2. d는 정수 x, y에 대하여 ax + by꼴로 표현 될 수 있는 가장 작은 자연수이다.

3. 정수 x, y에 대하여 ax + by꼴로 표현 되는 모든 정수는 d의 배수이다.

증명.

집합 S={m | m = ax + by > 0, ab≠0 $\lor$ a+b≠0, a,b,x,y ∈ $\mathbb{Z}$}를 정의하자.

$|a| =\begin{cases}\mbox{a*1 + b*0 ∈ S}&\mbox{if a > 0}\\\mbox{a*(-1) + b*0 ∈ S}&\mbox{if a < 0}\\\mbox{0}&\mbox{if a = 0... then b ≠ 0 -> |b| ∈ S}\end{cases}$

따라서 집합S는 |a|와 |b|중 적어도 하나는 원소로 가지므로 S는 공집합이 아니다...(1).

S가 자연수집합의 부분집합 이므로 가장 작은 원소가 존재한다. 이것을 d라고 하자.

 

S의 정의에 의해, 어떤 정수 k, l 에 대하여 d = ak + bl...(i) 이다.

나눗셈 정리에 의해 S의 임의의 원소 z 에 대해 z = dq + r (0 $\leq$ r < d)를 만족시키는 정수 q, r이 유일하게 존재한다.

z는 S의 원소이므로 z = au + bv...(ii)(u ∈ $\mathbb{Z}$, v ∈ $\mathbb{Z}$)이다.

이때 r≠0이라고 가정한다면 

0 < r = z - dq = (ii) - (i)q = au + bv - (ak + bl)q = au - akq + bv - blq = a(u - kq) + b(v - lq)  ∈ S이다.

그런데 d는 (1)에 따라 S의 가장 작은 원소이고,  r < d와 모순 되므로 r≠0는 거짓이다.

즉 z = qd (q∈$\mathbb{Z}$). z는 S의 임의의 원소 이므로, S의 모든원소는 d의 배수이다...(iii)

그러므로 a=0인 경우 |b|∈S이므로 b는 d를 약수로 가진다. 이때 0이 아닌 모든 수는 0의 약수 이므로 a또한 d를 약수로 가진다. 즉 d는 a와 b의 공약수이다. ...(2)

 

w가 a, b의 공약수라고 하자. a = a'w, b = b'w 이면 d = (i) = ak + bl = w(a'k + b'l)이므로  w는 d의 약수이다.

즉 a와 b의 공약수는 d의 약수이다....(3)

 

정리하면

두 정수 a,b가 주어 졌을때 ax+by꼴로 표현될 수 있는 자연수집합의 부분집합 S ≠ Φ 를 가진다...(1)

그 중 가장 작은 수 d는 a,b의 최대공약수이다...(2,3)

ax+by꼴로 표현될 수 있는 모든 자연수는 d의 배수이다...(iii)

따라서 1,2,3번 명제는 모두 참이다.

----------------------------------

 

사족1.

gcd(a,b)=d에 대해서

c∣a∧c∣b⇒c≤d로 정의할경우 gcd(0,0)은 정의 되지 않고 c∣a∧c∣b⇒c∣d.로 정의할 경우 gcd(0,0)=0이다.

gcd(0,0)=0인 경우 ${m|m=(ax+by)/gcd(a,b), (a,b,x,y∈ $\mathbb{Z})} = \mathbb{Z}$는 참이다.

사족2.

ax+by=gcd(a,b)*k, k∈$\mathbb{Z}$이므로, gcd(a,b)=1인 경우만  ax+by=1 을 만족하는 x가 존재한다.

(k=1/gcd(a,b)이므로)

따라서 ax+by=1를 만족하는 x를 찾으면  ax ≡ 1 (mod b)를  만족하는 x를 찾을수 있다.

(by ≡ 0 (mod b) 이므로)

이는 법 b에서 a의 곱셈에 대한 역원이며 ax+by=gcd(a,b)를 만족하는 x는 확장 유클리드 호제법으로 찾을 수 있다.