Skip to main content

Posts

Let thine heart retain my words: Keep my commandments, and live.

유클리드 호제법

· 5 min read
Jeongwon Her

euclid
최대공약수와 최소공배수를 구하는 방법

유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘 중 하나입니다. 호제법互除法이라는 한자어에서 볼 수 있듯, 몫과 나머지를 서로(互) 나누어(除) 최대공약수를 구하는 알고리즘 입니다.




정리

a,bZa,b\in {\mathbb {Z}}이고, aabb로 나눈 나머지가 rr이라고 하자. (여기서 aba\geq b이고, rr0r<b0\leq r \lt b인 정수.)

※ 피제수a와 제수b는 정수Z이고 피제수a는 제수b보다 크거나 같고, 나머지r는 0보다 크거나 같고 제수b보다 작다.

aabb의 최대공약수를 (a,b)\left(a,b\right) 라고 하면, 다음이 성립한다.

(a,b)=(b,r).\left(a,b\right)=\left(b,r\right).

※ 피제수a 제수b의 최대공약수는 제수b와 나머지r의 최대공약수와 같다.




증명

a,bZa,b\in {\mathbb {Z}}이고, aba\geq b라고 하자.

그러면, a=bq+ra=bq+ra=bq+ra=bq+r을 만족하는 유일한 정수 q,rq,r이 존재한다. 이때, 0r<b0\leq r \lt b이다.

(a,b)=d,a=dα,b=dβ\left(a,b\right)=d,a=d\alpha ,b=d\beta라고 하자. 즉, α\alphaβ\beta는 서로소이다.

a=bq+r.dα=dβq+rdr.\begin{aligned} &a=bq+r. \newline &\Rightarrow d\alpha =d\beta q+r \newline &\Rightarrow d|r. \end{aligned}

(즉, rrdd의 배수)

이제, r=dρr=d\rho.라고 하자. 여기서 β\betaρ\rho가 서로소라면, b(=dβ)b(= d\beta)r(=dρ)r(=d\rho)의 최대 공약수도 dd가 된다.

만약 (β,ρ)=d>1\left(\beta ,\rho \right)=d'>1 (서로소가 아닌 수, 즉 다른 공약수를 가지는 수)라면, β=dβ,ρ=dρ\beta =d'\beta ',\rho =d'\rho'으로 두었을 때,

a=bq+r.dα=dβq+dρ=ddβq+ddρ=dd(βq+ρ).α=d(βq+ρ).\begin{aligned} &a=bq+r. \newline &\Rightarrow d\alpha =d\beta q+d\rho =dd'\beta 'q+dd'\rho '=dd'\left(\beta 'q+\rho '\right). \newline &\Rightarrow \alpha =d'\left(\beta 'q+\rho '\right). \end{aligned}

이 되므로, dαd'|\alpha 이다. (즉, α\alphadd'의 배수)

즉, dα,dβd'|\alpha ,d'|\beta가 되어 α\alphaβ\beta는 서로소라는 것에 모순이다. 이는 (β,ρ)=d>1\left(\beta ,\rho \right)=d'>1 라는 가정에서 나타나는 모순이므로 (β,ρ)=1\left(\beta ,\rho \right)=1 (즉, β와 p는 서로소)이다.

따라서 곧 (b,r)=d\left(b,r\right)=d라는 것이다.


ab의 최대공약수 d가 있다고 할때 dα = dβ + r이고, (α,β)=1 서로소이다. 따라서 rd의 배수여야 한다. r=dρ

이때 (β,ρ)>1 즉 다른 나누어지는 수 d'가 있다면 α,β가 서로소라는 가정에 모순이기에 (β,ρ)=1 서로소이다. 따라서 (dβ,dρ)=(b,r)=d=(a,b)이다.




구현

그렇다면 프로그래밍 언어로 어떻게 구현할 수 있을까요? 먼저 큰 숫자의 최대공약수를 구하는 예제를 봅시다.

        a = b × q   + r
78696 = 19332×4 + 1368
19332 = 1368×14 + 180
1368 = 180×7 + 108
180 = 108×1 + 72
108 = 72×1 + 36
72 = 36×2 + 0

규칙을 찾으셨나요?

ab의 최대공약수는 상대적으로 작은 br의 최대공약수와 같기 때문에 br의 최대공약수를 찾을 때까지(나머지r이 0이 될때까지) 반복합니다.

나머지가 0으로 떨어질때까지 gcd를 재귀적으로 호출하는 방법으로 구현해봅시다!

// c/c++
int gcd(int a, int b) {
return b ? gcd(b, a%b) : a;
}

유클리드 호제법을 bitwise shift를 사용해 더 빨리 계산하는 binary GCD 알고리즘도 있습니다!




References

[wiki] 유클리드 호제법