베주 항등식(Bézout's Identity)은 두 정수와 그 최대공약수 사이의 관계를 보여주는 항등식이다. 그 내용은 다음과 같다.

위 세 명제 중 메인은 1번이며, 1번을 증명하는 과정에서 2번 명제와 3번 명제가 따라서 증명된다.

증명은 다음과 같은 순서로 진행된다. 자세한 과정은 아래에 있다.

둘 중 적어도 하나는 0이 아닌 정수 $a$, $b$가 있다. 이때 다음과 같은 집합 $S$를 정의하자.

$S = \left\{ m | m = ax + by > 0, x \in \mathbb{Z}, y\in \mathbb{Z} \right\}$

먼저 $S \ne \varnothing$임을 보이자. 만약 $a > 0$라면 $\left| a \right| = a \times 1 + b \times 0 \in S$이다. 만약 $a < 0$라면 $\left| a \right| = a \times (-1) + b \times 0 \in S$이다. 만약 $a = 0$라면 $b \ne 0$이라서 앞서 a의 경우와 같은 논리로 $\left| b \right| \in S$ 이다. 따라서 집합 $S$ 는 $\left| a \right|$와 $\left| b \right|$ 중 적어도 하나를 원소로 가지므로 $S \ne \varnothing$이다.

집합 $S$는 정의에 따라서 자연수의 부분집합이다. $S \ne \varnothing$이므로 자연수의 정렬성(Well-ordering Principle)[2]에 의해 집합 $S$는 가장 작은 원소를 가진다.

$\therefore$ 집합 $S$의 최소 원소, 즉 $ax + by$ 꼴로 나타낼 수 있는 가장 작은 자연수는 존재한다. 그것을 $d$라고 부르자.

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

나눗셈 정리에 의해, $S$에 속하는 임의의 원소 $x$ 에 대하여 $x = qd + r (0 \le r < d)$라고 할 수 있다. 만약 $x$ 가 $d$의 배수가 아니라고 가정하자.[3] 그렇다면 나머지 $r$ 은 0이 아닌 $0 < r < d$인 자연수이다. 그리고 $x$ 는 집합 $S$ 의 원소이므로 $x = au + bv, u \in \mathbb{Z} , v \in \mathbb{Z}$ 라고 할 수 있다.

$r$ 은 $x$ 를 $d$ 로 나누었을 때 나머지이므로 $d$ 보다 작다. 앞서 $d$ 를 집합 $S$ 에서 가장 값이 작은 원소로 정의했음에도 $d$ 보다 작은 $S$ 의 원소인 $r$ 이 존재하는 것은 $d$의 최소성을 위반하므로 모순이다. 따라서 처음의 가정인 "$x$ 가 $d$ 의 배수가 아니다."는 거짓이다. 따라서 $x$ 는 $d$ 의 배수이다.

$x$ 는 집합 $S$ 의 임의의 원소이므로 집합 $S$ 의 모든 원소는 $d$ 의 배수이다. 따라서 $a$ 혹은 $b$ 가 0이 아닌 정수 일 경우 $|a|$ 혹은 $|b|$ 가 집합 $S$의 원소이기 때문에 $d$ 를 약수로 갖는다. 한편 $a$ 혹은 $b$ 가 0일 경우 0이 아닌 모든 수는 0의 약수이기 때문에 $d$ 를 약수로 갖는다. 따라서 $d$ 는 $a$ 와 $b$ 의 공약수이다.

만약 $e$가 $a,b$의 공약수라고 하자. $a=a'e, b = b'e$이면 $d = ak+bl = e(a'k+b'l)$이므로, $e$는 $d$의 약수이다. 따라서 $a,b$의 모든 공약수는 $d$의 약수이므로, $d$는 약수 중에서 가장 큰 최대공약수이다.

유클리드 호제법을 수행한 뒤 그 과정을 따라가면 $d = ax+by$를 만족하는 정수 $x, y$를 직접 계산할 수 있는데, 이 알고리즘을 확장된 유클리드 호제법(extended Euclidean algorithm)이라 부르기도 한다. 유클리드 호제법이
$a = b q_1 + r_1, b = r_1 q_2 + r_2, r_1 = r_2 q_3 + r_3, \cdots,$
즉
$a = r_{-1}, b = r_{0}, r_i = r_{i+1} q_i + r_{i+2} (0 \le r_{i+2} < r_{i+1})$
의 알고리즘으로 진행되고, 마지막에 $r_n = \gcd(a,b)=d$ (즉 $r_{n+1} = 0$)으로 종결되었다고 하자. 이 때 수열 $x_i, y_i$를 다음과 같이 귀납적으로 정의한다.
$(x_{-1}, y_{-1}) = (1,0), (x_0, y_0) = (0,1), (x_{i+2}, y_{i+2}) = (x_{i} - q_i x_{i+1}, y_i - q_i y_{i+1} )$
이렇게 정의하면 귀납법을 이용해 항상 $r_i = a x_i + b y_i$가 됨을 보일 수 있고, 최종적으로 $d = r_n = a x_n + b y_n$을 얻을 수 있다.

항목 2의 증명을 보면 $d=ax+by$를 만족하는 정수 $x,y$가 존재한다는 것만 알려줄 뿐, 그 $x,y$를 계산하는 방법은 전혀 알려주지 않는다는 것에서 확장된 유클리드 호제법의 진가가 나온다. 알고리즘 정수론적인 관점에서 보면 그런 $x,y$를 실제로 계산하는 것은 잉여역수를 구하는 등 합동식 연산의 기초가 되기 때문에 중요하고, 또한 호제법 알고리즘의 시간 복잡도도 $O( (\log a)^2 )$로 (나눗셈 횟수만 고려하면 $O(\log a)$) 나름 괜찮으니만큼 훌륭한 필수 알고리즘인 것이다.

기호로 적으면 어려워 보이지만, '나머지를 a와 b의 일차결합으로 나타낸다'의 아이디어만 생각하면 손으로 계산하기도 생각보단 할만하다.
a = 6192, b = 1012
6192 = 6*1012 + 120, 120 = a - 6b
1012 = 8*120 + 52, 52 = 1012 - 8*120 = b - 8(a-6b) = -8a + 49b
120 = 2*52 + 16, 16 = 120 - 2*52 = (a-6b) - 2(-8a+49b) = 17a -104b
52 = 3*16 + 4, 4 = 52 - 3*16 = (-8a+49b) - 3(17a-104b) = -59a + 361b
gcd(a,b) = 4 = -59a + 361b

베주 항등식과 위의 확장된 유클리드 호제법은 다음 꼴의 일차 부정방정식을 완벽히 푸는 방법을 제공한다.

베주 항등식의 증명을 참고하면 방정식이 해가 존재할 필요충분조건은 $c \in S$의 여부이므로 바로 증명된다. 만약 $d \vert c$라면 확장된 유클리드 호제법으로 특수해를 구할 수 있다. 일반해에 대한 진술에 대해서는, $(x',y')=(x-x_0,y-y_0)$이 방정식 $ax' + by'=0$의 해여야 하는데, $a/d, b/d$는 서로소이므로 $(b/d) \vert (a/d) x'$에서 $(b/d) \vert x'$가 유도된다. (사실 이것도 베주 항등식을 이용한다.) $x' = (-b/d)k$로 놓으면 결론이 증명된다.

베주 항등식은 변수가 하나인 다항식에 대해서도 성립한다. 위의 $a, b, d$를 모두 최고차항이 1인(monic) 다항식으로 바꾸고, '가장 작은 자연수' 를 '차수가 가장 작은 다항식'으로 바꾸자. 물론 $x,y$는 monic일 필요는 없다. 다만 위의 증명은 유리수, 실수, 복소수 계수에서만 성립한다. 정확히는 계수가 체의 범위에 있을 때. 증명도 위와 거의 동일한데, $S$의 정의를 $ax+by$꼴의 모든 다항식으로 놓고, 차수가 가장 작은 monic 다항식을 $d$로 고르면 된다. 다항식에서도 나눗셈 정리가 나머지 정리라는 이름으로 그대로 먹히기 때문.

다항식 버전의 베주 항등식은 사실 교과과정에서 부분분수분해를 할 수 있는 암묵적인 근거가 된다. 정수론 버전의 베주 항등식은 유사하게 중국인의 나머지 정리의 근거가 되지만, 이건 교과에 안나오니까...

추상대수학 중 특히 환론을 안다면 단항이데알정역(PID)들이 베주 항등식을 만족시킨다는 것을 알 수 있는데, 단순히 이데알 $S=(a,b)$의 생성원을 $d$로 놓으면 된다. 나눗셈 정리와 유클리드 호제법이 성립하는 유클리드정역(ED)은 당연히 된다. 다만 역은 성립하지 않는데, 심지어는 유일인수분해정역(UFD)도 아닌데 베주 항등식은 되는 것들도 있다고 한다...