알아야할 표현
최대공약수 = 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)
