[CS] 유클리드 호제법 (JAVA)

유클리드 호제법

두 개의 자연수가 주어졌을 때, 두 수의 최대공약수를 구하는 알고리즘의 하나이다.

두 자연수 a, b (a > b) 에 대해서 a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수가 된다.

gcd(a, b) = gcd(b, r)
gcd(a, b, c) = gcd(gcd(a, b), c)

a = 36, b = 28

36 % 28 = 8
gcd(36, 28) = gcd(28, 8)

28 % 8 = 4
gcd(28, 8) = gcd(8, 4)

8 % 4 = 0
gcd(8, 4) = gcd(4, 0)

따라서, 36과 28의 최대공약수는 4가 된다.

 

코드로 구현

// 반복문 사용
int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    
    return a;
}


// 재귀함수 사용
int gcd(int a, int b) {
    if (a % b == 0) {
        return b;
    }
    
    return gcd(b, a % b);
}

 

베주 항등식

두 정수와 그 최대공약수 사이의 관계를 보여주는 항등식인데 다음 세 명제가 성립한다.
1. ax + by = gcd(a, b) 를 만족하는 정수 x, y가 반드시 존재한다.
2. gcd(a,b) 는 정수 x, y에 대하여 ax + by 형태로 표현할 수 있는 가장 작은 자연수이다.
3. 정수 x, y에 대하여 ax + by 형태로 표현되는 모든 정수는 gcd(a, b) 의 배수이다.

정수 a, b의 최대공약수를 gcd(a, b) 로 나타낼 때, 확장 유클리드 호제법을 이용하여 ax + by = gcd(a, b) 의 해가 되는 정수 x, y 짝을 찾아낼 수 있다.

a와 b가 서로소(gcd(a, b) = 1)인 경우, ax + by = 1 이 되어 a는 모듈로 연산의 곱의 역원이 된다.

\( a\cdot x\equiv 1 \pmod{b} \) 를 만족시키는 x를 찾을 수 있다는 의미이다.

 

확장 유클리드 호제법

베주 항등식에서 a, b의 최대공약수와 ax + by = gcd(a, b)를 만족하는 x, y를 구하는 알고리즘이다.

67x + 61y = 12 

67s + 61t = r

s	t	r	q
1	0	67
0	1	61
1 - 0 x 1 = 1	0 - 1 x 1 = -1	67 - 61 x 1 = 6	1
0 - 1 x 10 = - 10	1 - (-1) x 10 = 11	61 - 6 x 10 = 1	10

67s + 61t = 1 일 때에는 x = -10, y = 11 이다.

따라서, 67s + 61t = 12 일 때에는 x = -120, y = 132 이다.