유클리드 호제법

두 개의 양수 (a, b)의 최대공약수를 구하는 방법.

 

요약

\( a \geq b \)이고, a를 b로 나눈 몫을 q, 나머지를 r이라 할 때, 다음과 같이 쓸 수 있다.

\( a = bq + r, (0 \leq r < b) \)

이 때, (a, b의 최대공약수) = (b, r 최대공약수)이다.

---

증명

\( a = bq + r, (0 \leq r < b) \)

이 때, \( r = 0 \) 이면, b는 (a, b)의 최대공약수이다. (끝)

 

만약 \( r > 0 \) 이면, 위의 식을 r에 대해 정리한다. → \( r = a - bq \)

이제 (a, b)의 임의의 공약수 e를 이용해서, \( r = a - bq \) 식을 다시 써보자.

 

 

\( a = \textcolor{red}{e}k_{1} \)

\( b = \textcolor{red}{e} k_{2} \)

\( r = ( \textcolor{red}{e} k_{1})  - ( \textcolor{red}{e} k_{2})q \)

\( r = ( \textcolor{red}{e} k_{1})  - ( \textcolor{red}{e} qk_{2}) \)

\( r = \textcolor{red}{e} \{ k_{1}  - (qk_{2}) \} \)

 

\( r = a - bq \)의 우변 \( a - bq \)는 (a, b)의 임의의 공약수 e로 나누어 떨어지는 것을 알 수 있다.

따라서 r은 e로 나누어 떨어진다.

그러므로 e는 (b, r)의 공약수가 된다.

---

이번에는 e'를 (b, r)의 임의의 공약수라 하고, e'를 이용해서, \( a = bq + r \) 식을 다시 써보자.

 

\( b = \textcolor{blue}{e'}k_{3} \)

\( r = \textcolor{blue}{e'}k_{4} \)

\( a = \textcolor{blue}{e'}k_{3}q + \textcolor{blue}{e'}k_{4} \)

\( a = \textcolor{blue}{e'} (qk_{3} + k_{4}) \)

 

\( a = bq + r \)의 우변 \( bq + r \)은 e'로 나누어 떨어지는 것을 알 수 있다.

따라서 a는 e'로 나누어 떨어진다.

그러므로 e'는 (a, b)의 공약수가 된다.

---

 

정리하면,

(a, b)의 공약수는 (b, r)의 공약수이고,

역으로 (b, r)의 공약수는 (a, b)의 공약수이다.

따라서 (a, b 공약수 전체 집합)은 (b, r 공약수 전체 집합)과 같다.

즉, (a, b 최대공약수) =  (b, r 최대공약수)이다.

 

---

(a, b) 최대공약수 구하기 → \( a = bq + r, (0 \leq r < b) \)

\( r = 0 \) 이면, 최대공약수는 b

\( r > 0 \) 이면, (b, r) 최대공약수 구하기 → \( b = rq + r{'} \)

\( r{'} = 0 \) 이면, 최대공약수는 r

\( r{'} > 0 \) 이면, (r, r') 최대공약수 구하기 → 반복

이 방법을 나누어 떨어질 때까지 계속하면, 유한번의 나눗셈에 의해서 반드시 (a, b)의 최대공약수를 구할 수 있다.

 

예) 247, 962

\( 962 \div 247 = (247 \times 3) + 221 \)

\( 247 \div 221 = (221 \times 1) + 26 \)

\( 221 \div 26 = (26 \times 8) + 13 \)

\( 26 \div 13 = (13 \times 2) + 0 \)

따라서 (247, 962)의 최대공약수는 13이다.