GCD

자연수 세계 - 서론과 이야기거리 로 돌아가기

약수와 배수 ; 최대공약수

모든 정수는 몫과 나머지를 갖는다

어떤 자연수 a 가 있다하고 그 보다 작은 자연수로 나눈다고 해보자. 이런 연산은 초등학교 때부터 참 많이도 했을 것이다. 예를들어, 100 을 7 로 나누어보자.

$100=7\cdot 1+93=7\cdot 2+86=\cdots =7\cdot 13+9=7\cdot 14+2$

이다. 마찬가지로 어떤 자연수 a 를 더 작은 자연수 b 로 나누었을 때,

$a=b\cdot q+r$

로 표현할 수 있다. 여기서 주어지는 기초 정보인 b 는 0 이 아니라고 한다. (0 이면 무엇이 문제인가?) 앞의 예에서 보았듯이, 나타내는 방법은 a 와 b 에 따라 여러가지 경우다. 하지만, 위의 표현에 어떤 조건을 건다면 문제는 달라진다. 여러가지 조건이 가능하겠다. 또, 100 개의 사탕을 7 명에게 고루 나누어주면 남은 것의 개수는 ? 이라고 물을 때처럼 나눗셈의 현실적인 뜻을 생각하면서 조건을 나머지인 r 에 집중해보자.

$0\leq r<b$

라는 조건을 추가하자. 그렇다면

어떤 자연수 a, b 에 대하여 $0<b<a$ 이라면, 항상 다음 관계를 만족하는 정수 q 와 0 보다 크거나 같고 b 보다 작은 r을 찾을 수 있다.

$a=b\cdot q+r$

이 때, 조건을 만족하는 a 와 b 가 주어진다면 q 와 r 은 딱 하나씩, 정해질 것이다. (왜 그런가?)

이제 위의 표현을 정수로 확장해보자. 확장하여 일반식으로 나타내면 아래와 같다.

어떤 정수 a, b 에 대하여 b 가 0 이 아니라면, 항상 다음 관계를 만족하는 정수 q 와 0 보다 크거나 같고 b 보다 작은 r을 찾을 수 있다.

$a=b\cdot q+r$

이를 기호로 표시하면

$\forall a,b\ \exists q,r\ (a=b\cdot q+r)$

꼴이 된다. 여기서 b와 r에 대해서는 조건이 붙었지만, a에 대해서는 아무런 제약이 없다는 것을 명심하라. a는 0 이거나 음의 정수일 때도 이 문장은 참이다. a 가 -29, b 가 3 으로 주어졌다고 해도 $-29=3\cdot (-10)+1$이므로 q 는 -10 , r 은 1 로 나타난다. 그렇다면, 과연 $\forall a,b\ \exists !q,r\ (a=b\cdot q+r)$일까? (여기서 $\exists !$ 란 단 하나만 존재함을 나타낸다. ) 다시 말해 주어진 적당한 a 와 b 에 대해 조건을 만족하는 q 와 r 은 하나의 쌍으로만 나올까? 위의 정리를 살짝 일반화시켜 $|r|<b$ 로 절대값 r 이 b 보다 작다고 바꿔보자. 예를들어 a 는 13, b 는 3 이라면, 13 = 4*3 + 1 = 5*3 + (-2)도 된다. 대신 어떤 경우는 q가 정해지면 r은 유일하게 결정된다. 그렇다면 우리가 처음 던진 질문처럼 'r 이 0 보다 크거나 같고 b 보다 작다면' q 와 r 은 한 쌍만 나올까? (스스로 풀어보라)

이는 생각하기에 따라 당연해 보인다. 수직선 모델을 빌어 '설명'해보면, 어떤 직선에 0 을 한 점으로 표시하고 b 의 부호에 따라 한 쪽으로는 $b,2b,3b,\cdots$ 를, 다른 쪽으로는 $\cdots ,-3b,-2b,-b$ 를 표시하고 나면 모든 정수를 | b | 칸으로 쪼개어 표시한 것과 같다. 만약 a 가 이 중 어떤 점과 겹친다면 r 은 0 이고 겹치지 않는다면 $0<r<b$ 가 될 것이다. 어떤 경우든 q 를 찾는 알고리듬은 명확하다. 이를 식으로 표시하면

• a 는 b의 정수 배수이거나 아니다. 정수 배수라면 r = 0 이고 그때 정수 배수가 q 다.
• 정수 배수가 아니라 하자.
  • $bq<a<b(q+1)$ 이 참인 q 를 찾으면, 다시 말해, 0 < a - bq 이면 , a - bq 를 r 로 하면 된다.
  • $b(q+1)<a<bq$ 이 참인 q 를 찾으면, 다시 말해 $b(q+1)-a<0$ 이면, $b(q+1)-a$ 을 r 로 하면 된다.

