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

# Definition

Bézout's identity — Let a and b be integers or polynomials with greatest common divisor a. 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