As an extension of congruences, this is a powerful theorem for instantly finding the remainder of a large power.
When p is prime and a is an integer that is not a multiple of p:
ap−1 ≡ 1 (mod p)
Equivalent expression: ap ≡ a (mod p)（also holds when a is a multiple of p）
Example ①
Find the remainder when 2100 is divided by 101.
101 is prime. By Fermat's Little Theorem, 2100 ≡ 1 (mod 101)
Answer: The remainder is 1
Find the remainder when 2100 is divided by 101.
101 is prime. By Fermat's Little Theorem, 2100 ≡ 1 (mod 101)
Answer: The remainder is 1
Example ②
Find the remainder when 32023 is divided by 7.
7 is prime. 36 ≡ 1 (mod 7)（by Fermat, p−1=6）
2023 = 6×337 + 1 → 32023 ≡ 31 ≡ 3 (mod 7)
Answer: The remainder is 3
Find the remainder when 32023 is divided by 7.
7 is prime. 36 ≡ 1 (mod 7)（by Fermat, p−1=6）
2023 = 6×337 + 1 → 32023 ≡ 31 ≡ 3 (mod 7)
Answer: The remainder is 3
Example ③ (Application to multiplicative inverses)
Find the solution to 3x ≡ 1 (mod 7)（use Fermat's Little Theorem）.
36≡1(mod 7) → 3×3⁵≡1(mod 7) → x≡3⁵=243≡243−7×34=243−238=5(mod 7)
Answer:x ≡ 5 (mod 7)
Find the solution to 3x ≡ 1 (mod 7)（use Fermat's Little Theorem）.
36≡1(mod 7) → 3×3⁵≡1(mod 7) → x≡3⁵=243≡243−7×34=243−238=5(mod 7)
Answer:x ≡ 5 (mod 7)
Key points
- ap−1≡1(mod p)（p: prime, p∤a）
- Reduce the exponent to its remainder upon division by p−1
- Multiplicative inverse: the inverse of a is ap−2 (mod p)
Practice Problems
- Find the remainder when 512 is divided by 13.
- Find the remainder when 71000 is divided by 11.
- Solve 4x ≡ 1 (mod 13) using Fermat's Little Theorem.
Answers and Explanations
- 13 is prime. 512≡1(mod 13) → remainder 1
- 11 is prime. 710≡1(mod 11)。1000=10×100 → 71000≡1100=1(mod 11) → remainder 1
- 412≡1(mod 13) → 4×411≡1 → x≡411(mod 13)。4²=16≡3、4⁴≡9、4⁸≡81≡3、411=4⁸×4²×4¹≡3×3×4=36≡10(mod 13) → x≡10(mod 13)