gcd(a, b)는 a와 b의 약수이다.두 수 또는 다항식의 곱은 두 수의 최대공약수와 최소공배수의 곱과 같다gcd(a, b) · lcm(a, b) = a·b public static int gcd(int a, int b) { if (b==0) return a; return gcd(b, a%b);} 위 공식에 의해서 최대공약수(gcd)를 구하고, 다음과 같이 최소공배수lcm을 구한다. 두 수의 최소공배수 L = lcm(a, b)은 L= lcm(a, b)= a * b / gcd(a, b)