Exercise · ZW-FERMAT-PRIMALITY-TEST-006 · ★★☆ Intermediate
Compute \( 3^{6} \bmod 7 \) and state whether the test with base 3 concludes that 7 is prime or composite.
Choose one option.
A 6, concludes that 7 is composite B 3, concludes that 7 is prime C 0, concludes that 7 is prime D 1, does not conclude composite (consistent with prime) Show answer D. 1, does not conclude composite (consistent with prime)← Back to the question
Explanation Since \( 3^6 = 729 = 104\cdot 7 + 1 \), the remainder is 1; the congruence holds and the test does not rule out primality.
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