12.3. Applications in Primality Testing

Try these first

1. 1.

   State Fermat's Little Theorem.

   Hint

   Think about what prime means.

2. 2.

   What is a pseudo prime?

   Hint

   It behaves like a prime for certain tests.

3. 3.

   What does Fermat's Little Theorem state?

   • A number raised to its modulus is always 1.
   • If p is prime
   • then a^(p-1) ≡ 1 (mod p) for a not divisible by p.
   • Only even numbers are prime.

   Hint

   Focus on primes and powers.

4. 4.

   True or False: Carmichael numbers are primes.

   • True
   • False

   Hint

   Think about what defines a prime number.

5. 5.

   Determine the number of distinct Carmichael numbers up to 1000, utilizing the properties discussed in class.

   Hint

   Check the composite nature and co-prime conditions.

6. 6.

   If we observe that b^(n-1) ≡ 1 (mod n) for various bases, how can we design a further verification step using another theorem or method?

   Hint

   Think of double-checking solutions through additional methodologies.