Bézout's identity - 베주 항등식(Part. 1)

# Definition

Bézout's identity — Let a and b be integers or polynomials with greatest common divisor d. Then there exist integers or polynomials x and y such that ax + by = d. Moreover, the integers or polynomials of the form az + bt are exactly the multiples of d.
(reference)

---

Extended Euclidean과 연결되는 정수론의 기본 정리 중 하나이다.

증명부터 해보자.

 

$Lemma \ 1)$   $For \ \forall a, b \in \mathbb{N} \left(a \neq 0 \lor b \neq 0 \right)$ $\ Let \ S \ = \ \left\{ ax+by>0 \ | \ x, y \in \mathbb{Z} \right\}$  $Then \ S \neq \emptyset$

---

$a \neq 0 \lor b \neq 0$ 에서 일반성을 잃지않고 $a \neq 0$이라 두었을 때 $x = \pm1, y = 0$이라면

$|ax+by|=a\neq0$, $|ax+by| \in S$으로 $S$가 공집합이 아님을 알 수 있다.

 

$Proposition \ 1)$ $For \ \forall \ a,b, l \in \mathbb{N} \left(a \neq 0 \lor b \neq 0 \right)$ $\ let \ g=GCD(a,b)$, $then$ $there$ $exists$ $\exists x,y \in \mathbb{Z}$ $such$ $that$ $\ ax+by=g$

---

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

 

$S \subset \mathbb {N}$ , $S \neq \emptyset$(Lemma 1에 의해서) 가 성립하기에 Well-ordering principle에 의해 최솟값 $m \ = \ min\left\{ S \right\}\left(m \in \mathbb{N}\right)$ 를 잡을 수 있다( *반드시 존재한다 ).

$m = ax_{1} + bY_{1} \left( x_{1}, y_{1} \in \mathbb {Z} \right)$로 두고 다른 임의의 값 k를 잡자.

$let \  \forall k \in S, k = ax_{2} + by_{2} \left( x_{2}, y_{2} \in \mathbb{Z} \right)$

$k > m$ 일 것이고 $k = mq + r (0 \leq r < m)$ 으로 표현할 수 있다.

$\therefore \ k$ $= mq + r$ $= \left(ax_{1} + bY_{1}\right)q + r$

$r$ $= k - mq$ $= \left(ax_{2} + by_{2}\right) - \left(ax_{1} + by_{1}\right) q$ $=a\left(x_{2} - qx_{1}\right) + b\left(y_{2} - qy_{1}\right)$

$m \not| k$ 라고 가정해보면$r \in \mathbb{N}$임을 알 수 있고 $r < m$이 성립하게 되어 m이 최솟값이라는 가정에 모순된다. 따라서 $m | k$ 가 항상 성립하게 된다.

두 가지 경우로 나눠서 생각을 해보자.

1) $a = 0 \lor b = 0$

일반성을 잃지 않고 $a = 0$이라고 하면 $GCD(a,b) = GCD(b, 0) = 0$이 얻어지고 $x=0 \  and \ y =0$라는 쌍으로 표현 할 수 있음이 자명하다.

(* 본 증명에서는 증명의 간결함을 위하여 $For \ \forall n \in \mathbb{N} \ GCD(n, 0) = 0$으로 정의한다.)

2) $a \neq 0 \land b \neq 0$

$a \in S \land b \in S$ 에서 $m|a \land m|b,\ \therefore m|g$ 임을 알 수 있다.

$g = mG\left(G \in \mathbb{Z} \right)$라 두자.

$g$ $= mG$ $= \left(ax_{1} + by_{1}\right)G$ $= a(Gx_{1}) + b(Gy_{1})$ 

$x = Gx_{1}$, $y =  Gy_{1}$으로 표현 가능하다는 것이 얻어진다.

 

$Proposition \ 2)$ $For \ \forall \ a,b,l \in$ $\mathbb{N} \left(a \neq 0 \lor b \neq 0 \right)$ $let$ $g$ $=GCD(a,b)$, $then$ $there$ $exists$ $\exists x,y \in \mathbb{Z}$ $such$ $that$ $\ ax+by=gl$

---

Proposition 1로부터 $g = ax_{1} + by_{1}$ 라 두면

$gl=\left(ax_{1}+by_{1}\right)l$ $= a\left(lx_{1}\right) + b\left(ly_{1}\right)$ 으로 표현이 가능함을 알 수 있다.

 

$Proposition \ 3)$ $For \ \forall \ a,b,x,y l \in$ $\mathbb{N} \left(a \neq 0 \lor b \neq 0 \right)$ $let \ g=GCD(a,b)$, $then \ g|ax+by$

---

$g|x \land g|y$ 이므로 자명하게 $g|ax+by$가 성립한다.

 

Proposition 1, 2, 3으로부터

$Theorom \ 1)$ $For \ \forall \ a,b,x,y l \in$ $\mathbb{N} \left(a \neq 0 \lor b \neq 0 \right)$ $let \ g=GCD(a,b)$, $S$ $= \ \left\{ax+by>0 \ | \ x,y \in \mathbb{Z} \right\}$ $T\ = \ \left\{Mg \ | \ M \in \mathbb{Z} \right\}$, $then \ S = T$ 

---

 

이로써 정수에 대한 Bézout's identity의 증명이 완료된다.

일반적인 확장은 Part.2에서, 다항식으로의 확장은 Part.3에서 마저 기술하겠다.

https://ilikechicken.tistory.com/26

Bézout's identity - 베주 항등식(Part. 3)

https://ilikechicken.tistory.com/26