[친절한 수론 길라잡이] 5장. 가약성과 최대공약수

 

인 정수 m과 n이 있다고 해보자.

만일 n이 m의 배수라면, n=mk를 만족한다면, 'm이 n을 나눈다'라고 한다.

 

만일 m이 n을 나누면 우리는 m|n이라고 쓴다.

 

n을 나누는 수를 n의 약수라고 부른다.

만일 우리가 두 개의 정수를 가지고 있다면, 우리는 이 두 정수를 모두 나누는 공약수(common divisor)를 찾을 수 있다.

모두 0은 아닌 두 수 a와 b의 최대공약수는 a와 b를 모두 나누는 수 중에서 가장 큰 수이다.

기호로는 gcd(a, b)로 표기한다. 만일 gcd(a, b) = 1일때, 우리는 'a와 b는 서로소이다'라고 한다.

 

최대공약수를 찾는 가장 효율적인 방법은 유클리드 호제법(Euclidian algorithm)이다.

이 방법은 나머지가 0이 되도록 나눗셈을 반복하는 것이다.

 

gcd(36, 132)를 계산해보자.

먼저 132를 36으로 나누면, 몫이 3, 나머지가 24가 된다. 132 = 36 * 3 + 24

다음으로, 36을 앞에서 얻은 24로 나눈다. 그러면 새로운 나머지 12를 얻는다. 36 = 24 * 1 + 12

24를 12로 나누면, 나머지가 0이 된다.

gcd(36, 132) = 12이다.

 

유클리드 호제법은, 나머지가 0이 되는 나눗셈을 하기 바로 전단계의 나머지로 최대공약수를 찾는 방법이다.

큰 수로 한번 해보자.

gcd(1160718174, 316258250) = 1078

1160718174 = 3 * 316258250 + 211943424

316258250 = 1 * 211943424 + 104314826

211943424 = 2 * 104314826 + 3313772

104314826 = 31 * 3313772 + 1587894

3313772 = 2 * 1587894 + 137984

1587894 = 11 * 137984 + 70070

137984 = 1 * 70070 + 67914

70070 = 1 * 67914 + 2156

67914 = 31 * 2156 + 1078

2156 = 2 * 1078 + 0

 

수 A를 B로나눈 몫 Q와 R이 있다고 해보자.

A =  Q * B + R이 된다.

 

유클리드 호제법

두 개의 수 a와 b의 최대공약수를 계산하려면, r_-1 = a, r_0 = b라 놓고, 다음의 목과 나머지 구하는 과정을 계속하여 나머지 r_{n+1}이 0이 될 때까지 구한다. 이때, 0이 아닌 마지막 나머지 r_n이 a와 b의 최대공약수이다.

유클리드 호제법에서, 나머지는 반드시 작아지기 때문에, 유한한 연산 횟수를 가진다.

 

 

 

유클리드 호제법 알고리즘 - 컴퓨터로

#include <stdio.h>

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

int main()
{
    printf("%d\n", gcd(132, 36));               // 12
    printf("%d\n", gcd(1160718174, 316258250)); // 1078
    printf("%d\n", gcd(98765, 43210));          // 5
    return 0;
}