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

Fermat's little theorem states that if p is a prime number and if a is an integer such that p does not divide a, then ap - 1 ≡ 1 modulo p.

Fermat's Little Theorem provides a fundamental property involving prime numbers and modular arithmetic. It states that if you take a prime number 'p' and an integer 'a' that is not divisible by 'p', then raising 'a' to the power of (p-1) will yield a result that is congruent to 1 when divided by 'p'. This is written mathematically as: ap - 1 ≡ 1 (mod p). The theorem is significant because it allows for efficient calculations in number theory, especially in the fields of cryptography and primality testing.

You can think of this theorem like a special rule for a game where only certain numbers (primes) are allowed to make certain moves. If you have a number 'a' that plays well with these rules (a not divisible by p), then it will behave a certain way when you perform a calculation (multiplying it by itself multiple times), always leading you back to a recognizable outcome (which is 1 in this case).

A corollary of Fermat's theorem states that for every integer a and prime p, ap ≡ a modulo p.

The corollary to Fermat's Little Theorem extends to all integers, stating that for any integer 'a', the expression ap is congruent to 'a' when divided by a prime 'p'. This means that when you raise 'a' to the power 'p' and divide by 'p', the result will leave the same remainder as 'a' itself. This is a powerful tool for verifying primality without directly checking every integer.

Imagine you're at a party with a number of friends, and you're asked how many friends you brought with you (that’s your number 'a'). If you try to form groups of friends (doing the math with 'p' being a certain size group) and return to tell how many you had, the game allows you to say the same number 'a' instead of recounting everyone. The corollary assures you that process will always reflect your original count correctly.

To prove Fermat's theorem, we consider the first p - 1 multiples of a, showing they yield distinct non-zero remainders when divided by p.

The proof involves creating distinct multiples of 'a' (like a, 2a, ..., (p-1)a) and examining the remainders upon division by 'p'. By proving these remainders are all unique and not zero, it establishes the key aspect of the theorem: that the product taken to (p-1) modulo 'p' behaves predictably and leads to the correct conclusion of ap-1 ≡ 1 modulo p.

Think of a group of students (multiples of 'a') forming different pairs to play games (being divided by 'p'). Each pair of students results in unique outcomes (unique remainders), and no one ends up alone (no zero remainders), validating a reliable connection (the theorem). By ensuring everyone's results are distinct and consistently checking the outcomes, you can confidently say the game rules always hold true.

Fermat's theorem serves as the basis for a primality testing algorithm using randomly chosen bases to determine if a number is prime.

The theorem allows for a technique for testing the primality of numbers, where you take a number 'n' and test it against several co-prime integers ('b'). If for any chosen 'b', the condition bn-1 ≡ 1 (mod n) fails, then 'n' is composite. However, if it passes for all 'b', 'n' might be prime, but it is not guaranteed due to certain composite numbers (like Carmichael numbers) potentially passing the test.

Imagine testing if a new contestant (number 'n') can join your exclusive club (be prime) by checking their credentials (co-prime 'b's). If they fail any check, they’re out. However, some contestants might cleverly pass all checks not because they belong but because they've mastered the rules (Carmichael numbers), thus deceiving you into thinking they're legitimate members.

Carmichael numbers are special composite numbers that can pass Fermat's Little Theorem tests for all co-prime bases.

Carmichael numbers pose a challenge to primality testing because no matter which co-prime base you select, they satisfy the condition of Fermat's theorem (like 341 satisfying 2^340 ≡ 1 mod 341). This characteristic makes them pseudo primes, as they showcase that the theorem cannot always be used definitively to attest primality.

Think of Carmichael numbers as clever impostors who memorize the secret handshake and mannerisms of an elite club (the primes). No matter how many different members you ask to check their identity, these impostors would convincingly pass every test, leading you to mistakenly accept them as true members, while they are indeed non-members (composite).

--