소수: 수학자들이 사랑한 수 (6)

취미 기타취미

정수론민수

02.10

조합론적 증명

앞서 우리는 페르마의 소정리를 살펴보았다. 이번 장에서는 페르마의 소정리를 증명하는데 필요한 보조정리를 증명할 것이다. 그 보조정리의 증명은 너무나도 우아하고 탁월해서, 이번 장에는 그 증명에만 집중하고자 한다. 이번 장에서의 우리의 목표는 다음의 명제를 증명함이다.

보조정리
p를 소수, a를 자연수라 하자. 그렇다면 p는 a^p-a를 나눈다.

이 명제의 증명을 위해 구체적인 상황을 가정해 보자. 당신은 실에다 구슬을 꿰어 목걸이를 만드는 아르바이트를 하고 있다. 당신에겐 a 종류의 구슬이 주어졌고, 그중 p개를 골라 실에 꿸 것이다. 이때 만들 수 있는 목걸이의 종류는 몇 가지일까?

간단한 경우부터 시작해 보자. a = 2, p = 5인 경우다. A와 B, 두 종류의 구슬 중 5개를 선택하여 실에 꿰어야 한다. 각 위치마다 A와 B, 2가지 선택이 가능하고 그렇게 5번을 선택해야 하므로, 만들 수 있는 가닥의 가짓수는 2⁵ = 32다.

AAAAA, AAAAB, AAABA, AAABB, AABAA, AABAB, AABBA, AABBB, ABAAA, ABAAB, ABABA, ABABB, ABBAA, ABBAB, ABBBA, ABBBB, BAAAA, BAAAB, BAABA, BAABB, BABAA, BABAB, BABBA, BABBB, BBAAA, BBAAB, BBABA, BBABB, BBBAA, BBBAB, BBBBA, BBBBB

당신은 성실하게 모든 경우의 구슬 가닥들을 만들어냈다. 뿌듯한 마음도 잠시, 당신은 중요한 사실을 깨달았다. 당신이 만들고자 하는 것이 가닥이 아니라 목걸이란 점을 말이다. 목걸이는 '첫 구슬'이나 '마지막 구슬'이란 게 없다. 예컨대 AAAAB, AAABA, AABAA, ABAAA, BAAAA 이들은 결국 모두 같은 목걸이를 만들어낸다. 즉 모든 목걸이의 조합을 만들기 위해 모든 가닥의 조합을 만들 필요가 없었다. 물론 이 32가닥을 모두 분해하기란 너무 귀찮은 작업인지라, 당신은 먼저 이들을 '같은 목걸이가 되는 가닥'끼리 정리한다.

AAAAA

AAAAB, AAABA, AABAA, ABAAA, BAAAA

AAABB, AABBA, ABBAA, BBAAA, BAAAB

AABAB, ABABA, BABAA, ABAAB, BAABA

AABBB, ABBBA, BBBAA, BBAAB, BAABB

ABBAB, BBABA, BABAB, ABABB, BABBA

ABBBB, BBBBA, BBBAB, BBABB, BABBB

BBBBB

한 가지 구슬만을 사용해 만든 가닥을 '밋밋가닥' 두 가지 이상의 구슬을 사용해 만든 가닥을 '알록가닥'이라 부르도록 하자. 또 이렇게 만든 목걸이를 '밋밋목걸이' '알록목걸이'라 부르자. 당신은 다음과 같은 사실을 깨닫는다.

주어진 구슬의 종류가 2개이므로, 2개의 밋밋가닥이 있다.
5개의 알록가닥이 같은 알록목걸이를 만들어낸다. 하나의 알록가닥을 두고 옆으로 1칸, 2칸, 3칸, 4칸을 옮긴 경우가 그것들이다.
즉 2⁵개의 총 가닥 중, 밋밋가닥 2개를 제외한 나머지 2⁵-2개는 알록가닥이다. 이 알록가닥들은 최종 목걸이의 생김새에 따라 분류해 줄 수 있으며, 각 분류에는 5개의 알록가닥이 있다.
그러므로 5는 2⁵-2를 나눈다! (이쯤 되면 눈치챘겠지만, 총 만들어내는 목걸이의 경우의 수가 사실 우리의 최종 목적지가 아니었다. 그것을 세는 과정에서 우리는 원하는 결과를 증명해 냈다.)

