04. 최대공약수, 최소공배수

최대 공약수(GCD: Greatest Common Divisor)

두 정수의 공약수중에서 가장 큰 수를 최대공약수라고 하고, 두 정수 m,n에 대한 최대공약수를 gcd(m,n)이라고 표현한다.

최대공약수는 암호학에서 꽤 사용되는 분야이다. 주로, 어떤 수 m,n이 있을 때, 이 두 수가 서로 소인지(공통된 약수가 있는지 없는지)를 판단할 때 사용된다. 두 수가 서로 소가 되려면, 두 수에 대한 최대공약수가 1이되면 된다.

 

위의 gcd(m,n)=1이면 두 수는 서로소라는 성질을 포함해서 아래와 같은 최대공약수에 관련된 몇 가지 성질을 알아둘 필요가 있다.

• d | gcd(m,n)의 필요충분조건은 d | m 이고 d | n이다.
  이 말은 최대공약수의 약수는, 두 수의 공약수라는 말이다.(중학교때 배웠던^^)
  예를 들어 12와 18 이라는 수가 있을 때, 12의 약수는 1,2,3,4,6,12 이고, 18의 약수는 1,2,3,6,9,18이다. 따라서, 공약수는 1,2,3,6이고, 최대공약수는 6이다.
  이것을 위의 성질로 설명해보면, gcd(12,18)=6이고, 6의 약수는 1,2,3,6으로 위에서 계산한 공약수인 1,2,3,6과 일치한다.
  따라서, 두 수의 공약수를 구할 때는, 먼저 최대공약수를 구하고 그 최대공약수의 약수를 알아내면 되는 것이다.
• gcd(m,n)=1이면 두 수 m과 n은 서로소이다.(1 이외의 공약수가 존재하지 않는다.)
  바로 앞의 성질에서 본 바와 같이, 두 수의 공약수는 최대공약수의 약수인데, 이 최대공약수가 1이라면 1의 약수는 1 밖에 없으므로, 결국 두 수는 1 이외에는 공약수가 없는, 서로 소인 관계가 되는 것이다. '서로 소'라는 것을 영어로는 'Relatively Prime'이라고 한다.
• gcd(0,n) = n 이다.
  0은 모든 수로 나누어 떨어지고(0의 약수는 모든 수), n의 약수 중 가장 큰 수는 n이기에, 0과 n의 최대공약수는 n  

 

m = nq + r 이면, gcm(m,n) = gcd(n,r) 이다.

좀 낯설어 보이는 표현이지만 잘 알아두어야할 식이다. 컴퓨터 프로그래밍으로 최대공약수를 구해야 할 때 가장 많이 쓰이는 알고리즘이 '유클리드 호제법'인데, 이 방법의 기본바탕의 되는 원리가 이 것이기 때문이다.

예를 들어보면, 108과 72의 최대공약수를 구한다고 할 때, 먼저 108 = 72q + r의 형태로 만들면 108 = 72·1 + 36 이 되고, 이는 위 식 gcd(m,n)=gcd(n,r)에 따라 gcd(108,72) = gcd(72,36)이 된다. 즉, 제법 큰 수인 108과 72보다 작은 72와 36의 최대공약수를 찾는 '쉬운 방법'으로 변환된 것이다. gcd(72,36)은 암산으로도 바로 36이라는 것을 알 수 있다(36의 두 배가 72이므로). 즉, gcd(108,72)=gcd(72,36)=36

증명은 다음과 같다. 

d = gcd(m,n), d'=gcd(n,r) 이라고 하자. d = gcd(m,n) 이므로 d | m , d | n 이고, 따라서 d | r 이다. 

d | r 이므로 d | d' 이고, 역으로 d' | n 이고 d' | r 이란 사실로 부터 d' | m 을 얻을 수 있고, 그래서 d' | d 이다.

따라서 d = d' 이다. 

증명이 바로 이해 되었으면 아래 증명에 대한 설명글은 안 봐도 된다. ^^

• d = gcd(m,n), d'=gcd(n,r) 이라고 하자. 
• d = gcd(m,n) 이므로 d | m , d | n 이고, 따라서 d | r 이다.
  - 최대공약수의 약수는, 두 수의 공약수 이므로, 최대공약수 d는 m의 약수이기도 하고(d | m), n의 약수이기도 하다(d | n)
  - d | m 이므로 m=da, a:정수 라고 할 수 있다. 마찬가지로 d | n 이므로 n = db b:정수 라고 할 수 있다.
     m = nq + r에 대입하면 da = dbq + r 이다.
     양변을 d로 나누면 a = bq + r/d 가 된다. 여기서 a가 정수이므로 r/d 도 정수가 되야하고, 따라서 r은 d로 나눠져야한다.
     즉 d | r 인 것이다.
• d | r 이므로 d | d' 이다.
  d|m, d|n, d'|n, d'|r 이므로, m = nq + r 을 dα = dβq + d'γ 라고 할 수 있다. (여기서 α, β, γ 는 정수)
  dα = dβq + d'γ 식의 양변은 d로 나누면,  α = βq + d'γ/d 가 된다. 여기서 α가 정수이므로 d'γ/d 가 정수라야 하기에(어떠한 γ에 대해서도) d'/d 가 정수라야 한다. 즉 d | d' 이라야 한다.
