12.1.4. Proof of Fermat's Little Theorem

Try these first

1. 1.

   State Fermat's Little Theorem in your own words.

   Hint

   Think about what happens when you take a large exponent!

2. 2.

   What does it mean for two numbers to be co-prime?

   Hint

   Consider examples of small integers!

3. 3.

   What does Fermat's Little Theorem state?

   • a^(p) ≡ 1 mod p
   • a^(p-1) ≡ 1 mod p
   • a^(p+1) ≡ 0 mod p

   Hint

   Focus on what happens when a is raised to the power of p-1.

4. 4.

   True or False: All pseudo primes satisfy Fermat's little theorem for every base.

   • True
   • False

   Hint

   Reflect on the nature of Carmichael numbers.

5. 5.

   Prove that 13 is a prime using Fermat's Little Theorem.

   Hint

   Use several examples of a and compute explicitly.

6. 6.

   Find a Carmichael number greater than 561.

   Hint

   Check divisibility and apply Fermat's theorem multiple times!