이번엔 조금 더 난이도를 높여 a = 4이고 p = 7인 경우를 가정해 보자. 우리는 4종류의 구슬(A,B,C,D) 중 7개를 골라 가닥을 만들어야 하니, 4⁷, 곧 16384 종류의 가닥이 나올 것이다. 하지만 지난번에서 호되게 데어본 당신은 이 모든 종류를 만들지 않아도 된다는 사실을 알고 있다. 이들 중 한 가지 구슬만 이루어진 밋밋가닥은 총 4개뿐이며, 나머지 4⁷-4개의 가닥은 모두 알록가닥이다. 앞선 경우처럼 양 끝을 이었을 때 '같은 목걸이'가 되는 가닥끼리 모아보자. 예를 들어 목걸이 조합 AABBCCD는 다음 7개의 가닥으로 만들 수 있다:

AABBCCD, ABBCCDA, BBCCDAA, BCCDAAB, CCDAABB, CDAABBC, DAABBCC

즉, 4⁷-4개의 알록가닥들은 7개씩 묶어서 셀 수 있고, 이는 곧 7이 4⁷-4를 나눈다는 뜻이다.

이 논증은 a가 자연수이고 p가 소수일 때 항상 성립한다. a 종류의 구슬 중 p개를 골라 가닥을 꿰면, 총 a^p개의 가닥이 만들어진다. 이들 중 a개만이 밋밋가닥이고, 나머지는 모두 알록가닥이다. 재미있는 점은 이 알록가닥들을 '최종 목걸이의 생김새'에 따라 분류하면, 각 분류에 정확히 p개의 가닥이 들어간다는 사실이다. 마치 '둥글게 둥글게' 놀이처럼 a^p-a개의 알록가닥들을 "p개씩 모여!" 하면 탈락자 없이 깔끔하게 나누어진다. 이는 곧 p가 a^p-a를 나눈다는 뜻이다.

하지만 p가 합성수라면 이 방법은 더 이상 통하지 않는다. 예를 들어 a = 2이고 p = 6인 경우를 보자:

목걸이 ABBABB를 만드는 가닥은 3개뿐이다: ABBABB, BBABBA, BABBAB
목걸이 ABABAB를 만드는 가닥은 2개뿐이다: ABABAB, BABABA
반면 AAAAAB를 만드는 가닥은 6개나 된다: AAAAAB, AAAABA, AAABAA, AABAAAA, ABAAAA, BAAAAA

이처럼 최종 목걸이의 생김새에 따라, 그것을 만드는 가닥의 개수가 제각각이다. 각 알록 목걸이를 만드는 가닥의 가짓수가 항상 6개가 아니므로 2⁶-2개의 알록가닥들을 두고 '6개씩 모여!' 외쳤을 때 탈락자가 생기게 된다. 실제로 2⁶-2는 62이며, 이는 6으로 나뉘지 않는다!

이 목걸이 증명에서 p가 소수라는 사실은 꽤나 교묘하게 사용되었는데, 각 알록목걸이를 만드는 가닥이 정확히 p개라고 확신할 수 있는 이유가 바로 그것이다. p = 6의 경우처럼 합성수는 더 작은 수로 나뉘기 때문에, 2개짜리 패턴이나 3개짜리 패턴이 반복되는 문제가 생긴다. 하지만 p가 소수라면 이런 일이 일어날 수 없다. 이 점이 이 논증을 돋보이게 만든다.

수학에는 조합론(Combinatorics)이라는 분야가 있는데, 간단히 말해 '세는 방법'을 연구하는 학문이다. 조합론은 아주 복잡한 문제도 실생활의 예시와 영리한 셈법으로 해결하곤 하는데, 이를 조합론적 증명이라고 한다. 이런 증명법이 꼭 조합론에만 국한되지는 않는다. 정수론은 1, 2, 3, 4와 같은 특정한 수들을 다루는 학문이다 보니, '셈의 문제'로 재해석하기 좋다. 이때 복잡한 수식보다 조합론적 증명이 더 명쾌할 때가 많다. 조합론적 증명은 다른 증명법보다 필요한 선행지식이 적고 일반인도 이해하기 쉬운 '퍼즐' 같은 매력이 있어서, 이번 기회에 소개하고 싶었다.