gcd(최대공약수)

• 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)