12.1.2. Fermat's Little Theorem

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 (denoted as p ∤ a), then a^(p-1) ≡ 1 (mod p). This hold true for every integer a that is co-prime to p.

Fermat's Little Theorem is a fundamental theorem in number theory concerning prime numbers. It establishes that if you have a prime number p and an integer a that is not divisible by p, then when you raise a to the power of (p-1), the result will leave a remainder of 1 when divided by p. This means a^(p-1) is congruent to 1 modulo p, signifying a relationship between the integer a and the prime p.

Think of a club with p members who can each wear a unique badge (representing their integer a). If a member can successfully borrow the club's resources (such as a cake for the party) without breaking any club rules (not divisible by the number of members), they can be assured that their share of the resources will always leave them with at least one piece of cake (the remainder 1) after the party. This theorem guarantees that as long as they follow the rules, they will always receive their share.

An interesting corollary of this theorem is that a^p ≡ a (mod p) holds for every integer a and prime p. The proof can be divided into two cases based on whether p divides a or not.

The corollary extends the application of Fermat's Little Theorem by stating that for any integer a and prime p, raising a to the p-th power gives a result that is congruent to a modulo p. This means that if a is divisible by p, the remainders when a and a^p are divided by p are both 0. If a is not divisible by p, we can leverage Fermat's theorem to show that this equality still holds true, ultimately resulting in a congruency relationship.

Imagine you’re counting how many friends are attending a party where there are p seats at the table. If you have a group of friends represented by a (like '5'), when it's time to sit down for dinner (p), the way they sit down (a raised to the p) should still tell you the same number of friends (how many are actually present, or 'congruence') modulo the number of seats. So whether they eat sitting at least 0 chairs or if the number is greater, the count will always relate back to how many friends you expect based on the seating constraint.

To prove Fermat's Little Theorem, we consider the first p - 1 multiples of a: a, 2a, 3a, ..., (p-1)a, which yield distinct non-zero remainders when divided by p. We show that assuming two distinct multiples yield the same remainder leads to a contradiction.

The proof employs a contradiction approach. By assuming that any two multiples of a give the same remainder when divided by p, one can derive that p must divide the difference between the indices of these multiples. Since p is a prime number and does not divide a, it must follow that the multiples are distinct and their remainders must also be distinct non-zero values. This ensures that all multiples remain unique under modulo p.

Imagine a lineup of students waiting to board a bus. Each student holds a unique ticket number (the multiples of a) and the bus can only take a certain number of students (p). If two students claim to have the same ticket number (the same remainder), it would imply that there aren't enough ticket numbers for everyone (a contradiction), hence proving all students have unique tickets. Just like ticket numbers, Fermat’s theorem ensures that remainders from distinct multiples remain unique.

Fermat's Little Theorem has applications in computing values quickly modulo a prime p and forms the basis for primality testing algorithms.

The theorem is extremely handy not just for theoretical computations but also in practical applications like modular exponentiation, which appears in cryptography and number theory. By understanding that operations can be simplified using the theorem, computations involving large integers can be quickly reduced, making it efficient and less resource-intensive.

Think of baking a batch of cookies for a large number of friends. Instead of calculating how much sugar, flour, and butter you need for each individual cookie based on a complex recipe (a large number), you can use Fermat’s approach to split the total into manageable portions for each group of friends where the combined portions yield the same tasty result under simpler adjustments. This way, you can efficiently prepare in bigger batches without losing out on the quality of each cookie.

Carmichael numbers are composite numbers that satisfy Fermat's conditions for all bases, thus failing primality tests based on Fermat's Little Theorem.

Carmichael numbers present a challenge to the tests for primality derived from Fermat's theorem. These are special composite numbers that behave deceptively like primes – any base selected will end up satisfying the congruence condition of Fermat’s theorem, which could mislead a primality testing algorithm into declaring them as primes when they are actually composite.

Think of a security guard at a party checking IDs for age verification (i.e., testing if someone is old enough to enter). All party crashers imitate looking like they belong, flashing fake IDs (Carmichael numbers) that end up passing the test. The guard, relying on this simplistic check (Fermat's theorem based test), lets them in thinking they are legitimate guests while they are actually troublemakers. This illustrates the inherent flaw in a system relying solely on an imperfect criterion.

--