베주 항등식 (Bézout's Identity) 은 다음과 같습니다.
두 정수 $a$, $b$에 대하여 $d = \gcd(a, b)$이면, $d = am + bn$인 두 정수 $m$, $n$이 존재한다.$gcd(a, b)$는 최대공약수 입니다.
먼저 집합 $S$를 다음과 같이 정의한다.
$S$의 어떤 원소 $s$가 $s_{m}$의 배수가 아니라 하자.
$$ S = \left\{ t | t > 0, t = am + bn, m \in \mathbb{Z}, n \in \mathbb{Z} \right\} $$
$a^{2} + b^{2}$은 양의 정수 (자연수) 이므로, $S$는 $a^2 + b^2$를 원소로 가진다.
따라서 $S$는 공집합이 아니므로 자연수의 정렬 원리 에 따라 최소 원소가 존재한다.
$S$의 최소원소를 $\min(S) = s_{m}$라 하자.
$S$의 모든 원소 $s$는 $s_{m}$의 배수라는 것을 보이자.
$s_{m} \mid s$ 증명
나눗셈 정리 에 의해, $s = u s_{m} + v, 0 \leq v \le s_{m}$ 이라 할 수 있다.
$v = 0$이면 $s$가 $s_{m}$의 배수가 되기 때문에, $0 \le v \le s_{m}$ 이라 할 수 있다.
또, $S$의 정의에 따라 $s$는 어떤 정수 $x$, $y$에 대하여 $s = ax + by$ 라 할 수 있고, $s_{m}$도 마찬가지로 어떤 정수 $p$, $q$에 대하여 $s_{m} = ap + bq$이다.
$s = u s_{m} + v$에서 $v = u s_{m} - s$이고, $s = ax + by$, $s_{m} = ap + bq$에서 $v = u s_{m} - s = u (ap + bq) - (ax + by)$이다.
$v = u (ap + bq) - (ax + by) = aup + bup - ax - by = a(up - x) + b(up - y)$이라 할 수 있다.
이때, $up - x \in \mathbb{Z}$ , $up - y \in \mathbb{Z}$이므로 $S$의 정의에 따라 $v \in S$이다.
그런데, $S$의 최소 원소가 $s_{m}$인데, 동시에 $0 \le v \le s_{m}$ 이므로, 모순이다. ($v \le s_{m}$에서 $v$가 최소 원소가 되어버림)
따라서 전제조건인 "$S$의 어떤 원소 $s$가 $s_{m}$의 배수가 아니다"는 거짓으로, $S$의 모든 원소 $s$는 $s_{m}$의 배수이다.
$S$의 정의에서 $a \times 1 + b \times 0 = a$, $a \times 0 + b \times 1 = b$가 $S$의 원소이다.
$S$의 모든 원소는 $s_{m}$의 배수이므로 $a$, $b$도 $s_{m}$의 배수이다. (= $s_{m}$은 $a$, $b$의 약수, 즉 공약수이다.)
$s_{m}$은 $a$, $b$의 공약수이므로, 최대공약수 $d$의 약수이기도 하다. 따라서 어떤 정수 $c$에 대해 $c s_{m} = d$라 할 수 있고, $s_{m} = ap + bq$에서 $c s_{m} = d = a(cp) + b(cq)$이다.
$d$가 $S$의 원소이므로, $d = am + bn$인 두 정수 $m$, $n$이 존재한다.