12.1.1. Introduction to Fermat’s Little Theorem and Primality Testing

Try these first

1. 1.

   What is Fermat's Little Theorem?

   Hint

   Focus on the relationship between primes and coprime integers.

2. 2.

   Give an example of two coprime numbers.

   Hint

   Check their prime factors to see if they share any.

3. 3.

   What does Fermat's Little Theorem state?

   • a) It applies only to even numbers.
   • b) If p is prime
   • a^(p-1) ≡ 1 (mod p) for coprime a.
   • c) All composite numbers are prime.
   • d) Only prime squares satisfy it.

   Hint

   Think of relationships between primes and their determinants.

4. 4.

   True or False: Carmichael numbers can pass Fermat's test for any base.

   • True
   • False

   Hint

   Recall definitions of Carmichael numbers and their properties.

5. 5.

   Prove that there exist composite numbers that are Carmichael numbers. Give an example.

   Hint

   Investigate how the prime factorization relates to Fermat’s conditions.

6. 6.

   If you have an arbitrary integer n that is not prime, suggest a primality test using Fermat's theorem.

   Hint

   Identify bases that offer the best logical coverage in the integer space.