설명 끝. 예를들어 a 가 27 라 하자. 만약 b 가 4 라면, 4*6 < 27 < 4(6+1) 이므로 q 는 6, r 은 1 이다. 그때 만약 b 가 -4 라면, (-4)(-6) < 27 < (-4)(-6 +1) 은 성립하지 않는다. 대신 (-4)(-7+1) < 27 < (-4)(-7) 이므로 q 는 -6, r 은 3 이다. 이 알고리듬은 b 보다 작은 r 이 양수이도록 유일하게 결정한다.

정의

이미 알고 개념들일 것이다. 0 이 아닌 정수 a, b 에 대하여

정의 : 약수와 배수 : $a=b\cdot k$ 인 양의 정수 k가 있으면 b를 a 의 '약수'라 한다. 그리고 a를 b의 '배수'라한다.

나눗셈에서 썼던 기호를 쓰면 $a\mid b$ 이면 b를 a의 약수라 하고 a 는 b 의 배수가 된다. 0 이 아닌 어떤 두 정수 a, b 에 대해서도 a = bq + r 인 관계가 성립하므로, 약수의 정의를 'r = 0 인 경우 b 를 a 의 약수다' 라고 정의해도 괜찮다.

정의 : 공약수  : a 의 약수이고 b 에도 약수인 것을 'a 와 b 의 공약수'라 한다.

정의 : 공배수  : a 의 배수이고 b 에도 배수인 것을 'a 와 b 의 공배수'라 한다.

정의 : 최대공약수  : 공약수 중 가장 큰 것을 '최대공약수'라 한다.

최대공약수를 이렇게 정의해 주어도 된다. (두 정의가 등가라는 것을 증명해보라.)

정의 : 최대공약수 := a, b의 모든 공약수들이 나누는 공약수

a와 b의 최대공약수가 d라면

$(a,b)=d$ 또는 $GCD(a,b)=d$

라고 쓰기로 하자.

정의 : 최소공배수  : 공배수 중 가장 작은 것을 '최소공배수'라 한다.

a와 b의 최소공배수가 m 이라면

$LCM(a,b)=m$

라고 쓰기로 하자. 따라서 공약수는 최대공약수의 약수들이며, 공배수는 최소공배수의 배수들이다.

최대공약수는 매우 중요한 역할을 한다는 사실을 차차 알아갈 것이다. 그런데 과연 최대공약수를 어떻게 찾을까? 위의 정의대로 하면 a 와 b 라는 두 수가 주어지면 우선 그 수의 공약수를 찾아야 한다. 그 말은 두 수를 소수로 분해한다는 것을 전제하고 있다. 어떤 수를 소수로 분해하는 것은 암호 체계에서 쓰이고 있을 만큼 매우 어려운 알고리듬이다. 다음 예를보자.

(8,12) = 4 , (5,9) = 1, (12, 18) = 6 , (693, 2541) = 231 , (27797,22781) = 209

수가 커질수록 점점 어려워진다. 그렇다면 두 수의 최대공약수를 찾는 것이 실수를 찾는 것보다 어려운 알고리듬일까? 그렇지는 않다. 하나의 수를 소수로 분해하고 다음 수를 소수로 분해해서 둘을 비교하는 사고틀을 벗어나면 된다. 이 두수의 상대적 관계를 보면서 해결해갈 수 있다. 유클리드 알고리듬 이 바로 그것이다. 유클리드 알고리듬은 아주 단순하면서도 광범위하게 응용되는 중요한 법칙이다. 그것은 주어진 두 수의 '상대적 관계'를 중요하게 생각했다는 점에서 중요한 사고의 전환이라 할만하다. 이에 대해서는 보기로 한다.

서로소 관계 : (a, b) = 1 이면 서로소 관계에 있다고 한다.

예를 들어, 27, 64 두 수에 대하여 (27, 64) = 1 다. 4 와 12 를 본다면 4 의 약수는 1, 2, 4 이고, 12 의 약수는 1, 2, 3, 4, 6, 12 이므로 (4,12) = 4 다.

최대공약수의 성질

과연 0 이 아닌 어떤 정수 a, b 에 대해서도 최대공약수는 존재할까? 이는 다음의 정리로서 답을 얻을 수 있다. 정리 : 주어진 a와 b에 s와 t를 선형으로 결합해서 만들 수 있는 자연수를 모두 모아 보면 그 중 가장 작은 수가 최대공약수이다. 기호로 다시 쓰면

