정수론 (5) - 페르마의 소정리
저번에 합동식에서 나눗셈을 하기 위한 조건에 대해서 알아보았습니다.
이 내용을 바탕으로 정수론에서 매우 중요하게 다뤄지는 정리인 페르마 소정리에 대해서 알아보겠습니다.
페르마 소정리는 아래와 같습니다. (단, $p$는 소수, $a$는 $p$의 배수가 아닌 정수)
$$
a^{p-1} \equiv 1 \mod p
$$
예를 들어서 $p = 7, a = 12$ 라고 하면,
$$
12^{7-1} = 12^{6} = 2985984 \equiv 1 \mod 7
$$
이 됩니다. 암호학의 핵심이 되는 정리라고 할 수 있죠.
이 정리가 어떻게 응용될 수 있는지는 나중에 더 보기로 하고, 이번 글에서는 이 정리의 증명에 집중하겠습니다.
페르마 소정리의 증명
다음과 같은 크기 $p-1$의 집합을 살펴보겠습니다. (단, $p$는 소수)
$$
\lbrace 1, 2, \cdots, p-1 \rbrace
$$
이 집합의 모든 원소에 $a$ 를 곱하겠습니다. (단, $a$는 $p$의 배수가 아닌 정수입니다)
$$
\lbrace a, 2a, \cdots, (p-1)a\rbrace
$$
먼저 다음 사실을 보이는 것이 이 증명의 핵심입니다.
$$
\lbrace 1, 2, \cdots, p-1 \rbrace = \lbrace a, 2a, \cdots, (p-1)a \rbrace \mod p
$$
예를 들어서 $p = 5, a = 2$라고 하면,
$\lbrace 1, 2, 3, 4\rbrace$에 $2$를 곱한 집합 $\lbrace 2, 4, 6, 8 \rbrace$는 $\bmod 5$에서 $\lbrace 2, 4, 1, 3 \rbrace = \lbrace 1, 2, 3, 4 \rbrace$가 됩니다.
위의 사실을 보이기 위해 아래의 사실을 보입시다.
$$ \lbrace a, 2a, \cdots, (p-1)a \rbrace \mod p \text{의 모든 원소들은 서로 다르다.} $$
증명은 귀류법을 쓰면 간단합니다. $i \neq j$인데 $ia \equiv ja \mod p$인 $i, j$가 존재한다고 가정합시다.
$p$가 소수이므로 저번 글에서 봤었듯 양변을 $a$로 나눌 수 있습니다.
양변을 나누면 $i \equiv j \mod p$가 되며, $1 \leq i, j \leq p-1$ 이므로 $i = j$입니다. 이는 가정에 모순입니다.
따라서 $\lbrace a, 2a, \cdots, (p-1)a\rbrace$와 $\lbrace 1, 2, \cdots, p-1 \rbrace$은 같은 집합입니다.
두 집합이 법 $p$에 대해 동일하므로 이 두 집합의 모든 각 원소를 곱한 값도 같을 것입니다.
$$
a^{p-1}(p-1)! \equiv (p-1)! \mod p
$$
$(p-1)!$과 $p$는 공통 인수를 가지지 않으므로 서로소입니다.
따라서, $(p-1)!$의 역원이 존재하며, 양변을 $(p-1)!$ 으로 나누면 아래의 식이 성립합니다.
$$
a^{p-1} \equiv 1 \mod p \quad \blacksquare
$$
기약잉여계
페르마 소정리의 증명 자체는 간단하지만, 이 과정에서 중요한 개념이 등장합니다.
$p$가 소수일 때 아래의 식이 성립합니다.
$$
\lbrace 1, 2, \cdots, p-1 \rbrace \equiv \lbrace a, 2a, \cdots, (p-1)a \rbrace \mod p)
$$
이런 형태의 집합은 정수론 곳곳에서 중요하게 쓰입니다. 그래서 이름도 있습니다. 바로 기약잉여계라고 합니다.
기약잉여계: 정수 $m$에 대하여 1부터 $m-1$까지 $m$과 서로소인 수들을 모아놓은 것
예를 들어 $9$ 기약잉여계는 $\lbrace 1, 2, 4, 5, 7, 8 \rbrace$가 되겠네요.
기약잉여계의 특징은 모든 원소가 역원을 가지기 때문에, 언제나 나눗셈이 가능하다는 점입니다.
이렇게 페르마 소정리에 대한 내용을 끝냅니다. 다음 글에서는 페르마 소정리의 일반화 버전인 오일러 정리에 대해 알아보겠습니다.
