12.3.2. Primality Testing Algorithm Limitations

Try these first

1. 1.

   What is Fermat's Little Theorem?

   Hint

   Think about how it relates to primes and modular arithmetic.

2. 2.

   Explain what a pseudo prime is.

   Hint

   Consider an example of a composite number.

3. 3.

   What does Fermat's Little Theorem state for a prime p?

   • a^(p-1) ≡ 1 (mod p)
   • a^(p) ≡ 1 (mod p)
   • p | a
   • gcd(a
   • p) = 0

   Hint

   Recall the theorem definition directly.

4. 4.

   Is 341 a pseudo prime?

   • True
   • False

   Hint

   Think about its factors.

5. 5.

   Prove that 561 is a Carmichael number by demonstrating it satisfies Fermat's theorem for all valid bases.

   Hint

   Tackle it by considering GCD conditions for 3, 11, and 17, and apply Fermat's theorem.

6. 6.

   Find a composite number greater than 100 which is not a Carmichael number and explain why it fails the Fermat test.

   Hint

   Test various bases and demonstrate a failure in at least one case.