유클리드 호제법 - 최대공약수 구하기(+ 최소공배수)

알아야할 표현

 

최대공약수 = GCD = Greatest Common Divisor

GCD(A, B) = A와 B의 최대공약수

 

유클리드 호제법

 

두 양수 A, B(A > B)에 대하여 A = BQ + R (0 ≤ R < B) 이라 하면, A, B의 최대공약수는 B, R의 최대공약수와 같다.

즉, GCD(A, B) = GCD(B, R)

R = 0이라면 A, B의 최대공약수는 B가 된다.

(출처 - 유클리드 호제법 나무위키)

 

정리

 

A와 B의 GCD는 B와 (A를 B로 나눈 나머지)의 GCD와 같다.

GCD(A, B) = GCD(B, A%B)

 

예시

 

ex) 270, 192의 최대공약수

GCD(270, 192) = GCD(192, 78) = GCD(78, 36) = GCD(36, 6) = GCD(6, 0) = 6

 

증명

 

나머지는 나눠지는 수가 나누는 수보다 작아질 때까지 빼는 것과 같다. 다르게 말하면

R = A - BQ

즉, 나머지는 B를 Q번 뺀 결과다.

A, B가 양수이고 A > B 일 때, GCD(A, B) = GCD(B, A-B)를 증명하면 위의 명제도 증명이 가능하다.

GCD(A, B) = GCD(B, A-B) = GCD(B, A-B-B) = GCD(B, A-B-B-B- ... -B) = GCD(B, A%B)

 

A = B + C 라 하자 (A, B, C는 양수)

 

C = A - B

A는 A와 B의 최대공약수의 배수 -> A = X × GCD(A, B)

B는 A와 B의 최대공약수의 배수 -> B = Y × GCD(A, B)

C = (X-Y) × GCD(A, B) -> GCD(A, B)는 C의 약수

-> GCD(A, B) 는 B와 C의 공약수인 것을 알 수 있다.

공약수 ≤ 최대공약수 이기때문에

GCD(A, B) ≤ GCD(B, C) --- 1번

 

A = B + C

B = M × GCD(B, C)

C = N × GCD(B, C)

A = (M+N) × GCD(B, C) - > GCD(B, C)는 A의 약수

-> GCD(B, C)는 A와 B의 공약수인 것을 알 수 있다.

공약수 ≤ 최대공약수 이기때문에

GCD(B, C) ≤ GCD(A, B) --- 2번

 

GCD(A, B) ≤ GCD(B, C) --- 1번

GCD(B, C) ≤ GCD(A, B) --- 2번

-> GCD(A, B) = GCD(B, C)

 

∴ GCD(A, B) = GCD(B, A - B)

 

∴ GCD(A, B) = GCD(B, A%B)

 

번외) 최소공배수

 

최소공배수 = LCM = Least Common Multiple

LCM(A, B) = A와 B의 최소공배수

 

최소공배수는 A와 B의 소인수분해에서 각 소인수의 지수 중 더 큰 쪽을 취해 곱한 값이다.
(= A와 B의 소인수분해에서 공통되지 않은 소인수들의 곱 × 공통된 소인수)

 

A = a1 × a2 × a3 × ... × GCD(A, B) (A를 소인수분해) (a1 × a2 × a3 × ... 는 공통된 부분 제외)

B = b1 × b2 × b3 × ... × GCD(A, B) (B를 소인수분해) (b1 × b2 × b3 × ... 는 공통된 부분 제외)
GCD(A, B)는 A와 B의 공통된 소인수들의 곱

LCM(A, B) = a1 × a2 × a3 ... x b1 × b2 × b3 × GCD(A, B)

 

∴ LCM(A, B) = (A x B) / GCD(A, B)