Euclidean Algorithm(유클리드 호제법)

Related to: Algorithms

개요

유클리드 알고리즘은 두 자연수의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 의미한다.

2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

$a = k x, b = k y, k = g cd (a, b), r = a % b = k x % k y = x % y$

$a = b q + r ⟹ k x = k y q + r ⟹ x 과 y q 는 서로소$

$r = k (x - y q) = k p ⟹ 나머지 r 도 k 의 배수$

$k x = k (y q + p), x = y q + p, p = x - y q$

x와 yq는 서로소이므로 1 이외에 공약수가 존재하지 않는다. 따라서 나머지 r은 x와 yq에 대하여 서로소이다.

그러므로, a와 b의 최대공약수는 k인 것과 같이 b와 r의 최대 공약수도 k이다.