• 역으로 d' | n 이고 d' | r 이란 사실로 부터 d' | m 을 얻을 수 있고, 그래서 d' | d 이다.
  d'|n, d'|r 이기에 m = nq + r 식은 m = d'αq + d'β (α,β 는 정수) 로 나타낼 수 있고, 양변을 d'으로 나누면 m/d' = αq + β 가 되어서, αq + β 가 정수이기에 m/d' 도 정수가 되어야 하고, 따라서 d' 은 m의 약수라야 한다. (d' | m)
  d|m, d'|n, d'|r 이므로 m = nq + r 식은 dα= d'βq + d'γ (α,β,γ 는 정수) 로 나타낼 수 있고, 양변을 d'으로 나누면 (d/d')α = βq + γ 가 되고, 우변인 (βq + γ) 가 정수이므로 좌변인 (d/d')α 도 정수가 되야 하고, 따라서 d' | d 이다.
• 그러므로 d| d' 이고 d' | d 이므로, d = d' 이다.

(명제)

양의 정수 m,n에 대해, am+bn = gcd(m,n)을 만족하는 정수 a와 b가 존재한다. 

이 명제는 모듈러 산술에서 아주 중요한 정리인 '중국인의 나머지 정리'를 이해하기 위해서 필요한 부분으로, 증명없이 그냥 알아 두면 되겠다.

내용은, 두 수에 대한 최대공약수는 두 수에 어떤 값을 곱한 후 더한 값으로 표현할 수 있다는 것이다. 

예를 들어, 두 수 m=6, n=9에 대해서 gcd(6,9)=3이다. 이것을 6a + 9b로 표현할 수 있다는 것이고, (a,b)=(2,-1)= (5,-3) ... 일 때 6a+9b=3을 만족한다. 즉, 6a + 9b = 3을 만족시키는 a,b가 항상 존재한다.

m과 n이 서로 소인 경우는 gcd(m,n)=1이 된다. 따라서, 위의 명제에 따르면, m과 n이 서로 소이면 am + bn = 1을 만족하는 a,b가 존재한다. 

두 수의 최대공약수 구하기

두 정수의 최대공약수는 어떻게 구할까?

가장 단순한 방법은 모든 공약수를 구한 후, 거기서 가장 큰 수를 찾는 것이다. 물론 효율적이지 않다.

중학교때 배웠던 방법은 소인수분해를 해서 구하는 방법이 있다. 소인수분해가 가능한 비교적 작은 수에 대해서는 아주 쉽게 구할 수 있는 방법이다. 그러나, 소인수분해가 거의 불가한 큰 수에 대해서는 먹히지 않는 방법이다.

소인수분해에 의한 최대공약수 구하기

서로소가 나올 때까지 공약수로 나누고, 나온 공약수를 모두 곱한다. 

60과 48의 최대공약수를 구하는 것은,

    2 )60  48

    2 ) 30  24

    3 ) 15  12

         5   4

서로 소인 5와 4가 나올 때까지 공약수 2,3,3으로 나눴고, 이 세 수를 곱한 18이 최대공약수가 된다.

소인수분해가 가능하지 않은 큰 수에 대해서는 그 옛날 그리이스 수학자인 유클리드에 의해 만들어졌다는 알고리즘을 사용한다.

유클리드 호제법 (Euclidean Algorithm)

유클리드 호제법은 두 정수의 최대공약수를 구하는 알고리즘의 하나로, 컴퓨터 프로그래밍으로 두 수의 최대공약수를 구할 때 가장 많이 사용되는 알고리즘이다. 여기서 호제법(互除法)이란 것은 두 수가 서로(互) 상대방 수를 나누어(除 나눌 제)서 결국 원하는 수를 얻는다는 의미이다. 

기본 원리는 위 쪽에서 설명한 최대공약수의 성질 중, [m = nq + r 이면, gcm(m,n) = gcd(n,r)]를 이용한 것이다. 즉, 정수 m과 n에 대해서 m을 n으로 나눴을 때 나머지를 r이라고 하면, m과 n의 최대공약수는 n,r의 최대공약수와 같다는 것이다.(단, m>n) 이 성질에 따라, n을 r로 나눈 나머지 r'을 구하고, 다시 r을 r'으로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 최대공약수가 된다.

2006과 1360에 대해 유클리드 알고리즘으로 최대공약수 구하기

2006 = 1360 ×1 + 646

1360 = 646  × 2 + 68

646 = 68 × 9 + 34

68 = 34 × 2 + 0   --> 34: 최대공약수

최소공배수(Least Common Multiple)

두 정수의 최소공배수는, 두 수의 공배수중에서 가장 작은 수이고, 두 수 m,n에 대한 최소공배수는 lcm(m,n)으로 표현한다.

최소공배수의 중요한 성질은 다음과 같다.

• lcm(m,0) = 0 
  두 수중 하나가 0일 때 최소공배수는 0이다. 최대공약수의 경우는 0이 아닌 수가 최대공약수이다. gcd(m,0)=m
• lcm(m,n) = |mn|/gcd(m,n)
  두 수의 최소공배수는, 두 수를 곱한 값을 최대공약수로 나눈 값과 같다.
  예를들어, lcm(192,72) = |192 x 72| / gcd(192,72) = (192 x 72) / 24 = 576