FermatLittle

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

페르마 소정리

소수의 세계에는 어떤 일이 일어나고 왜 그럴까 하는 것은 아직까지 상당부분 모습을 드러내지 않고 있다. 거기도 놀라운 세상이 펼쳐질 것 같은데 탐험가들은 그 세계에 충분히 이르지 못하고 있다. 그렇다고 이 세계에 대해 사람들이 무관심하거나 게을렀던 것은 결코 아니다. 이 탐험길에 커다른 기여을 한 사람이 바로 페르마다.

페르마는 비록 법 전문가였지만 젊었을 때 공부했던 수학을 평생 즐겨했다. 법학이 사실은 논리학에 견줄 만큼 대단히 논리적인 학문이라고 이해한다면 수학애호가였던 그가 수학의 세계 곳곳에 새 땅을 일군 것은 마냥 놀랄만한 일은 아니다. 비록 수학자로 먹고 사는 일을 한 것은 아니었지만 페르마는 인류 역사상 가장 위대한 아마츄어 수학자였다. 그 중 산술 분야에서서 업적을 볼 것이다. 이 정리를 보통 페르마의 위대한 정리 (또는 '페르마 마지막 정리') 에 견주어 ‘페르마 소정리(Fermat's little theorem)’라고 부른다.

어떤 정수가 다른 정수로 나뉘는 것을 알아내는 절대적인 일반 법칙을 찾지 못했거나, 혹 사람의 능력으로는 찾을 수 없다고 해도 수학하는 사람들은 절망하지 않는다. 그 절대법칙을 찾는 것에서 물러서서 풀만한 문제들로 쪼개보면서 가능한 것들에 대하여 해답을 찾아가는 것도 즐거운 여정이다. 십진법 체계에서, 예를 들어, 짝수로 끝나는 모든 자연수는 2로 나뉜다. 또는 0이나 5로 끝나는 모든 수는 5로 나뉜다. 또는 어떤 자연수가 있을 때, 그 자연수를 구성하는 숫자들을 합해서 3이 되면 그 수는 3으로 나뉜다... 이런 예는 아주 많다. '페르마 소정리'는 그런 단순한 것을 뛰어 넘어 수론에서 새로운 길을 트는 첫발이 되었다고 볼 수 있다.^[1] 페르마가 내디딘 길을 따라 자연수와 소수 세계의 탐험길은 여러 갈래로 갈리게 되었다. 그 중 페르마 소정리와 맞닿아 있는 몇가지 정리들 중 기초적인(elementary) 방법으로 밝힐 수 있는 것들도 함께 살피기로 한다.

페르마 소정리

어떤 수를 나눌 수 있는가에 대한 일반 법칙들은 이미 페르마 전 수천년 동안 있었을 터이지만 페르마가 해낸 것처럼 틀린 것 없이, 간명하게 드러나면서 수학적으로 의미있는 경우는 아직 발견되지 않았다. 페르마는 1640년 가을 친구에게 보낸 편지(불어, 영어)에 이 정리에 대하여 썼다. 정리 부분만 요약하면 다음과 같다.

정리 : p가 소수고 p가 a를 나누지 않는다면, p는 $a^{p-1}-1$ 을 나눈다.

어떤 자연수 a 에 곱셈으로 조직된 요소 중에 p 가 없다면, 그 자연수를 p-1 번 곱한 다음 1을 뺀 수는 반드시 p 로 나뉘어야 한다는 말이다. 따라서 어떤 자연수 a 가 주어졌을 때, 그것보다 작은 자연수들 중 소수를 골라내 a 를 나눠보고, 안나뉘면 a 를 그 소수에서 하나 뺀만큼 곱한 다음 1 을 빼면 된다. 그렇게 얻어진 수와 그 배수들은 p 를 '가지게' 된다. 또는 모듈 합동 관계의 언어를 써서 나타내면

정리 : p가 소수고 p가 a를 나누지 않는다면, $a^{p-1}\equiv _{p}1$

모듈 합동 관계에서 그 예가 될만한 것들을 이미 보았다 : $10^{10}\equiv _{11}(-1),\ 10^{2}\equiv _{3}1,\ 10^{6}\equiv _{7}1$

페르마 소정리의 증명

페르마는 이 정리에 대하여 엄격하게 증명하지 않은 것으로 알려졌다. 대신 지금까지 발견된 최초의 증명은 라이프니쯔의 증명이다. 이 정리의 중요성 때문에 그 이후 여러가지 증명이 나왔다. 그 중 간단한 증명을 보도록 하자. ^[2] 만약 이 정리가 주어졌고 증명을 어떻게 할지 막막하다면 먼저 우리 앞에 놓인 변수와 그 핵심적 모양이 무엇인지 보자. $a^{p-1}$ 꼴이 반드시 등장해야 한다는 것, 그리고 이것은

{\begin{matrix}\underbrace {a\cdot a\cdot a\cdots a} \end{matrix}}

로 a가 p-1번 등장하는 꼴이 나온다는 것에 주목할 수 있다. 게다가 정리의 식에서 p가 소수라는 것이 핵심적인 제약조건으로 역할을 해야만 할 것이다. (p가 소수가 아닌 경우를 스스로 검토해보라.) 그 중 어떤 소수 p도 그보다 작은 자연수 $1,2,3,4,5,\dots ,p-1$ 들을 나눌 수 없다. 그리고 그 개수는 p-1개 다. 그렇다면 p보다 작은 자연수의 개수 p-1은 a가 등장하는 회수와 연관이 있을지 모른다. 어떻게 하면 a 를 p-1 번 등장하게 할까?

증명

$1,2,3,4,5,\cdots ,p-1$ 에 모두 a를 곱한 수들을 보자.

1a,2a,3a,4a,5a,\cdots ,(p-1)a

이 수들은 최소한 두가지의 성질을 가지고 있다. (왜 그런가?)

첫째, 이 수들은 모두 p 로 나뉠 수 없다.
둘째, 이 수들의 열에 있는 어떤 두 수도 p로 나누어 나머지가 같을 수 없다.

그렇다면 위의 수들은 모두 나머지로 $1,2,3,4,5,\cdots ,p-1$ 들이 꼭 한번 씩 나타나게 된다. 따라서 이 수들을 모두 곱하여 나온 수는

(1a)\cdot (2a)\cdot (3a)\cdot (4a)\cdot (5a)\cdots (p-1)a

p의 배수에 $1\cdot 2\cdot 3\cdots (p-1)$ 가 더해진 수가 될 것이다. 다시 말해,

(1a)\cdot (2a)\cdot (3a)\cdot (4a)\cdot (5a)\cdots (p-1)a=p\cdot q+1\cdot 2\cdot 3\cdots (p-1)

인 q가 있게 된다. 양쪽에 $1\cdot 2\cdot 3\cdots (p-1)$ 을 빼고 곱셈에 대한 기본적인 성질에 따라

1\cdot 2\cdot 3\cdots (p-1)\cdot (a^{p-1}-1)=p\cdot q

이다. 산술의 기본정리를 위한 기초정리 증명에서 보았듯이 $1\cdot 2\cdot 3\cdots (p-1)$ 가 p로 안나뉘므로 $a^{p-1}-1$ 가 나뉜다. 증명 끝

증명을 다시 보라. 문제의 두 조건은 어디에서 결정적인 역할을 하였는가?
페르마 소정리 관련 증명들 : 넘어간 부분 증명, 페르마 정리의 관련 다른 증명들

페르마 소정리의 발전

위의 페르마 정리는 수론의 연구에 획기적인 기여를 하였다. 이 정리는 간단한 조건만 가지면서, 지극히 일반적인 '틀'을 가진 수들에 대하여 나눌 수 있음을 말하고 있다. 여기에 쓰인 변수는 두가지 밖에 없고 문장은 매우 간단하다. 중요한 정리들이 그렇듯 이 정리는 다른 중요한 정리를 증명하는데 자주 쓰일 뿐더러 이 정리 자체가 연구 대상이 되어 발전되어 간다. 무엇보다 위의 정리에서 어떻게 하면 제약조건을 없애거나 줄여 일반적으로 나타내 볼 수 있을까 하는 문제를 생각해볼 수 있다.

페르마 소정리 일반화 1

위의 정리에서 a가 p의 배수가 아니라는 조건을 완화시켜보자. 간단히 이렇게 바꾸면 된다. (왜 그런가?)

정리 : p가 소수라면, $a^{p}\equiv _{p}a$

페르마 소정리 일반화 2

페르마 소정리를 구체적인 수에서 검토해보기 위하여 소수 23을 모듈로 하고 23과 a가 23의 배수가 아닌 것 중 5를 예로 들어보면,

5^{2}\equiv _{23}2,\ 5^{4}\equiv _{23}4,\ 5^{8}\equiv _{23}16\equiv _{23}7,\ 5^{16}\equiv _{23}49\equiv _{23}3,\ 5^{20}\equiv _{23}12,\ 5^{20}\equiv _{23}24\equiv _{23}1

그런데 5대신 4를 예로 들어보면,

4^{2}\equiv _{23}-7,\ 4^{3}\equiv _{23}-28\equiv _{23}-5,\ 4^{4}\equiv _{23}-20\equiv _{23}3,\ 4^{8}\equiv _{23}9,\ 4^{11}\equiv _{23}-45\equiv _{23}1,4^{22}\equiv _{23}1

이다. 앞의 a가 5일 때는 최초로 p로 나뉘는 것이 $5^{22}-1$ 인데 비해 a가 4일 때는, $4^{11}-1$ 일 때였다. '주어진 소수 p 가 a 를 나누지 않을 때, $a^{x}-1$ 최초로 p로 나뉘게 하는 최소값 x는 꼭 p-1이라고 할 수 없다'는 실마리를 찾은 셈이다. 이를 바탕으로 페르마 소정리를 살짝 일반화시켜보는 정리를 보자.

정리 : p가 소수고 a를 나누지 않는다면, $a^{x}\equiv _{p}1$ 가 되는 최소의 x는 p-1의 약수이다.

페르마 소정리 일반화 3 : 오일러

오일러는 다음과 같이 일반화하였다. 문제의 조건에서 소수라는 엄격한 조건을 완화한 것이다. ^[3]

a 와 n 이 서로 소라면, $a^{\varphi (n)}\equiv _{n}1$

여기서 함수 $\varphi (n)$ 는 n 보다 작고 n 과 서로소인 수들의 개수를 나타내는 함수라 하자. 보통 오일러 함수라고 부른다. 이 정리에서 n 이 소수라면 $\varphi (n)$ 는 물론 p-1 이라 페르마 소정리를 포괄한다.

증명

n보다 작고 n와 서로소인 관계에 있는 수가 $k_{1},k_{2},\cdots ,k_{m}$ 로 m개 있다고 하자. 이 수들에 모두 a 를 곱한다. 그렇다면 그 수들은 모두 n 과 서로소이며, 따라서 서로 다른 나머지를 갖는다. 그 나머지들을 $r_{1},r_{2},\cdots ,r_{m}$ 라고 하자. 이 수들은 순서만 다를 뿐 $k_{1},k_{2},\cdots ,k_{m}$ 의 항들과 같다. 그렇다면

a\cdot k_{1}=q_{1}\cdot n+r_{1}

a\cdot k_{2}=q_{2}\cdot n+r_{2}

\ldots

a\cdot k_{m}=q_{m}\cdot n+r_{m}

이다. 항들끼리 곱해서 n에 대해 정리하면 어떤 수 Q에 대해

a^{m}\cdot k_{1}\cdot k_{2}\cdots k_{m}=Q\cdot n+r_{1}\cdot r_{2}\cdots r_{m}

인 Q 가 있을 것이다. 따라서

k_{1}\cdot k_{2}\cdots k_{m}\cdot (a^{m}-1)=Q\cdot n

이고 $a^{m}-1$ 은 n으로 나뉜다. 증명 끝.

앞의 정리에서 $\varphi (n)$ 를 분명하게 나타낼 수 있다. (스스로 풀어보라)

n 이

p^{\alpha }\

이라면

\varphi (p^{\alpha })=p^{\alpha }-p^{\alpha -1}

n 이

p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{m}^{\alpha _{m}}

이라면,

\varphi (p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{m}^{\alpha _{m}})=n(1-{\frac {1}{p_{1}}})(1-{\frac {1}{p_{2}}})\cdots (1-{\frac {1}{p_{m}}})

윌슨 정리

페르마 소정리와 그것을 더 일반화시킨 오일러 정리는 산술의 발전에 지대한 공헌을 끼쳤고 지금도 그렇다. 마치 새 길을 내는 것과 같은 역할을 했기 때문에 그리로 가는 길들은 이 길을 거쳐가게 된다. 앞으로 볼 제곱꼴 나머지에서도 이를 느낄 수 있을 것이다. 페르마 소정리에서 쓰인 증명 방식을 응용한 (소위) 윌슨 정리를 보면서 페르마 소정리의 '힘'을 느껴보도록 하자.

이 정리는 다음의 정리를 증명할 때 쓰이기도 했다.

페르마-오일러 정리 : $x_{1}^{2}+x_{2}^{2}=N$ 일 때 N이 소수라면 항상 $4n+1$ 꼴이고 그 역도 성립한다.

놀라운 정리다! 이 멋진 사실을 드러내는데 라그랑쥐는 이 정리를 증명^[4]하고 페르마-오일러 정리를 증명하는 데 썼다.^[5] 이 정리는 이론적으로 널리 쓰이지는 않지만, 어떤 수가 소수가 될 필요충분조건을 말한다는 점에서 '소수의 행동이나 성격'을 나타낸다고 볼 수 있다.

정리 :

(p-1)!\ \equiv _{p}\ -1\ \Leftrightarrow \ p\in {\mbox{Prime}}

사실, 이 정리를 과연 윌슨 정리로 부르는 것은 무리가 있다. 지금까지 알려진 바에 따르면 1770 년 윌슨이 이 정리를 발표하였고는 하지만, 증명이 없었다. 이 정리의 발견 자체는 이미 그보다 1000여년 전인 지금의 이라크 학자였던 이븐 알-헤이담(ibn al-Haytham) 의 공헌이었다. 그리고 지금까지 발견된 증명 중 발표가 가장 빠른 것은 1773 년 라그랑쥐의 증명이다. 라이프니쯔가 그보다 100여년 앞서 증명한 것으로 보이지만, 발표는 안되었다.^[6]

$7^{222}$ 의 십진법으로 나타낼 때 끝자리수는 무엇일까?

페르마 소정리의 응용

수론 전반에 끼친 영향은 말할 것도 없다. 그렇다고 거기에 머물러 있지 않는다.

소수의 성질을 파악하는데 가장 기초적인 정리 중 하나다. 예를들어 어떤 수 n 이 소수인지 아닌지 판별할 수 있는 도구도 된다. 이를 페르마 소수 판정(Fermat primality test)이라고 부른다. 어떤 자연수 n 에 대해 그것보다 작은 자연수들을 차례로 x 에 넣어서 $x^{n-1}\equiv _{n}1$ 인지 보면 된다. 만약 그렇다면 n 은 소수고 그렇지 않고 어떤 수 a 에서 앞의 식이 안되면 그 n 은 소수가 아니다. 알고리듬으로 만들 수는 있다.
암호를 만들고 푸는데도 중요한 역할을 한다 : Wikipedia의 RSA 설명 참고.
페르마를 괴롭히는 수들 : 테스트 해가면서 앞의 틀이 안되는 경우, 다시 말해, $x^{n-1}$ 을 n 으로 나누었더니, 나머지가 1 이 아닌 어떤 수가 있다면, 그것은 분명하게 말하고 있다. " n 은 소수일 수 없다 " 고. (물론 이때, x 와 n 은 서로소 일 경우다.) 그런데, 문제는 어떤 n 에 대해 $x^{n-1}\equiv _{n}1$ 의 틀을 만족한다고 해서 그것이 소수라는 보장이 없다는 것이 문제다. 이렇게 테스트를 통과하는 수들, 어떤 x 에 대해서도 $x^{n-1}$ 을 n 으로 나누었더니, 나머지가 1 인 경우의 n 들 중에는 소수도 있고 합성수도 있을 수 있다. 과연 있을까? 진짜 있다. 그것은 20 세기 초 미국의 카마이클(R.Carmichael) 이 발견했다.

561,1105,1729,...

들이 그 예인데, 놀랍게도 이 수들은 모두 세개 이상의 소수의 곱으로 되어 있다. 또 이 수들은 소수에 비해서도 매우매우 드물게 드러난다. 하지만 어쨌든 그 수들 덕분에 페르마가 밝혀 놓은 소수 판정은 '넌 소수가 아니야' 라고 말할 수는 있지만, '그래 넌 소수야'라고 쉽게 말할 수 없게 되어버렸다. 페르마를 무척 괴롭히는 수들이다.

wikipedia Carmichael number