Abstract Algebra: Theory and Applications · Problem 7.5.2

Algebraic Coding Theory — Thomas Judson

Mathematics — Abstract Algebra · primality-testing-pseudoprimes

Problem

Primality Testing. Recall Fermat's Little Theorem from Chapter 6. Let

p

be prime with

\gcd(a, p) = 1

. Then

a^{p-1} \equiv 1 \pmod{p}

. We can use Fermat's Little Theorem as a screening test for primes. For example, 15 cannot be prime since

2^{15-1} \equiv 2^{14} \equiv 4 \pmod{15}.

However, 17 is a potential prime since

2^{17-1} \equiv 2^{16} \equiv 1 \pmod{17}.

We say that an odd composite number

n

is a pseudoprime if

2^{n-1} \equiv 1 \pmod{n}.

Which of the following numbers are primes and which are pseudoprimes? (a) 342 (b) 811 (c) 601 (d) 561 (e) 771 (f) 631