페르마의 소정리

페르마의 소정리라고도 불리는 이 정리는 다음과 같이 수학적으로 표현된다.

Let $p$ be a prime number, and let $a$ be an integer that is not a multiple of $p$. Then

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

풀어 써보면 이렇다.

$1^4 \equiv 2^4 \equiv 3^4 \equiv 4^4 \equiv 6^4 \equiv ...$ $1 \space (mod \space 5)$

다시 풀어 써보면 이런 뜻이다.

5의 배수가 아닌 어떤 정수에라도, 5-1 = 4 제곱을 하면 그 수를 5로 나눈 나머지는 1이라는 뜻이다.

가령 7의 4제곱은 2,401로, 5로 나눴을 때 1이 남는다.

페르마의 소정리가 강력한 이유는, 아주 큰 수라도 어떤 수로 나눴을 때의 나머지를 쉽게 구할 수 있기 때문이다.

예를 들어 $2^{85}$ 를 $11$ 로 나누면 몇이 남을까?

페르마의 정리를 이용하면, $2^{10} \equiv 1 \space (mod \space 11)$ 임을 알 수 있다.

$2^{85} \equiv (2^{10})^8 \times 2^5$ 이므로, 결국 $2^5 = 32$ 를 $11$ 로 나눈 나머지인 $10$ 이 답이 된다.

사실 위 문제를 풀기 위해서는 페르마의 소정리뿐 아니라 정수론에 등장하는 몇 가지 규칙들에 대해서도 알긴 해야 한다.

중요한 점은, 승수와 소수가 갖는 특성을 일반화할 때, 엄청나게 큰 수에 대해서도 자신 있게 대답할 수 있게 된다는 것이다.

수학의 중요한 특징 중 하나인 일반화가 갖는 힘이라고 할 수 있다.