Practice question · Multiple choice
Fermat's little theorem says a^(p−1) ≡ 1 (mod p) for prime p. Why does that make it a fast primality test rather than only a curiosity?
Hints
- The theorem says what primes do. Ask what follows when a number does not do it.
- Modular exponentiation is fast. Factoring is not. Which does this test need?
Show the answer
B. Because it cheaply proves a number is NOT prime, without finding a factor
Why
It is a one-way test: failure proves compositeness without exhibiting a factor, and passing is only evidence. Carmichael numbers pass for every a and are composite, which is why practical tests like Miller-Rabin repeat with random bases, and why RSA key generation can find 2048-bit primes in moments.
Practise Congruences and Applications
The app has 6 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.