Elementary Number Theory - 2.4 The Euclidean Algorithm

Elementary Number Theory - 2.4 The Euclidean Algorithm

유클리드 알고리즘 

이거 되게 어렵다. 이해하면 뭐든 쉽지만 그 전까지는 어려움. 이해 조금 가기 시작해서 이 포스트를 쓴다.

a = qb + r, then gcd(a,b) = gcd(b,r)

이거임.

a = qb + r 이므로

r = a - qb 이다.

근데 책이나 동영상 찾아보면 이 부분이 추상적으로 써있어서 도통 이해를 하기가 힘들었다.

d = gcd(a, b)라고 하면

a = d * k 로 표현 해볼 수 있고

b = d * l 로 표현 해볼 수 있다.

a와 b에 각각 d가 들어있기 때문이다.

그러면 r = a - qb 인데 r = dk - qdl 이므로 r = d( k - ql ) 로 표현 할 수 있다.

고로 d | a - qb 이고 a - qb = r 이므로 d | r 이다.

d = gcd(a, b)이고 a >= b > 0 인 경우

a = qb + r 에서 d | r을 나눈다는 것.

그럼 예제를 한번 풀어보자

Example 2.3

gcd(12378, 3054) 이걸 한번 구해보자.

a = 12378이고

b = 3054다.

12378 = q0 * 3054 + r0 로 놓아보자.

그럼 여기서 q는 f12눌러서 console 창을 띄워서 계산을 해보면

에 의해서 4가 나온다.

12378 = 4 * 3054 + 162

q0 = 4, r0 = 162 가 나온다.

여기서 gcd( 12378, 3054 ) = gcd( 3054, 162 )라는 얘기다.

그러면 3054 = q1 * 162 + r1 의 식을 얻을 수 있다.

gcd(3054, 162) = gcd(162, 138)

3054 = 4 * 162 + 138

q1 = 18, r1 = 138

q2 = 1, r2 = 24

계속 계산을 해보면

q3 = 5, r3 = 18

q4 = 1, r4 = 6

q5 = 3, r5 = 0

이다.

나머지 r이 0이 나온다는 것은 나누어 떨어진다는 말이다.

마지막으로 나온 나머지 r4가 gcd(a, b)와 같다.

r4는 6이므로 gcd(a, b) = 6 이다.

end.