유클리드 호제법

누리위키, 온 누리의 백과사전
ProtArie (토론 | 기여)님의 2013년 9월 24일 (화) 19:07 판 (새 문서: '''유클리드 호제법'''(Euclidean algorithm)이란 주어진 두 수의 최대공약수를 구하는 알고리즘으로, 다음 성질에 기초한다: \[a=bq+r \quad\Lon...)
(차이) ← 이전 판 | 최신판 (차이) | 다음 판 → (차이)

유클리드 호제법(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) 코드[편집]

다음은 프롤로그로 표현한 유클리드 호제법이다.

gcd(X,0,R) :- R is X, !.
gcd(X,Y,Rr) :- R is X mod Y, gcd(Y,R,Rr).

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

같이 보기[편집]