[Mathematics] 유클리드 호제법의 증명

이제 벌써 제가 중학교 3학년입니다.. 시간이 왜 이리 빠른지 모르겠어요. 저는 아직 애긴데 벌써 고교생이라니. 저는 진짜 아직 애긴데. 저번에 서울과학고등학교를 넣었던 적이 있는데 2차에서 가볍게 떨어져주고요즘 유가도 비싼데 괜히 서울까지 왔다갔다만 했다 이번에는 지방과고인 전북과학고를 넣었습니다. 합격할 것 같긴 하지만 합격하려면 준비를 철저히 해야 하죠. 제 자소서에 제가 수학특기로 유클리드 호제법을 넣었습니다. 면담에서 증명하라칼것같아서 글을 써보려 합니다.

 

우선 유클리드 호제법이라는 것은 a>b인 두 자연수 a, b에 대해서 a=bq+r이라고 할 때 gcd(a, b)=gcd(b, r)이라는 것입니다. 이게 무슨 의미가 있냐 하면 gcd(3414943903189551289, 5271801051238932951279151101)과 같은 엄청나게 큰 수들의 최대공약수 값을 구할 때에 굉장히 유용합니다. 수가 계속해서 작아지니까요. 전산적으로도 큰 의미가 있죠. 이는 나중에 Algorithm 관련 글에서 한 번 더 다루겠습니다.

 

암튼 그래서 유클리드 호제법을 증명해봅시다.

 

gcd(a, b)는 a와 b 모두에 들어 있는 인수죠. 그러니까 gcd(a, b)=G라고 하면 a와 b는 이렇게 나타낼 수 있습니다. $$ a = Ga', b = Gb' (단, a'과 b'은 서로소) $$ 이건 아주 간단한 내용이죠?

 

그리고 a>b이기 때문에 b로 a를 나눌 수가 있습니다. 거기서 나오는 몫을 q, 나머지를 r이라고 하면 이렇게 나타낼 수 있겠죠. $$ a = bq + r (단, r < b) $$ r은 나머지기 때문에 b보다 작은 것은 당연합니다.

 

그렇다면 이제 gcd(a,b) = gcd(b,r)임을 증명하면 되겠죠? 아까 a=bq+r이었으니까 여기에다가 a=Ga', b=Gb'을 대입하면 이렇게 됩니다. $$ Ga' = Gb'q + r $$ 그렇게 되면 r은 이렇게 되겠죠? $$ r = Ga' - Gb'q = G(a'-b'q) $$ 이러면 b=Gb'이기 때문에 b와 r 모두 공통으로 G라는 약수를 가지고 있음을 알 수 있습니다.

 

그런데 아직 이 G가 최대공약수인지는 몰라요. 이 G가 최대공약수임을 증명하기 위해 귀류법을 사용해보겠습니다.

 

歸謬法, Proof by Contradiction

수학과 논리학의 증명법 중 하나. 배리법(背理法)이라고도 한다.

어떤 명제가 참이라고 가정한 후, 모순을 이끌어내 그 가정이 거짓임을, 즉 처음의 명제가 참임을 증명하는 방법이다. 일상 언어 생활에서도 은근히 자주 볼 수 있는 방식이다. "그래, 네 말이 맞다고 치자. 그런데 이러이러하니까 말이 안 되네. 따라서 네 말은 틀렸어"식의 말이 다름 아닌 귀류법.

수학에서는 흔히 간접적 증명이라고도 부른다.

 

나무위키에서 인용했습니다. 암튼 이 귀류법을 이용할건데, 한번 G가 최대공약수가 아니라고 가정해봅시다. 그렇다면 b와 r 모두 다른 약수를 가지고 있겠죠? 그 약수를 m이라고 해 봅시다. 그런데 b=Gb', r=G(a'-b'q)이기 때문에 굳이 b와 r로 나타내지 않아도 b'과 a'-b'q가 같은 약수를 가지고 있으면 되겠죠? $$ b' = mb'', a'-b'q = mr' $$

 

그러면 a'b'q=mr'이라는 식에 b'=mb''을 대입하여 봅시다. $$a'-mb''q = mr' $$ 정리하면 이렇게 되겠죠? $$ a' = mr' + mb''q = m(r' + b''q) $$ 그런데 이렇게 되면 a'과 b'이 서로소라는 조건에 위배됩니다! 모순이 생기는 거예요. 그래서 이건 틀렸고, G가 최대공약수가 되며 증명이 완료됩니다.

 

Comment.

아 면담때 진짜 잘해야하는데