$(a,b)=\min\{v\ |\ v=a\cdot s\pm b\cdot t\}$

최대공약수의 응용

직선형 디오판테스 방정식의 해 구하기

위의 정리1)을 살짝 일반화하면 이렇게 바꿀 수 있다.

정리 1  : 어떤 정수 b가 두 수의 곱 ax를 나누고 (a,b) =1 이면 b는 x를 나눈다.

이번엔 방정식의 언어로 써보면

정리 1'  : bx = ay 이고 (a,b)=1이면, x = am이고 y=bm인 m이 존재한다.

그리고 이를 좌표 위에 직선의 방정식과 연관된 용어로 하면,

정리 1"  : (a,b)=1이면, 직선 ay - bx = 0 위에 놓인 모든 정수점을 찾으면 어떤 정수 m에 대하여 x = am이고 y=bm 다.

이는 ax - by = 0 꼴의 디오판테스 방정식의 일반 해를 구하는 것에 대하여 말하고 있다. 이로부터 다음과 같은 사실을 유추할 수 있다.

정리 2  : 'ay - bx = c 를 참이도록 하는 정수 해 (x,y)가 있다.' $\Leftrightarrow$ 'c는 (a,b)로 나뉜다.

증명

($\Rightarrow$)정수해가 있으면 c는 (a,b)로 나뉜다 : (a, b) = d 이면, c도 d로 나뉜다는 것은 두말할 나위 없다.

($\Leftarrow$) c가 (a,b)로 나뉘면 정수해를 갖는다 : c로 나뉘면 양쪽 항을 모두 c로 나누자. 그렇게 되면 a'y - b'x = 1'이 되고 (a',b') = 1이다. 따라서 이는 산술의 기본정리의 기초정리 0에 따라 해를 갖는다.

정리 3 : (a,b) =1 이면 ay - bx = c 를 참이도록 하는 정수 해 (x,y)는 끝없이 많다.

그리고 만약 우리가 그 중 하나$(x_{0},y_{0})$ 만 찾는다면 정수 k 에 대해 (x,y)는 항상 $(x_{0}+ak,y_{0}+bk)$) 이다.

증명

어떤 하나의 해 $(x_{0},y_{0})$ 를 찾았다고 해보자(이 부분은 아래 보일 것이다). 그러면

$ay_{0}-bx_{0}=c$ 이므로

$ay-bx=ay_{0}-bx_{0}$이고,

$a(y-y_{0})=b(x-x_{0})$

이다. 정리 1")에 따라 $x-x_{0}=am$ 이고 $y-y_{0}=bm$ 인 어떤 m 이 있게 된다.

이제 정리의 조건을 만족하면 이 디오판테스 방정식이 최소한 하나의 해가 있다는 것을 보일 것이다. 산술의 기본정리의 기초정리 0에서 보았듯이 (a,b) =1 이면 ay - bx = 1 일 때의 해가 있다. 그 해를 $(x_{1},y_{1})$라 하면,

$ay_{1}-bx_{1}=1$

이고, 양쪽 항에 모두 c를 곱하면,

$ay_{1}c-bx_{1}c=c$

이므로 최소한 하나의 해는 $(x_{1}c,y_{1}c)$ 이다.

놀랍게도 직선형 디오판테스 방정식의 계수 a, b의 최대공약수만 찾으면 그 방정식의 해를 구할 수 있게 된 것이다. 이는 두 문제가 겉으만 달라 보일 뿐 논리적으로 같은 힘을 갖고 있다는 것을 뜻한다. 그런데, 만약 (a,b)= 1 인 상황에서는 어떻게 될까?

직접 풀어보라

• (a, b) = (a, a-b)
• 어떤 자연수가 완전제곱꼴이 아니면 짝수개 약수를 갖고, 완전제곱꼴이면 홀수개 약수다.
• 약수가 5개만 있는 자연수를 찾아보라. 약수가 6개만 있는 약수를 찾아보라.
• a가 4로 안나뉘는 짝수라하자. 그렇다면 a의 약수에는 짝수 약수의 개수와 홀수 약수의 개수의 관계는?

자연수 세계 - 서론과 이야기거리 로 돌아가기

Note

Math : Math글쓰기 | Math번역 | MathBoard | Math&Culture | MathMoim
OnLineMathCenter | MathCamp | SoftMathJournal | MathBook | CyberAcademia | Academia