유클리드 호제법

유클리드 호제법(유클리드 互除法, Euclidean Algorithm)은 유클리드 알고리즘이라고도 불리는데, 유클리드의 원론(Euclid's Elements) 제7권에 서술되어 있으며, 글로 보존된 세계 최초의 알고리즘이라고 한다.

유클리드 호제법은 두 자연수 또는 정식에 대한 최대공약수를 구하는 알고리즘의 하나인데, 다음 두 가지 아이디어를 기초로 한다.

1. 만약 $b|a$ 성립하면, $gcd(a,b)=b$이다.
2. 만약 정수 $q$와 $r$에 대해, $a=bq+r$이면, $gcd(a,b)=gcd(b,r)$이다.

출처

• 위키백과 유클리드 호제법