알아야할 표현 최대공약수 = GCD = Greatest Common DivisorGCD(A, B) = A와 B의 최대공약수 유클리드 호제법 두 양수 A, B(A > B)에 대하여 A = BQ + R (0 ≤ 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 증명 나머지는 나눠지는 수가 나누는 수보다 작아질 때까지 빼는 것과 같다. 다르게 말하..