Exercise · ZW-FERMAT-PRIMALITY-TEST-009 · ★★☆ Intermediate
For n = 21 and a = 2, what result does the Fermat test give?
Choose one option.
Show answer
- A. It concludes that 21 is composite, since \( 2^{20} \equiv 4 \pmod{21} \)
Explanation
Computing \( 2^{20} \bmod 21 \) gives 4 (since \( 2^6 \equiv 1 \pmod{21} \) and \( 2^{20} = 2^{18}\cdot 2^2 \equiv 4 \)), which is not 1; the test declares 21 composite.
Review the concept: Fermat primality test
The Fermat primality test is a probabilistic criterion for an integer \(n>1\): it declares \(n\) composite if, for some base \(a\) coprime to \(n\), the power \(a^{n-1}\) is not congruent to 1 modulo \(n\).
\[a^{n-1} \equiv 1 \pmod{n}\]
More practice problems: fermat primality test
- ZW-FERMAT-PRIMALITY-TEST-001 What does a^n-1 not≡ 1 pmodn with gcd(a, n) = 1 tell you?
- ZW-FERMAT-PRIMALITY-TEST-002 What is 2^4 bmod 15 ?
- ZW-FERMAT-PRIMALITY-TEST-003 What is the name of the test that uses a^n-1 ≡ 1 pmodn to detect composites?
- ZW-FERMAT-PRIMALITY-TEST-004 What condition must the base a satisfy in the Fermat test?
- ZW-FERMAT-PRIMALITY-TEST-005 If n is prime and gcd(a, n) = 1, what holds?
- ZW-FERMAT-PRIMALITY-TEST-006 Compute 3^6 bmod 7 and state whether the test with base 3 concludes that 7 is prime or composite.
- ZW-FERMAT-PRIMALITY-TEST-007 Use the test with base 2 for n = 9. What do you conclude?
- ZW-FERMAT-PRIMALITY-TEST-008 For n = 13 and a = 5, what is the remainder of 5^12 bmod 13 ?
← ZW-FERMAT-PRIMALITY-TEST-008 ZW-FERMAT-PRIMALITY-TEST-010 →