페르마의 소정리

선행지식

• 모듈러 성질

<aside> 💡

정리

임의의 정수 a와 소수 p에 대하여

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

특히 gcd(a,p)=1일 때

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

</aside>

증명 개요

1. $p∤a$라 가정하고, 집합 {1,2,...,p-1}의 각 원소에 a를 곱하고 mod p를 취하면 ${a,2a,...,(p-1)a}≡{1,2,...,p-1}$의 순열이 된다.
2. 두 집합의 곱을 비교하면

$$ 1\cdot2\cdots(p-1) \equiv a\cdot2a\cdots(p-1)a = a^{p-1}(1\cdot2\cdots(p-1)) \pmod{p} $$

1. $gcd((p-1)!,p)=1$이므로 양변에서 (p-1)!를 약분하여

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

1. 양변에 a를 곱해

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

응용

• 모듈러 역원:

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

• 거듭제곱 축약:

$$ a^k \bmod p = a^{k \bmod (p-1)}\bmod p,\quad(gcd(a,p)=1) $$

예제

• p=7, a=12일 때

$$ 12^6 = 2,985,984 \equiv 1 \pmod{7} $$