gen-briefly-explain-fermat-s-little-theorem-and-one-common-misco-9a12

Briefly explain Fermat's little theorem and one common misconception about it.

# Fermat's Little Theorem **The theorem states:** If *p* is a prime number and *a* is any integer not divisible by *p*, then: a^(p-1) ≡ 1 (mod p) Alternatively: a^p ≡ a (mod p) for any integer *a*. **In plain terms:** When you raise a number to the power of (prime - 1) and divide by that prime, the remainder is always 1. **Example:** Let p = 5, a = 2 - 2^4 = 16 - 16 ÷ 5 = 3 remainder **1** ✓ ## Common Misconception **The converse is NOT always true.** Many people mistakenly believe that if a^(n-1) ≡ 1 (mod n), then *n* must be prime. **Counterexample:** n = 561, a = 2 - 2^560 ≡ 1 (mod 561) - But 561 = 3 × 11 × 17 (composite!) Such numbers are called **Carmichael numbers** — they pass Fermat's test for all bases but aren't prime. This is why primality testing requires more sophisticated methods than just Fermat's theorem.