[Algorithm/기본지식] 유클리드 호제법

 

유클리드 호제법

 

 

https://terms.naver.com/entry.naver?docId=2073670&cid=47324&categoryId=47324

 

 

두 정수 a, b의 최대 공약수를 G(a,b)라고 표현한다.

이때 정수 a, b, q, r (b는 0이 아니다)에 대하여 a = bq + r 이면 G(a, b) = G(b, r)이 성립한다.

 

 

증명

 

G(a, b) = g일 때, 최대공약수의 성질에 의해 a = a′g, b = b′g이고 G(a′, b′) = 1이다. (최대공약수가 g이기 때문에 a′, b′는 서로소 이다.)

a = bq + r 로부터 r = a - bq = g(a′ - b′q) 이고, g는 r의 약수이다.

G(b, r) = g임을 보이기 위해서는 G(b′, a′ - b′q) = 1임을 보이면 된다. => b = b′g, r= g(a′ - b′q)로 표현되기 때문이다.

​

어떤 정수 d가 존재하여 G(b′, a′ - b′q) =d(≠ 1)라고 하면, b′ = dm, a′ - b′q = dn라고 할 수 있고, a′ = b′q + dn = dmq + dn = d(mq + n) 이므로 G(a′, b′) = 1라는 가정에 모순이다. 따라서 G(b′, a′ - b′q) = 1이므로 G(b, r) = g가 성립한다.

 

---

 

단순한 반복을 통해서도 유클리드 호제법이 맞음을 증명할 수 있다.

​

임의의 수 a, b가 있을 때,

1. a%b연산을 통해 나머지 c를 구한다. 만약 나머지 c가 0이 아니라면

2. 1에서 구한 나머지인 c를 이용해 b%c 연산을 한다. 즉, b가 c의 배수인지 확인한다. 아니라면 b%c의 나머지인 c1을 구한다.

3. 2와 같은 방법으로 c%c1의 연산을 통해 c가 c1의 배수인지 확인한다.

4. 위 방법을 반복해 나머지가 0이 될 때 까지 연산을 반복한다.

​

식으로 표현하면\begin{align*}
a &= b \cdot x_1 + c \\
b &= c \cdot x_2 + c_1 \\
&\dots \\
c_{n-3} &= c_{n-2} \cdot x_n + c_{n-1} \\
c_{n-2} &= c_{n-1} \cdot x_{n+1} + c_n
\end{align*}​

와 같은 형태로 나타낼 수 있는데,

$$\text{만약 } c_n = 0 \text{ 이라면, } c_{n-2} \text{ 는 } c_{n-1} \text{ 의 배수이고, } c_{n-3} \text{ 도 } c_{n-1} \text{ 의 배수다.}​$$

결국 나머지 값이 0이 될 때의 c는 a와 b의 최대 공약수이다.

그리고 a, b, x, c (b는 0이 아니다)에 대하여 a = bq + r 이면 G(a, b) = G(b, r) 이 성립한다.