12.5.1. Example of a Carmichael Number (561)

Try these first

1. 1.

   State Fermat's Little Theorem.

   Hint

   Think about the relation between primes and modular arithmetic.

2. 2.

   What is an example of a Carmichael number?

   Hint

   Recall that it misleads primality tests while being composite.

3. 3.

   What does Fermat's Little Theorem state?

   • If p is prime
   • then a^p ≡ 0 (mod p)
   • If p is prime
   • then a^(p-1) ≡ 1 (mod p)
   • If a is even
   • a^2 is even

   Hint

   Remember the key formula in the theorem.

4. 4.

   Is 561 a prime number?

   • True
   • False

   Hint

   Recollect the definition of prime numbers.

5. 5.

   Prove that if a number n satisfies b^(n-1) ≡ 1 for all bases b co-prime to n, then n is a Carmichael number.

   Hint

   Use the prime factorization of n and analyze the implications for all bases.

6. 6.

   In a practical application, explain how one could modify a basic primality test to take Carmichael numbers into account.

   Hint

   Consider the diversity of bases used in testing.