정수론 5장 - 유클리드 호제법을 파헤쳐보자!

이상준교수님의 유튜브영상을 참조하였습니다

오늘은 유클리드 호제법에 대해서 알아볼거다

 

우선 유클리드 호제법에 대해 설명을 하기 전에, 기본적인 나눗셈에 대한 기호를 설명하겠다

정수 n과 0이 아닌 정수 m에 대하여

적당한 정수 k가 n = mk 를 만족시키면 

1. m이 n을 나눈다
2. m은 n의 약수이다
3. n은 m의 배수이다.

이고, m ∣ n이라고 쓴다

 

주의 :: 0은 약수가 될수 없지만, 모든 수의 배수가 될수 있다. ∵ n x 0 = 0

 

유클리드 호제법

 

최대공약수를 영어로는 greatest common divisor, 축약형으로 gcd(a, b)를 a와 b의 최대공약수로 나타낸다.

유클리드 호제법은

 

gcd(a, b) = gcd(b, a mod b)라는 점을 이용해서, 나머지가 0이 나올때까지 반복 수행해주는 것이다.

 

설명

 

문자 모양새는 다음과 같다

gcd(a, b)

gcd(b, r1) (a = q1*b + r1)

gcd(r1, r2) (r1 = q2* r2 + r3)

gcd(r2, r3)

...

gcd(rn-1, rn)

gcd(rn, 0) 일때 rn값이 gcd(a, b)값이라는 것이다.

 

아직 내말이 뭔소리인지 못알아들으셨다면 

의사코드로 설명해보겠다

 

gcd(a, b)

   b가 0이라면 a를 반환해라

   b가 0이 아니라면 gcd(b, a%b)를 반환해라

 

실제로 적용해서 써보면, 

gcd(1729, 2743)을 구해보자

 

gcd(2743, 1729)

 = gcd(1729, 1014)

 = gcd(1014, 715)

 = gcd(715, 299)

 = gcd(299, 117)

 = gcd(117, 65)

 = gcd(65, 52)

 = gcd(52, 13)

 = gcd(13, 0)

 

13으로 알고리즘 종료, 실제로 소인수분해해서 확인해보면

1729 = 13 * 133

2743 = 13*211 인것을 알수 있다

 

그럼 이게 도대체 왜 같은 것일까?

 

증명

 

핵심은 gcd(a, b) = gcd(b, a mod b)라는 점에 있다.

 

a mod b = r로 두면, a = qb + r이다 (0<=r <b)

 

gcd(a, b) = g1, gcd(b, r) = g2로 두면

 

a = g1 * A

b = g1 * B

 

r = a-qb

r = g1 * A - q*B*g1

r = g1( A - qB)

그러므로 g2의 공약수 중 g1이 포함되므로, g2 >= g1이다

 

반대로 이번에는

b = g2 * k

r = g2 * l 로 둔다면

a = qb + r이므로 대입해주면

 

a = q * k *g2 + g2*l

a = g2(qk + l) 이다

 

그럼 g1 의 공약수중 g2가 있으므로 g1 >= g2가 되는데, 위에꺼와 합치면

g1 = g2가 된다

 

그러므로 증명은 되었다.

 

종료조건

그러면, 이게 항상 무조건 끝날까?

 

답은 그렇다 이다.

 

왜냐하면, 

 

gcd(a, b)

gcd(b, r1) (a = q1*b + r1)

gcd(r1, r2) (r1 = q2* r2 + r3)

gcd(r2, r3)

...

gcd(rn-1, rn)

gcd(rn, 0) 

 

이러한 모양새일때, ri= qi+1*ri+1 + ri+2이므로

 

a> b > r1> r2이므로 감소하는 수열이다

 

a, b가 양수일때는 무조건 0이 나오므로 종료됨을 알수 있다.

 

시간복잡도//연산횟수

알고리즘에 있어서 연산횟수는 적어야 한다. 무조건. 

 

그러므로 이 알고리즘의 연산횟수를 알아내는 것은 이 알고리즘의 효율성을 나타내는데 도움이 된다

 

알아보자.

정확하게 구해야 되는거 아니라면, 2이상의 수로 계속 나눈것의 나머지가 나올테니, loga n이런식으로 나올것을 예상할수 있다.

 

정확하게 구하기 - 

 

나눗셈의 성질을 잘 생각해보면

 

ri+2< ri2인것을 증명할수 있다

 

ri= qi+1*ri+1 + ri+2이니까

 

이게 성립한다

 

ii) ri+1 <= ri2일때는 ri+2< ri+1이므로 성립한다

 

ri+2< ri2이게 증명되었으니 시간복잡도는 금방 구한다.

 

gcd(a, b)

gcd(b, r1) (a = q1*b + r1)

gcd(r1, r2) (r1 = q2* r2 + r3)

gcd(r2, r3)

...

gcd(rn-1, rn)

gcd(rn, 0 =rn+1) 이니까

 

rn+1 = 0 이 나올때까지 굴리면 된다.

 

 

위 그림을 보면

r2k< b2k이다.

 

r2k<0 일때 종료조건이 성립하니까

 

r2k< b2k<= 1 을 만족시키는 최소의 k값이 연산횟수일것이다.(왜냐하면 저 조건 만족시키자마자 바로 끝나기 때문)

 

b2k<= 1

 

b <= 2k

 

로그를 씌워주면

 

log2b< = k가 된다

 

그러면 k가 최소여야 하니

 

log2b= k 일것이다.

 

연산횟수는 k가 아닌 2k이므로 연산횟수는 2log2b일것이다.

물론 이것보다 빨리 끝날수도 있고, 대부분이 그러할 것이다.

 

위는 최대 연산횟수이기 때문이다.

 

시간복잡도는 O(log2b)이다. (상수계수 생략)