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

페르마의 소정리 증명

앞선 장에서 우리는 조합론적 방법으로 다음 사실을 증명했다.

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

우리가 목걸이라는 개념을 이용해 이 사실을 증명했으니 편의상 ‘목걸이 보조정리’라고 부르도록 하자. 목걸이 보조정리를 이용해 페르마의 소정리를 증명하려면, 소수가 지닌 또 하나의 특별한 성질을 알아야 한다. 이 성질은 매우 중요해서 특별한 이름이 붙어있다. 다만 증명은 생략하도록 하겠다.

유클리드의 보조정리
소수 p와 자연수 x, y를 가정하자. 만약 p가 xy를 나눈다면, p는 x와 y 중 적어도 하나를 나눈다.

유클리드의 보조정리를 보고 '굳이 p가 소수여야 하나?'라는 의문이 든 분들을 위해 몇 가지 예제를 살펴보자. 예를 들어 p=5, x=4, y=10이라 하자. 5는 40을 나누며, 유클리드의 보조정리에 따라 5는 4를 나누거나 10을 나눠야 한다. 실제로 후자가 성립한다. 반면 p=6, x=4, y=9인 경우를 보자. 6은 36을 나누지만, 6은 4도 9도 나누지 못한다. 이런 현상은 왜 일어나는 걸까?

유클리드의 보조정리는 '산술의 기본정리'와 함께 '소수의 원자성'을 뒷받침한다. 산술의 기본정리가 '모든 자연수는 유일한 방법으로 소인수분해된다'이며, 이는 '만물은 원자로 이루어져 있다'는 원자론의 원칙과 궤를 같이한다. 반면 유클리드의 보조정리는 'p가 xy의 일부라면 x의 일부이거나 y의 일부여야 한다', 즉 p가 두 조각으로 나뉘어 일부는 x에, 일부는 y에 포함될 수 없다는 뜻이다. 이는 원자가 더 이상 쪼개지지 않는다는 사실과 일맥상통한다. (각주 [1] 참고.)  6이 유클리드의 보조정리를 만족하지 않는 이유는, 6은 2와 3으로 쪼개어지기 때문이다. 2는 4를 나누고, 3은 9를 나눈다. 그래서 6은 4×9, 즉 36이라는 전체는 나누지만, 각각의 부분인 4와 9는 나누지 못한다.

소수의 정의와 유클리드의 보조정리는 소수의 원자성을 떠받치는 원칙이다. 그리하여 둘은 ‘뗄레야 뗄 수 없는 관계’처럼 보인다. 즉, 임의의 자연수가 소수라면 유클리드의 보조정리를 만족하고, 반대로 임의의 자연수가 유클리드의 보조정리를 만족하면 소수여야 하는 것처럼 보인다. 하지만 이는 우리에게 익숙한 '정수'라는 수체계에서만 참이다. 수학자들은 정수의 성질을 유지하며 그 체계를 확장하는 방법을 발견했고, 놀랍게도 그렇게 확장된 수체계에서는 우리가 당연하게 여겨온 사실들이 성립하지 않을 수 있다는 것을 깨달았다. 예를 들어 수체계를 조금만 확장해도 '유일 소인수분해'가 성립하지 않는 경우가 생긴다. 즉 6이라는 수가 2 x 3말고도 ‘다른 방법’으로 분해되는 것이다! 물론 이 주제는 우리가 아직 이해하기에는 이르니, 나중에 다루도록 하자. 지금은 '우리에게 너무나 당연한 성질'조차도 '정수'라는 특별한 상황에서만 성립한다는 점만 기억하자.

본 주제로 돌아와, 목걸이 보조정리와 유클리드의 보조정리를 이용해 페르마의 소정리를 증명해 보자. 먼저 p를 소수로, a를 p와 서로소인 정수라 하자. 우리가 증명한 소정리에 의해 p는 a^p-a를 나눈다. a^p-a는 a(a^{p-1}-1)로 분해할 수 있고, 유클리드의 보조정리에 의해 p는 a를 나누거나 a^{p-1}-1을 나눠야 한다. 하지만 a와 p가 서로소이므로, p는 a를 나누지 못한다! 따라서 p는 a^{p-1}-1을 나눈다. 이를 합동연산으로 표현하면 a^{p-1} ≡ 1 (mod p)가 되며, 이로써 페르마의 소정리를 증명했다.

페르마의 소정리를 증명했다고 끝일까? 물론 아니다. 수학자들은 '하나의 사실'에 만족하지 않는다. 그들은 그 사실 너머에 있는 '왜 이럴 수밖에 없을까'라는 원리를 탐구한다. 과연 p는 꼭 소수여야만 할까? 임의의 자연수에서는 이 성질이 성립할 수 없을까? 수학자 오일러는 바로 이 의문을 속 시원하게 해결했다. 그는 페르마와 달리 자신만의 도구를 하나 만들었는데, 그것이 바로 오일러 피함수(Euler’s totient function) φ(n)이다. (각주 [2] 참고.) 오일러 φ함수의 정의는 다음과 같다.

φ(n) = 1 이상 n 이하의 자연수 중 n과 서로소인 수의 개수

1 이상 4 이하의 자연수 중 4와 서로소인 수는 1과 3이다. 그러므로 φ(4)는 2다. 

1 이상 5 이하의 자연수 중 5와 서로소인 수는 1, 2, 3, 4다. 그러므로 φ(5)는 4다. 

1 이상 6 이하의 자연수 중 6과 서로소인 수는 1과 5다. 그러므로 φ(6)은 2다. 

1 이상 7 이하의 자연수 중 7과 서로소인 수는 1, 2, 3, 4, 5, 6이다. 그러므로 φ(7)은 6이다. 

