📂정수론

확장된 유클리드 정리 증명

정리 ¹

두 정수 $a,b$ 에 대해 $ax + by = \gcd (a,b)$ 는 반드시 정수해를 가진다.

설명

이 정리는 $\gcd (a,b)$ 가 $a$ 와 $b$ 의 일차^linear식으로 나타날 수 있다는 의미에서 선형 합동 정리^{linear Congruence theorem}이라고도 불린다.

다소 복잡한 모양새고 존재성만 논하기 때문에 직접적으로 쓰이긴 어려울 것 같지만 의외로 굉장히 많이 사용한다. 구체적인 해 $(x,y)$ 를 찾아주는 건 아니지만 $a$, $b$ 에 대한 관계식에서 출발할 수 있다는 것만 해도 굉장한 수확이기 때문이다. 실제 $x$, $y$ 가 무엇인지 알 바 아닐 때엔 무척 유용하게 쓸 수 있다.

증명

초등적 증명

전략: 확장된 유클리드 정리라는 이름답게 유클리드 호제법을 반복한다. 그 때문에 꼭 정리라는 말만 쓰지 않고 확장된 유클리드 알고리즘이라 부르기도 한다.

---

유클리드 호제법: $ r_i<r_{i+1}$ 에 대해 점화식 $r_{i-1} = q_{i+1} \cdot r_{i} + r_{i+1}$ 을 만족시키는 $a: = r_{-1}$ 와 $b:=r_{0}$ 를 정의하자. $r_{n+1} = 0$ 을 만족시키는 $n$ 에 대해, $r_{n} = \gcd (a,b)$

유클리드 호제법에 따르면 $r_{1}$ 은 $$ r_{1} = a - q_{1} b $$ 즉 $a$ 와 $b$ 에 대한 선형결합으로 나타낼 수 있다. 한편 $$ r_{2} = b - q_{2} r_{1} $$ 인데, 바로 위의 $r_{1} = a - q_{1} b$ 를 대입하면 $$ \begin{align*} r_{2} =& b - q_{2} r_{1} \\ =& b - q_{2} ( a - q_{1} b ) \\ =& -q_{2} a + ( 1 + q_{1} q_{2} ) b \end{align*} $$ 즉 $r_{2}$ 역시 $a$ 와 $b$ 에 대한 선형결합으로 나타낼 수 있다. 이를 $n$ 번 반복하면 $r_{n}$ 은 어떤 $x,y \in \mathbb{Z}$ 에 대해 $$ r_{n} = x a + y b $$ 로 나타낼 수 있을 것이다. 유클리드 호제법에서 $r_{n} = \gcd (a,b)$ 이므로, $(x,y)$ 는 $ax + by = \gcd (a,b)$ 의 해로써 존재한다.

■

대수적 증명

정수환 $\mathbb{Z}$ 는 PID이므로 베주 정역이다.

■

같이보기

일반화: 베주 정역

대수적 증명에서 $\mathbb{Z}$ 가 베주 정역임을 지적했던 것처럼, 베주 정역이라면 그곳이 어디든 확장된 유클리드 정리가 성립한다.