[정수론 입문 시리즈 16편] 페르마 소정리는 왜 거듭제곱 계산을 단순하게 만들까?

중국인의 나머지 정리까지 오면 합동식의 기본 도구는 어느 정도 갖추게 됩니다. 이제는 모듈러 세계에서 큰 거듭제곱을 빠르게 다루는 정리를 볼 차례입니다. 그 출발점이 페르마 소정리입니다.

What this post covers

• 페르마 소정리의 내용을 설명합니다.
• 왜 소수 mod에서 거듭제곱이 특별한 패턴을 보이는지 감각을 잡습니다.
• 간단한 예시로 큰 거듭제곱의 나머지를 빠르게 구합니다.
• 다음 글의 오일러 정리로 자연스럽게 이어집니다.

이번 글에서 새로 나오는 용어

• 페르마 소정리 (Fermat's Little Theorem): 소수 $p$와 $p$의 배수가 아닌 정수 $a$에 대해 $a^{p-1} \equiv 1 \pmod p$가 성립한다는 정리입니다.
• 소수 (Prime Number): 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수입니다.
• 합동 (Congruence): 같은 나머지를 가지는 관계입니다.
• 오일러 정리 (Euler's Theorem): 페르마 소정리를 일반 mod로 확장한 정리입니다.

페르마 소정리의 내용

소수 $p$와 $p$의 배수가 아닌 정수 $a$에 대해

$$a^{p-1} \equiv 1 \pmod p$$

가 성립합니다.

또는 같은 내용을 다음처럼도 자주 씁니다.

$$a^p \equiv a \pmod p$$

두 형태는 서로 연결되어 있습니다. 다만 입문 단계에서는 조건을 구분해 기억하는 것이 좋습니다.

• $a^{p-1} \equiv 1 \pmod p$ 형태는 $p \nmid a$일 때 쓰고
• $a^p \equiv a \pmod p$ 형태는 모든 정수 $a$에 대해 성립하는 버전으로 볼 수 있습니다.

왜 이 정리가 유용할까?

이 정리는 매우 큰 거듭제곱의 나머지를 줄이는 데 강력합니다. 소수 mod에서는 일정한 주기가 생기기 때문입니다.

예를 들어 mod 7에서는

$$a^6 \equiv 1 \pmod 7$$

가 $a$가 7의 배수가 아닐 때 성립합니다. 그러면 $a^{100}$ 같은 큰 지수도 6으로 나눈 나머지를 이용해 줄일 수 있습니다.

예시 1. $3^{100} \pmod 7$

페르마 소정리에 의해

$$3^6 \equiv 1 \pmod 7$$

입니다.

100을 6으로 나누면

$$100 = 6 \times 16 + 4$$

이므로

$$3^{100} = (3^6)^{16} \times 3^4 \equiv 1^{16} \times 3^4 \equiv 81 \equiv 4 \pmod 7$$

입니다.

직접 큰 수를 계산할 필요 없이 지수를 줄일 수 있습니다.

예시 2. $2^{30} \pmod 5$

5는 소수이므로

$$2^4 \equiv 1 \pmod 5$$

입니다.

또

$$30 = 4 \times 7 + 2$$

이므로

$$2^{30} = (2^4)^7 \times 2^2 \equiv 1^7 \times 4 \equiv 4 \pmod 5$$

입니다.

이 정리의 조건을 꼭 봐야 한다

페르마 소정리는 아무 mod에서나 쓰는 정리가 아닙니다.

• 법 $p$는 소수여야 하고
• $a$는 $p$의 배수가 아니어야 합니다.

예를 들어 mod 8에서는 일반적으로 $a^7 \equiv 1$ 같은 식을 그대로 기대하면 안 됩니다. 그 경우는 다음 글의 오일러 정리처럼 더 일반적인 틀에서 봐야 합니다.

Common mistakes

1. 법이 소수인지 확인하지 않는 실수

페르마 소정리는 소수 mod에서의 정리입니다.

2. $a$가 $p$의 배수인 경우까지 그대로 적용하는 실수

조건을 만족하지 않으면 $a^{p-1} \equiv 1 \pmod p$를 바로 쓸 수 없습니다.

3. 지수를 줄이면서 나머지 계산을 끝까지 정리하지 않는 실수

지수만 줄이고 마지막 작은 거듭제곱 계산에서 실수하는 경우가 많습니다.

Wrap-up

이번 글에서는 페르마 소정리를 통해 소수 mod에서 큰 거듭제곱의 나머지를 빠르게 줄이는 방법을 정리했습니다.

다음 글에서는 이 생각을 일반 mod로 확장하는 오일러 피 함수와 오일러 정리를 살펴보겠습니다.