12.5.2. Final Remarks on Number Theory

Try these first

1. 1.

   State Fermat's Little Theorem in your own words.

   Hint

   Think about what happens when you raise numbers that fit this requirement.

2. 2.

   What is a Carmichael number? Give an example.

   Hint

   These numbers can fool primality tests!

3. 3.

   Which statement accurately describes Fermat's Little Theorem?

   • If p is prime and a is any integer
   • then a^(p-1) ≡ 0 (mod p)
   • If p is prime and a is co-prime to p
   • then a^(p-1) ≡ 1 (mod p)
   • Carmichael numbers are prime

   Hint

   Which option keeps the focus on co-primality?

4. 4.

   True or False: All composite numbers are Carmichael numbers.

   • True
   • False

   Hint

   Think about examples of composites that are not Carmichael.

5. 5.

   Given the number 561, demonstrate why it is a Carmichael number using Fermat’s Little Theorem for bases 2, 3, and 5.

   Hint

   Use Fermat's theorem for your calculations.

6. 6.

   Construct your primality testing algorithm incorporating Fermat’s theorem, listing steps you would take to strengthen it against Carmichael numbers.

   Hint

   Think about involving multiple tests!