12.2. Understanding Fermat's Little Theorem

Try these first

1. 1.

   State Fermat's Little Theorem.

   Hint

   Recall the conditions regarding p and a.

2. 2.

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

   Hint

   Think about the factors of the numbers.

3. 3.

   What does Fermat's Little Theorem state?

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

   Hint

   Think about the prime’s relation with its multiples.

4. 4.

   Carmichael numbers behave like primes under which condition?

   • True
   • False

   Hint

   Recall the definition of Carmichael numbers.

5. 5.

   Given a prime p = 17, find an integer a that satisfies Fermat's Little Theorem, and prove it.

   Hint

   Reduce 10^(16) step by step modulo 17.

6. 6.

   For the Carmichael number 561, show all bases up to 10 satisfy Fermat's Little Theorem.

   Hint

   Recall the properties of modular arithmetic.