[Java] 최대공약수, 최소공배수

본 글에서는

• 최대공약수, 최소공배수를 간단히 구하는 방법을 소개합니다.
• 최대공약수를 간단히 구하는 방법인 유클리드 호제법을 증명해봅니다.
• 최대공약수를 이용해 최소공배수를 간단히 구하는 방법을 소개합니다.

최대공약수(GCD) 간단히 구하기

유클리드 호제법을 사용하면 GCD를 간단히 구할 수 있습니다.

유클리드 호제법

두 수 A, B (A > B)에 대해 A를 B로 나눈 나머지를 R라고 하자.
A와 B의 최대공약수는 R와 B의 최대공약수와 같습니다.
이 과정을 나머지가 0이 될 때까지 반복하면 나누는 수가 A, B의 최대공약수이다.

무슨 말인지 잘 이해가 되지 않습니다. 예시를 통해 이해를 해 봅시다.

Q. 1071과 1029의 최대공약수를 구하시오

$i)$ 1071과 1029의 최대공약수는 42($=1071 \mod 1029$)와 1029의 최대공약수와 같다.
$ii)$ 42와 1029의 최대공약수는 21($=1029 \mod 42$)와 42의 최대공약수와 같다.
$iii)$ $42 \mod 21 = 0$ 이므로 나누는 수인 21이 1071과 1029의 최대공약수이다.

A. 1071과 1029의 최대공약수는 21

유클리드 호제법 증명

1. A와 B의 최대공약수를 G라고 가정

$A > B$인 두 수 $A$, $B$에 대해, $A$와 $B$의 최대공약수를 $G$라고 하면 $A = aG$, $B = bG$ $(a, b는 서로소)$ 로 나타낼 수 있다.

2. A를 B로 나눈 나머지(R) 또한 G로 나누어 떨어진다.

$A$를 $B$로 나눈 몫을 $Q$, 나머지를 $R$라고 하면 $A = BQ + R$로 나타낼 수 있다.
이를 $R$에 대한 식으로 나타내면 $R = A - BQ = aG - bGQ = G(a - bQ)$ 이므로 $R$ 또한 $G$로 나누어 떨어진다.

3. B와 R의 최대공약수도 G이다.
이 때, $R = rG$, 라고 하면 $r$과 $b$는 서로소이다.
왜냐?
만약 $r$과 $b$가 다른 공약수를 가지고 있다면 그 공약수를 $G'$라 했을 때, $R = r'G'G$, $B = b'G'G$ 라고 쓸 수 있다.
그러면 $A = b'G'GQ + r'G'G = G'G(b'Q + r')$ 이고, $A$와 $B$는 $G'G$를 최대공약수로 가진다는 결론이 나오므로 $A$와 $B$의 최대공약수가 $G$라는 가정에 모순된다.

따라서, $A$, $B$의 최대공약수인 $G$는 $B$와 $R$의 최대공약수와 동일하다.

Java 코드로 표현

두 정수를 입력받아 유클리드 호제법으로 최대공약수를 구하는 코드는 다음과 같습니다.

import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int A = sc.nextInt();
		int B = sc.nextInt();
	
		int a = A;
		int b = B;
		
		// 더 큰 수가 a가 되도록 한다.
		if (a < b) {
			int temp = a;
			a = b;
			b = temp;
		}
		
		// 유클리드 호제법 수행
		while (a % b != 0) {
			int temp = a % b;
			
            // a를 b로 나눈 나머지가 0일 될 때까지 반복
			a = b;
			b = temp;
		}
		
		int GCD = b;
        int LCM = A * B / GCD;
        
		System.out.printf("%d와 %d의 GCD는 %d 입니다.", A, B, GCD);
		System.out.printf("%d와 %d의 LCM은 %d 입니다.", A, B, LCM);
		
		sc.close();
	}
}

최소공배수(LCM) 간단히 구하기

최소공배수는 다음 사실을 이용하여 구할 수 있습니다.

$LCM · GCD = A · B$

즉, 두 수의 곱은 최소공배수와 최대공약수의 곱과 같습니다. 그 이유도 생각해보면 정말 간단합니다.

$A$와 $B$의 최대공약수를 $G$라고 하면 $A = aG$, $B = bG$ $(a, b는 서로소)$ 로 나타낼 수 있다.
$aG$와 $bG$의 공통 배수중 가장 작은 값은 $abG$이다. 따라서 $abG$는 $A$와 $B$의 최소공배수이다.
$∴ LCM · GCD = abG · G = abG^{2} = aG · bG = A · B$

그러므로 유클리드 호제법을 통해 최대공약수를 구하면, 자연스럽게 최소공배수도 간단히 구할 수 있는 상황이 됩니다.

Java 코드로 표현

import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int A = sc.nextInt();
		int B = sc.nextInt();
	
		int a = A;
		int b = B;
		
		// 더 큰 수가 a가 되도록 한다.
		if (a < b) {
			int temp = a;
			a = b;
			b = temp;
		}
		
		// 유클리드 호제법 수행
		while (a % b != 0) {
			int temp = a % b;
			
			a = b;
			b = temp;
		}
		
		int GCD = b;
		int LCM = A * B / GCD;
		
		System.out.println(GCD);
		System.out.println(LCM);
	}
}