1 이상 8 이하의 자연수 중 8과 서로소인 수는 1, 3, 5, 7이다. 그러므로 φ(8)은 4다. 

이들을 살펴보며 몇 가지 '패턴'을 발견할 수 있다.   

φ(n)은 1 이상 n 미만이다.

p가 소수라면 φ(p) = p-1이다. p가 소수일 때는 p보다 작은 모든 자연수와 서로소이기 때문이다.

n이 다양한 수로 나뉜다면, φ(n)은 상대적으로 작은 값을 갖는다. (각주 [3] 참고.)

자 이제 오일러가 발전시킨 페르마의 보조정리를 살펴보자.

정리
a와 n이 서로소라 하자. 그렇다면 a^(φ(n)) ≡ 1 (mod n)

역시 예제를 살펴보지 않을 수가 없겠다. 아무래도 계산이 쉬운 n = 10의 경우를 살펴보자. 먼저 X (mod 10)은, X라는 자연수의 1의 자리만 살핀다라는 뜻과 같다. 예컨대 34 = 4 (mod 10)인데, 10이 34 - 4, 곧 30을 나누기 때문이다.

이 정리를 확인하려면 먼저 φ(10)을 알아야 한다. 10보다 작으며 10과 서로소인 수는 1, 3, 7, 9가 있으므로 φ(10)은 4다. a는 10과 서로소여야 하니, 여기서는 1, 3, 7, 9를 각각 a에 대입해 식을 살펴보자.

a=1이라면, 1⁴=1이므로 1 ≡ 1 (mod 10)을 만족한다.

a=3이라면, 3⁴=81이므로 81 ≡ 1 (mod 10)을 만족한다.

a=7이라면, 7⁴=2401이므로 2401 ≡ 1 (mod 10)을 만족한다.

a=9이라면, 9⁴=6561이므로 6561 ≡ 1 (mod 10)을 만족한다.

하지만 a를 2나 5처럼 10과 서로소가 아닌 수로 택하면 이 식이 성립하지 않는다. 2⁴=16이므로 16 ≡ 6 (mod 10)이고, 5⁴=625이므로 625 ≡ 5 (mod 10)이다.

앞서 우리는 p가 소수라면 φ(p)=p-1이란 사실을 보았다. 오일러의 정리에 n에 소수 p를 대입하면 페르마의 소정리가 된다. 뉴턴 역학이 아인슈타인의 상대성 이론의 특수한 경우이듯, 페르마의 소정리 역시 오일러의 정리의 특수한 경우에 불과했던 것이다. 오일러의 정리를 보면 페르마의 소정리가 너무나 당연하고 사소하게 느껴진다. 페르마의 소정리보다 더 깊은 통찰을 담고 있기 때문이다. "페르마가 발견한 놀라운 패턴을 '제대로 이해하려면' p-1을 φ(p)로 이해해야 해! 이 놀라운 정리의 '참 비밀'은 바로 φ함수야!”

오일러가 페르마의 보조정리를 확장했다고 이야기가 끝났을까? 그럴 리가! 오일러의 정리는 우리에게 더 거대한 진실의 일부를 암시한다. 오일러의 정리에 의하면 a가 1, 3, 7, 9 중 하나일 때 a⁴ ≡ 1 (mod 10)이 성립한다. 그렇다면 더 작은 지수는 어떨까? a=3일 때, a¹, a², a³, a⁴는 각각 3, 9, 27, 81로 mod 10에서는 3, 9, 7, 1이 된다. 즉 1, 3, 7, 9의 조합이 모두 나온다. 반면 a=9라면, a¹, a², a³, a⁴는 각각 9, 81, 729, 6561이며, mod 10에서는 9, 1, 9, 1이 된다. 모든 조합이 나타나지 않는다. 왜 이런 차이가 생기는 걸까?

그 비밀은 10과 서로소인 수들의 집합 {1, 3, 7, 9}에 특별한 연산 체계가 존재하기 때문이다. 사실 꼭 10일 필요는 없다. n이 어떤 자연수든 n보다 작으며 n과 서로소인 자연수들의 집합은 특별한 연산 체계를 지닌다. 이러한 연산 체계를 군(group)이라 부르는데, 놀랍게도 오일러 사후 약 70년이 지나서야 수학에서 '정식으로' 정립된 개념이다. 이 놀라운 오일러의 정리조차도 군론의 관점에서 보면 너무나 당연한 결과다. 이렇게 더 큰 세계를 발견하고, 기존의 지식이 그저 당연한 것이 되어버리는 순간들이 수학의 경이이자 매력이다.

물론 지금 군론으로 뛰어들 수도 있겠지만, 우리는 조금 더 역사의 발자취를 찬찬히 따라가며 필요한 선행지식과 도구를 모을 것이다. 오일러의 정리와 φ함수가 더 큰 세계로 인도하는 길이라는 사실을 염두에 두고, 소수의 더 깊은 비밀들을 탐험해 보자.

[1] 유클리드의 보조정리는 1이 소수여서는 안 되는 또 다른 이유를 덧붙인다. 1은 x와 y가 무엇이든 xy, x, y를 전부 나누기 때문이다.

[2] 해당 그리스 문자의 이름이 phi여서 피함수라고 부른다. 1 이상 n이하의 자연수 중 n과 서로소인 수를 n의 totient라고 하지만, 거의 사용하지 않는 단어이다.

[3] 사실 φ(n)의 값을 구하는 간단한 공식이 있다. n의 각 소인수 p에 대해, n에 (1-1/p)를 곱하면 된다. 예를 들어 6의 소인수는 2와 3이다. 따라서 φ(6)는 6×(1-1/2)×(1-1/3)=6×(1/2)×(2/3)=2가 된다.