12.1. Discrete Mathematics

Try these first

1. 1.

   What is Fermat's Little Theorem?

   Hint

   Think about the relationship between primes and powers.

2. 2.

   State the corollary of Fermat's Little Theorem.

   Hint

   Consider how division by p affects powers.

3. 3.

   What does Fermat's Little Theorem state?

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

   Hint

   Think about congruence relations with primes.

4. 4.

   True or False: Carmichael numbers pass Fermat's theorem condition for every base.

   • True
   • False

   Hint

   Consider definitions of pseudo primes.

5. 5.

   Demonstrate that 623 is not prime using Fermat’s theorem and explain the reasoning.

   Hint

   Use several bases to test the true nature of 623.

6. 6.

   Using Fermat’s theorem, test whether 341 can be declared prime given various bases and show examples.

   Hint

   Check bases coprime with 341; recall 341 = 11 * 31.