베주 항등식(Bezout's identity)

베주 항등식은 나눗셈 정리와 최대공약수 개념을 활용하여 증명할 수 있고, 추후 유클리드 호제법을 증명하기 위한 도구적 역할을 합니다.

 

 

---

 

정리($N.T$) 1.5) 베주 항등식
$a,b \in\mathbb{Z}-\{ 0 \}$ 일 때,
$$ax+by=\gcd(a,b)=g$$ 를 만족하는 어떤 두 정수 $x,y\in\mathbb{Z}$ 가 항상 존재한다. 즉, 임의의 영이 아닌 두 정수의 최대공약수는 그 두 정수의 어떤 선형결합 표현으로 반드시 나타낼 수 있다.

증명) $X=\left\{ax+by\mid x,y\in\mathbb{Z}\;,\; ax+by \geq 1 \right\}$ 라 하자. 여기서 $ax+by \geq 1$ 이라는 것은 곧 $ax+by$ 가 $0$ 보다 큰 정수라는 뜻이다. 그러면 $x=a$, $y=b$ 를 택했을 때 $a^2+b^2 > 0$ 이므로 $X$ 는 공집합이 아니다. 고로 자연수의 정렬성(Well-ordering principle)에 의하여 $X$ 는 최소원소를 가지고, $\min (X)=g$ 라 표기하자. $g\in X$ 이므로, $g\geq 1$ 이고 $g=ax+by$ 가 되게 하는 어떤 $x,y\in\mathbb{Z}$ 가 존재한다. 또한 선형결합 성질인 정리($N.T$) 1.2 에 의하면 $c\mid a$ 이고 $c\mid b$ 이면 $c\mid (ax+by)=g$ 가 성립한다. 따라서 이제 $g=\gcd (a,b)$ 임을 보이려면 최대공약수의 정의 중 ② 에 해당하는, $g\mid a$ 와 $g\mid b$ 를 보이면 충분하다.

$g\mid a$ 임을 보이기 위해, $a=qg+r$ 이고 $0\leq r\leq g-1$ 이라 두자. 그러면

$$r=a-qg=a-q(ax+by)=(1-qx)a+(-qy)b$$
가 성립한다. 그런데 $r$ 은 나머지라서 $r\geq 0$ 이고, $1-qx:=X\;,\;-qy:=Y$ 로 생각하면 $r\in X$ 이다. 이때 $r\geq 1$ 이라 가정하자. 그러면 $r\in X$ 가 되고 $1-qx < x$ 이고 $-qy < y$ 이므로 $r<g$ 가 되는데, 이는 $g=\min (X)$ 라는 가정에 모순이다. 따라서 $r=0$ 이 되어야 하고, 이는 곧 $a=qg \;\; \Rightarrow g\mid a$ 임을 뜻한다. $g\mid b$ 또한 비슷하게 증명하면 된다. $_\blacksquare$

 

 

 

따름정리($N.T$) 1.5.1)
$g=\gcd(a,b)$ 라 하자. 그러면 $g$ 는 임의의 두 정수 $m,n$ 에 대하여 $ma+nb$ 꼴로 나타내어지는 정수 중 최솟값에 해당한다.

증명) $g=\gcd(a,b)$ 라 하자. 위의 베주 항등식에 의하여 $g=ax+by$ 를 만족하는 $x,y\in\mathbb{Z}$ 가 존재한다. $g$ 는 $a,b$ 의 최대공약수이므로 $g\mid a$ 이고 $g\mid b$ 이다.

이제 원소 $d\in X$ 를 고려하자. 귀류법을 사용하기 위해서, $X$ 의 원소 중 최솟값이 $d\neq g$ 라 가정하자. 따라서 $d<g$ 가 성립해야 하고, 그러면 $d\mid a$, $d\mid b$ 이기에 $g\neq d\mid g$ 가 성립해야 한다. 그런데 위 베주 항등식에 관한 정리에 의하면 $X$ 의 최소원소는 $\gcd (a,b)$ 즉 $g$ 여야 하고, 이는 모순이다. $_\blacksquare$

 

 

 

정리($N.T$) 1.6)
$g=\gcd (a,b)$ 라 하면, 임의의 $m\in\mathbb{N}$ 에 대해 $\gcd(ma,mb)=mg$ 가 성립한다.

증명) $g\mid a$ 이고 $g\mid b$ 이므로 어떤 정수 $k_1,k_2$ 에 대하여 $a=gk_1$, $b=gk_2$ 가 성립한다. 그러면 $ma=mgk_1$ 이고 $mb=mgk_2$ 이므로 $(mg)\mid (ma)$ 이고 $(mg)\mid (mb)$ 이다.
$mg$ 가 $ma$, $mb$ 의 최대공약수임을 귀류법으로 보이기 위해 $d>mg$ 인 최대공약수 $d$ 가 존재한다고 하자. 즉 $d\mid (ma)=(mgk_1)$ 이고 $d\mid (mb)=(mgk_2)$ 가 성립한다. 그러면 베주 항등식에 의하여 $d$ 는 $(ma)x+(mb)y=mg$ 또한 나누어야 한다. 하지만 이는 $d>mg$ 라는 가정에 모순이다. $_\blacksquare$

 

 

 

 

 

[참고문헌]

Introduction to Number Theory - William W. Adams, Larry Joel Goldstein