페르마의 소정리 증명

July 28, 2020

개요

**페르마의 소정리(Fermat's little Theorem, FlT)**는 정수론의 근간이 되는 매우 중요한 정리입니다. 페르마의 소정리는 다음과 같습니다.

$p$ 가 소수이고, $gcd(n, p) = 1$ 이면, $n^{p-1} \equiv 1 (mod\;p)$

쉽게 풀어 설명하면 임의의 소수인 p와, p와 서로소인 수 n의 p-1승을 p로 나눈 나머지는 1이라는 뜻입니다.

PS를 하면서도 상당히 많이 사용하게 되는 정리이므로 증명이 필요하다고 생각 되어, 친구의 도움을 받아 증명을 하게 되었습니다.

페르마의 소정리 증명

페르마의 소정리에 나오는 정의에 따라 p를 어떤 소수, a를 p와 서로소인 수로 두겠습니다. $\mathbb {Z}$ 는 정수집합입니다. 집합 $S=\{n|n \neq 0, n = \mathbb {Z}\,mod\;p\}$ 는 그럼 $p-1$ 개의 원소를 가지게 됩니다. 집합 $aS=\{n|n \neq 0, n = a ⋅ (\mathbb {Z}\,mod\;p)\}$ 는, 집합 $S$ 에 있는 모든 원소에 a를 곱한 원소로 이루어져있는 집합으로, 역시 $p-1$ 개의 원소를 가지게 됩니다.

집합 aS를 봅시다.

\{a⋅1, a⋅2, ⋯, a⋅(p-1)\}

이 집합에 $(mod\;p)$ 연산을 해주면 놀랍게도 집합 S와 원소가 일치함을 보일 수 있습니다. p가 소수이고, a와 서로소이기 때문입니다. 따라서 $(mod\;p)$ 에서 다음과 같습니다.

\{a⋅1, a⋅2, ⋯, a⋅(p-1)\} = \{1, 2, ⋯, (p-1)\}

그렇다면 집합 S의 원소들을 모두 곱한 값 $(p-1)!$ 과 집합 aS의 모든 원소들을 곱한 값 $a^{p-1}⋅(p-1)!$ 은 $(mod\;p)$ 에서 합동이며 수식으로 표현하면 다음과 같습니다.

a^{p-1}⋅(p-1)! \equiv (p-1)! ⋅ (mod\;p)

여기서 나머지 연산은 분배법칙이 성립하므로 $(p-1)!$ 을 소거 하면 다음과 같은 결과를 얻을 수 있습니다.

a^{p-1} \equiv 1 (mod\;p)

Q.E.D.!