계산 방법
최대공약수(GCD)는 두 수를 모두 나누는 가장 큰 수, 최소공배수(LCM)는 두 수의 공통 배수 중 가장 작은 수입니다.
유클리드 호제법: gcd(a, b) = gcd(b, a mod b)
lcm(a, b) = a × b ÷ gcd(a, b)
유클리드 호제법 예시
gcd(48, 18) → gcd(18, 48 mod 18 = 12) → gcd(12, 6) → gcd(6, 0) = 6
이 방법은 기원전 300년경 유클리드의 원론에 나온 알고리즘으로, 지금도 컴퓨터 연산에 그대로 쓰입니다.
자주 묻는 질문
최소공배수는 어디에 쓰나요?
분수의 통분, 주기가 다른 두 사건이 언제 다시 겹치는지(예: 3일마다 오는 버스와 5일마다 오는 버스), 톱니바퀴가 다시 맞물리는 시점 계산 등에 씁니다.
최대공약수는 어디에 쓰나요?
분수의 약분, 직사각형을 정사각형으로 남김없이 자를 때의 최대 크기, 물건을 여러 그룹에 똑같이 나눌 때의 최대 그룹 수 등입니다.
세 개 이상은 어떻게 구하나요?
두 개씩 순차적으로 구하면 됩니다. gcd(a,b,c) = gcd(gcd(a,b), c)입니다.