유클리드 호제법 편집하기

'''유클리드 호제법'''(Euclidean algorithm)이란 주어진 두 수의 [[최대공약수]]를 구하는 [[알고리즘]]으로, 다음 성질에 기초한다: \[a=bq+r \quad\Longrightarrow\quad (a,b)=(b,r).\]

여기서 \((a,b)\)는 \(a\)와 \(b\)의 최대공약수를 뜻한다. 다시 말해, 두 수의 최대공약수는 두 수중 큰 수를 피제수로 하고 작은 수를 제수로 하여 구한 나머지와, 제수의 최대공약수와 같다는 것이다. 

== 증명 ==
\(a=bq+r\)이라고 하자. 만약 \((a,b)=d\)이고, \(a=md\), \(b=nd\)라고 두면, \(md=ndq+r\)이라고 할 수 있다. 즉, \(r=md−ndq=(m−nq)d\)가 되어 \(d\)는 \(r\)의 [[약수]]이다. 

이제 \(d=(b,r)\)임을 증명하자. \(d\)는 \(b\)와 \(r\)의 공약수이고 \(r\)은 \(a\)를 \(b=nd\)로 나눈 나머지였으므로, 어떤 [[자연수]] \(k<n\)가 존재하여 \((b,r)=kd\)이다. 

다시 쓰면, \(n=n′k\)를 만족하는 \(n′\)에 의해 \(b=n′kd\)이고, 적절한 자연수 \(t\)에 의해 \(r=(m−nq)d=tkd\)이다. 이것을 처음 식에 넣으면 다음을 얻는다. \[a=n′kdq+tkd=(n′q+t)kd.\] 즉, \(a\)또한 \(kd\)의 배수가 되므로, \((a,b)=d\)이라는 가정에 의해 \(k=1\)이다. 그러므로 \((b,r)=d\)이다. 

== 유클리드 호제법의 사용 ==
예를 들어, 252와 198의 최대공약수를 구해보자. \[\begin{eqnarray*} (252,198) &=& (198,54) & \leftarrow 252=198⋅1+54. \\
&=& (54,36) & \leftarrow 198=54⋅3+36. \\
&=& (36,18) & \leftarrow 54=36⋅1+18. \\
&=& (18,0) & \leftarrow 36=18⋅2+0. \\
&=& 18. & \end{eqnarray*}\] 위처럼 두 수중 큰 수를 작은 수로 나눈 것의 나머지를 반복적으로 구하는 것으로 두 수의 최대공약수를 쉽게 구할 수 있다. 

== 프로그래밍 코드 ==
=== 프롤로그(Prolog) 코드 ===
다음은 [[프롤로그]]로 표현한 유클리드 호제법이다.

<font face="Fixedsys">gcd(X,0,R) :- R is X, !.<br/>
gcd(X,Y,Rr) :- R is X mod Y, gcd(Y,R,Rr).</font>

위 코드를 컨설트하고 '''gcd('수', '수', R).'''을 명령하면 '''R'''에 두 수의 최대공약수를 출력해준다. 단, 앞쪽에 있는 수가 더 커야한다. 

== 같이 보기 ==
* [[유클리드]](Euclid) 
* [[나눗셈]]

[[분류:수학]]
[[분류:수론]]