Util Monster
유클리드 호제법 & 소인수분해
최대공약수(Greatest Common Factor 또는 Greatest Common Divisor, GCD)는 두 개 이상의 정수가 공통으로 가지는 약수 중 가장 큰 수입니다. 예를 들어 12와 18의 약수는 각각 {1,2,3,4,6,12}와 {1,2,3,6,9,18}이며, 공통 약수는 {1,2,3,6}이고 최대공약수는 6입니다.
유클리드 호제법은 기원전 300년경 유클리드가 발견한 최대공약수를 구하는 효율적인 알고리즘입니다. a를 b로 나눈 나머지를 r이라 할 때, GCD(a,b) = GCD(b,r)이 성립합니다. 나머지가 0이 될 때까지 이 과정을 반복하면 마지막 나누는 수가 최대공약수가 됩니다.
각 수를 소인수분해한 후 공통된 소인수들의 최소 지수를 곱하면 최대공약수를 구할 수 있습니다. 예: 72 = 2³×3², 48 = 2⁴×3¹이면 GCF = 2³×3¹ = 24입니다.
• 분수의 약분: 분자와 분모를 최대공약수로 나눔
• 비율 단순화: 두 수의 비를 가장 간단한 형태로 표현
• 타일링 문제: 직사각형을 정사각형 타일로 채우기
• 기어 설계: 톱니바퀴의 최소 톱니 수 계산
• 주기 계산: 두 사건이 동시에 발생하는 주기
최대공약수(Greatest Common Factor, GCF 또는 Greatest Common Divisor, GCD)는 두 개 이상의 정수를 모두 나누어떨어지게 하는 수(공약수) 중에서 가장 큰 수입니다. 수학에서 매우 중요한 개념으로, 분수의 약분, 비율 계산, 패턴 분석 등 다양한 분야에서 활용됩니다. 예를 들어 12와 18을 생각해보면, 12의 약수는 1, 2, 3, 4, 6, 12이고 18의 약수는 1, 2, 3, 6, 9, 18입니다. 이 중 공통으로 나타나는 약수는 1, 2, 3, 6이며, 가장 큰 공약수인 6이 바로 12와 18의 최대공약수입니다. 최대공약수가 1인 두 수를 "서로소(coprime 또는 relatively prime)"라고 하며, 이는 1 이외에 공통 약수가 없다는 의미입니다.
유클리드 호제법(Euclidean Algorithm)은 기원전 300년경 그리스 수학자 유클리드가 저서 "원론(Elements)"에서 소개한 알고리즘으로, 2000년 넘게 사용되고 있는 가장 오래된 알고리즘 중 하나입니다. 이 방법은 큰 수의 최대공약수도 매우 빠르게 계산할 수 있는 장점이 있습니다. 원리는 간단합니다: 두 수 a, b (a > b)가 있을 때, a를 b로 나눈 나머지를 r이라 하면 GCD(a, b) = GCD(b, r)입니다. 이 과정을 나머지가 0이 될 때까지 반복하면, 마지막으로 나누는 수가 최대공약수가 됩니다. 예를 들어 GCD(1071, 462)를 구하면: 1071 = 462 × 2 + 147 → GCD(462, 147) / 462 = 147 × 3 + 21 → GCD(147, 21) / 147 = 21 × 7 + 0 → GCD(21, 0) = 21. 따라서 최대공약수는 21입니다. 이 방법의 시간 복잡도는 O(log min(a,b))로 매우 효율적입니다.
소인수분해는 어떤 수를 소수(prime number)들의 곱으로 나타내는 것입니다. 이 방법을 사용하면 최대공약수를 체계적으로 구할 수 있습니다. 방법은 다음과 같습니다: ① 각 수를 완전히 소인수분해합니다. ② 공통으로 나타나는 소인수를 찾습니다. ③ 각 공통 소인수의 지수 중 작은 값을 선택합니다. ④ 선택한 소인수들을 모두 곱합니다. 예를 들어 72와 48의 최대공약수를 구하면: 72 = 2³ × 3² = 8 × 9 / 48 = 2⁴ × 3¹ = 16 × 3. 공통 소인수는 2와 3이며, 2의 지수는 min(3, 4) = 3, 3의 지수는 min(2, 1) = 1입니다. 따라서 GCF = 2³ × 3¹ = 8 × 3 = 24입니다. 이 방법은 세 개 이상의 수의 최대공약수를 구할 때 특히 유용하며, 각 수의 구조를 명확하게 이해할 수 있는 장점이 있습니다.
최대공약수(GCF)와 최소공배수(LCM)는 밀접한 관계가 있습니다. 두 자연수 a, b에 대해 다음 공식이 성립합니다: a × b = GCF(a, b) × LCM(a, b). 이 공식을 이용하면 최대공약수를 알 때 최소공배수를 쉽게 구할 수 있습니다: LCM(a, b) = (a × b) / GCF(a, b). 예를 들어 12와 18의 경우: GCF(12, 18) = 6 / LCM(12, 18) = (12 × 18) / 6 = 216 / 6 = 36. 반대로 최소공배수를 알 때 최대공약수를 구할 수도 있습니다. 소인수분해로 이해하면 더 명확합니다: 최대공약수는 공통 소인수의 최소 지수를 사용하고, 최소공배수는 모든 소인수의 최대 지수를 사용합니다. 12 = 2² × 3¹, 18 = 2¹ × 3²일 때, GCF = 2¹ × 3¹ = 6 (최소 지수), LCM = 2² × 3² = 36 (최대 지수)입니다.
최대공약수는 일상생활의 다양한 문제를 해결하는 데 활용됩니다. 1) 타일링 문제: 24cm × 36cm 직사각형 바닥을 정사각형 타일로 빈틈없이 채우려면 타일 한 변의 길이는 GCF(24, 36) = 12cm가 되어야 합니다. 2) 분수 약분: 18/24를 기약분수로 만들려면 분자와 분모를 GCF(18, 24) = 6으로 나누어 3/4로 약분합니다. 3) 비율 단순화: 48:72의 비를 간단히 하려면 GCF(48, 72) = 24로 나누어 2:3으로 표현합니다. 4) 포장 문제: 사과 36개와 오렌지 48개를 같은 개수씩 나누어 선물 세트를 만들 때, 최대 GCF(36, 48) = 12세트를 만들 수 있으며, 각 세트는 사과 3개, 오렌지 4개로 구성됩니다. 5) 주기 계산: A 행성은 12년, B 행성은 18년 주기로 공전한다면, 두 행성이 같은 위치에서 만나는 주기는 LCM(12, 18) = 36년이지만, 공통 약수인 GCF(12, 18) = 6년마다 일정한 패턴이 반복됩니다. 6) 기어 설계: 톱니가 24개인 기어와 36개인 기어가 맞물릴 때, GCF(24, 36) = 12개씩 구간으로 나누어 설계하면 정확한 맞물림을 보장할 수 있습니다.
프로그래밍에서 최대공약수는 다양한 알고리즘과 암호화 기법에 활용됩니다. 재귀 함수를 이용한 유클리드 호제법 구현: function gcd(a, b) { return b === 0 ? a : gcd(b, a % b); } 이 간단한 함수는 매우 효율적으로 최대공약수를 계산합니다. RSA 암호화: 공개키 암호화 시스템인 RSA는 최대공약수가 1인 두 수(서로소)를 찾는 과정이 핵심입니다. 두 소수 p, q를 선택하고, (p-1)(q-1)과 서로소인 공개지수 e를 선택합니다. 화면 해상도 비율: 1920×1080 해상도의 비율을 구하면 GCF(1920, 1080) = 120으로 나누어 16:9가 됩니다. 분수 연산 최적화: 컴퓨터에서 분수를 다룰 때, 분자와 분모를 항상 최대공약수로 나누어 기약분수 형태로 유지하면 오버플로우를 방지하고 계산 효율을 높일 수 있습니다. 유리수 판별: 순환소수를 분수로 변환한 후 약분할 때 최대공약수를 사용합니다. 게임 개발: 타일 맵 에디터에서 그리드 크기를 결정하거나, 캐릭터 이동 속도를 동기화할 때 최대공약수를 활용하여 최적의 기본 단위를 찾습니다.