최대공약수(GCD) & 최소공배수(LCM)

GCD (Greatest Common Divisor)

최대공약수

최대공약수는 두수의 공통된 약수 중 최대 값을 찾는 것이다. 처음으로 생각하는 것은 공통된 약수를 찾는 것인데, 잠시 초등학교로 돌아가면, 2 나 3으로 계속 나누는 방식일 것이다. 하지만 유클리드 호제법을 사용하면 쉽게 코드로 나타낼 수 있다.

유클리드 호제법이란?

2개의 자연수 A, B (A ≥ B)가 있을 때 두수를 나눈 나머지가 R이라고 할때 이 값이 A,B 에 대한 GCD와 같으면 B가 최대공약수 라는 공식이다. 여기 까지 들으면 감이 안올 텐데 증명을 통해서 확인해보자.

증명

a, b가 서로소일때, G는 최대공약수이다. A가 B보다 크기 때문에 A=B*q+R 라고 할 수 있다.

1. A와 B를 정의한다.

    A = Ga
    B = Gb
   

2. A>=B 이기 때문에…

    A = B*q+R
   

3. R을 이항한다.

    R = A - B*q
   

4. 각각 1)의 값을 대입하고 비교하면 a, b가 서로 서로소라면 G가 A, B의 최대공약수가 될 수 있다는 것과 같이, R 과 B 역시 (a - b*q), b 가 서로소라면 R과 B의 최대 공약수도 G이라는 것을 알 수 있다.

       
    R = G(a - b*q)
       
    A = Ga
    B = Gb
    R = G(a - b*q)
       
   

a-b*q 와 b는 서로소인가?

'a-b*q 와 b는 서로소가 아니다' 라고 가정하고 증명을 진행하자.
아래와 같이 두수의 공약수가 있을 것이다.

a-b*q = gk
b = gk'

대입하고... 이항하면
a-gk'*q = gk
a = g(k+k'*q)

a와 b를 비교하자. 
이 식이 나오기 까지 a, b가 서로소 라는 가정으로 전개하였기 때문에 두수 역시 서로소이여야 한다.

b = gk'
a = g(k+k'*q) 

g!=1 일때 공통된 g 라는 수가 있기 때문에 a와 b는 서로소가 아니게 된다.
그렇기 때문에 두수가 서로소가 아니다 라는 명제가 잘못된 것으로...

결론은 'a-b*q 와 b는 서로소이다' 가 되는 것이다.

위와 같은 식에 따라서 A%B = R 과 B에 대한 최대공약수는 A, B에 대한 최대 공약수와 같다. 간단히 나타내면 GCD(A, B) == GCD(B, R) 이다.

위 식 GCD(A, B) == GCD(B, R) 에서 R은 A%B 이기 때문에 이를 코드로 나타내면 아래와 같다. int b가 0이면, A%B == 0 으로 B가 최대 공약수라는 것을 알 수 있다. B는 여기서 이전 스텝의 a%b이거나 그냥 0일 수 있다.

public static int gcd(int a, int b){
	if(b==0){
		return a;
	}
	else {
		return gcd(b, a%b);
	}
}

---

LCM (Least Common Denominator)

최소공배수

최소공배수는 두수에 임의의 값을 곱해서 얻을 수 있는 배수 중 최솟값을 의미한다. 최대공약수를 구했다면, 두수의 곱을 최대 공약수로 나눔으로 구할 수 있다. 최대 공약수에서 a, b는 서로소이기 때문에 Gab 가 가장 작은 배수가 된다.

A = Ga
B = Gb

공배수에 최대 공약수인 G가 중복되기 때문에 G를 하나 없애면 최소가 된다.
A * B = Ga * Gb

최소 공배수 = G*a*b = A*B/G

이를 코드로 나타내면 다음과 같다.

public static int lcm(int a, int b) {
	return a*b/gcd(a,b);
}