페르마의 소정리(Fermat's Little Theorem).
오일러 피함수 aφ(n) ≡ 1 (mod n) 연장선으로 보면 된다.
n = p (소수)라면 φ(p) = p - 1
aφ(p) = a(p-1) ≡ 1 (mod p)
∴ ap ≡ a (mod p)
| 정리.1 |
| 소수 p라 두고, 어떤 정수를 a라 두면, ap ≡ a (mod p) |
예제 1. a = 5, p = 7
→ 57 = 78125 ≡ 5 (mod 7)
→ 56 = 15625 ≡ 1 (mod 7)