유클리드 호제법은 gcd(a,b)=gcd(b,r)로 알려져있지만 더 일반화된 형태로 gcd(a,b)=gcd(a,b+ak)가 성립한다 증명은 다음과 같다

d=gcd(a,b)라고하자 a와 b+ak가 있을때 둘을 d로 나눈 a/d와 b/d+ak/d가 서로소이므로 a와 b+ak의 최대공약수가 d이다