[대수학 - 정수론] 유클리드 호제법에 대하여

유클리드 호제법이란?

---

유클리드 호제법(Euclidean Algorithm)은 유클리드 알고리즘이라고도 불리며,

 

2개의 자연수(다항식)의 최대공약수를 구하는 방법이다.

 

유클리드 호제법의 정리를 보면

 

a와 b가 자연수이고, a를 b로 나눈 나머지를 r이라고 하자.

(단, a ≥ b, 0 ≤ r < b)

 

a와 b의 최대공약수를 (a, b)라고 하면,

 

(a, b) = (b, r)이 성립한다.

---

이해

---

일단 최대 공약수에 대한 이해가 필요하다.

 

최대 공약수라 함은 두 수를 모두 나누어 떨어지게 하는 수 중 가장 큰 수를 의미한다.

(공약수 중 가장 큰 수)

 

ex.

 

108 = 2 × 2 × 3 × 3 × 3

 

72 = 2 × 2 × 2 × 3 × 3

 

공통되는 부분을 골라내면

 

2 × 2 × 3 × 3이 된다.

 

즉 36이 최대 공약수가 되는 것이다.

 

이렇게 최대 공약수를 구하는 방법을 알고리즘화 한 게 유클리드 호제법이다.

 

위에 미리 언급한 정리를 예시를 이용하여 최대한 풀어서 설명해보자면

 

108 = 2 × 2 × 3 × 3 × 3에서 

 

72 = 2 × 2 × 2 × 3 × 3을 뺀다.

 

36 = 1(2 × 2 × 3 × 3)

(공통부분이 더 이상 뺄 수 없을 때까지)

-

 

72 = 2(2 × 2 × 3 × 3)에서

 

36 = 2 × 2 × 3 × 3을 뺀다.

 

36 = 2 × 2 × 3 × 3

 

-

 

36 = 2 × 2 × 3 × 3에서

 

36 = 2 × 2 × 3 × 3을 뺀다

 

0

 

대충 이런 식으로 전개됨을 알 수 있는데

 

두 수가 2 × 2 × 3 × 3 부분만 남을 때까지 위와 같은 방법을 반복하는 거다.

 

추가 예시

1071 = 3 × 3 × 7 × 17

 

1029 = 3 × 7 × 7 × 7

 

↓

 

1071 = 51(3 × 7)

 

1029 = 49 (3 × 7)

 

42 = 2(3 × 7)

_

 

1029 = 49 (3 × 7)

 

42 = 2(3 × 7)

 

21 = 1(3 × 7)

 

_

 

42 = 2(3 × 7)

 

21 = 1(3 × 7)

 

21 = 1(3 × 7)

 

_

 

21 = 1(3 × 7)

 

21 = 1(3 × 7)

 

0

 

 

이렇게 서로소의 곱 중 서로 겹치지 않는 수를 모두 제거해준다고 생각하면 된다.

 

추가로 이를 이용해 최소공배수를 구할 수 있는데

 

최소 공배수는 두 수를 서로소로 쪼갰을 때,

 

중복되지 않는 소인수와 서로 같은 소인수가 있다면 차수가 큰 소인수를 모은

 

수의 집합을 모두 곱해주면 된다.

 

최대 공약수를 서로소로 쪼개 보면

 

두 수의 서로소 중 중복되는 서로소의 차수가 작은 것들을 모두 가지고 있다.

 

즉 두 수의 곱에서 최대 공약수를 나눠주면 최소 공배수를 얻을 수 있다.

---

코드

---

import java.util.Scanner;

class Main{
    
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
		
		int num1,
			num2 = 0,
			multiply,
			store;
		
		num1 = sc.nextInt();
		
		multiply = sc.nextInt();
		
		if(num1 < multiply) {
			
			num2 = num1;
			num1 = multiply;
			
		}else {
			
			num2 = multiply;
			
		}
		
		multiply = num1 * num2;
		
		while(num2 != 0) {
			
			store = num2;
			num2 = num1 % num2;
			num1 = store;
			
		}
		
		System.out.println(num1);
		System.out.println(multiply / num1);
        
    }
    
}

이건 내가 작성한 코드인데

 

if(num1 < multiply) {
			
	num2 = num1;
	num1 = multiply;
		
}else {
		
	num2 = multiply;
		
}

 

사실 이 부분은 필요 없다.

 

while(num2 != 0) {
			
	store = num2;
	num2 = num1 % num2;
	num1 = store;
			
}

 

num1이 num2보다 작더라도 나머지 구하는 부분에서 뒤 바뀐다.

 

---

public static int gcd(int a, int b){

	if(b == 0) return a;
    return gcd(b, a % b);
    
}

 

재귀(점화식)를 이용한 방법

---

public static void main(String[] args){

	Scanner sc = new Scanner(System.in);
		
	int num1 = sc.nextInt(),
    	num2 = sc.nextInt(),
        calc1 = num1,
        calc2 = num1;
    
	while(true) {
    
		if(calc1 > calc2) calc1 -= calc2;
        
		else if(calc1 < calc2) calc2 -= calc1;
        
		else break;
        
	}
    
	System.out.print(calc1 + "\n" + num1 * (num2 / calc1) );
    
}

 

mod 연산을 minus 연산으로 처리한 것

---

뒤에 두 방법은 기존의 내 코드를

 

다른 방식으로 재해석한 코드인데

 

왠지 모르게 매료된다...