12.1.4. Proof of 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 (i.e., a is co-prime to p), then ap - 1 ≡ 1 modulo p.

Fermat's Little Theorem provides a relationship between prime numbers and integers. Specifically, it states that if you take any integer 'a' that is not divisible by a prime number 'p', raising 'a' to the power of (p-1) will yield a result that is congruent to 1 when divided by 'p'. This means that the remainder of the division of a^(p-1) by p is 1. It's significant because it allows us to make deductions about numbers and perform tests for primality.

Think of Fermat's Little Theorem as a special rule in a game where you can only use certain numbers (the prime numbers) in a particular way. If you follow the rule and do things correctly (use a number a that isn't divisible by p), you will always land back on a certain 'safe spot' (1) when you play by raising it to a specific power.

Assuming the theorem is true, a corollary is that ap ≡ a modulo p for every integer a.

The corollary expands the application of Fermat's Little Theorem to all integers, not only those co-prime to p. If 'a' is divisible by 'p', both a and a^p will leave a remainder of 0 when divided by 'p'. On the other hand, if 'a' is not divisible by 'p', we can use the theorem to conclude that a^p is congruent to a modulo p. Both situations showcase the theorem's utility in modular arithmetic.

Imagine you are calculating the time on a clock. If it's 3 o'clock, and you move forward 3 hours, you end up at 6 o'clock. But if you made that move with 12 hours in mind (the next day), you'd still be at 3 o'clock (12 o'clock wraps around). Similarly, Fermat's theorem shows that whether 'a' fits neatly into 'p' or not, you can always tell where you'll end up after the 'moves' defined by the theorem.

To prove Fermat's Little Theorem, consider the first (p - 1) multiples of a, namely, 1 times a, 2 times a, ..., (p - 1) times a. All these multiples are claimed to give different non-zero remainders when divided by p.

The proof begins by assuming that you have the multiples of 'a' from 1 to (p - 1). The claim is that these multiples modulo 'p' will yield distinct values. We will prove this by contradiction: if two multiples give the same remainder, we can show that this leads to a logical inconsistency, thus proving that they must be different. If 'a' and 'p' are coprime, it prevents any 'collisions' in remainders, allowing us to conclude our proof.

Imagine a row of lockers, numbered from 1 to p-1, where each locker can only hold one unique item. If you tried to put two of the same item (two of the same multiple of a) in different lockers but they ended up in the same one, you would quickly realize it's impossible because that locker can only hold one item. This demonstrates why all multiples of 'a' must be different when you divide by 'p'.

The conclusion is that ap - 1 ≡ 1 modulo p, which confirms Fermat's Little Theorem. The theorem is powerful for various applications, notably in primality testing.

The conclusion drawn from the proof confirms that if 'a' is coprime to 'p', then raising it to the power 'p-1' will yield a remainder of 1 when divided by 'p'. This theorem not only simplifies certain calculations but also allows for effective testing of whether numbers are prime, providing significant utility in both theoretical and applied number theory.

Understanding Fermat's Little Theorem is like having a powerful calculator in your toolbox for solving math problems in number theory. It allows you to quickly verify calculations and determine the nature of numbers, facilitating quicker and easier work when dealing with primes, much like having a shortcut to your favorite destination.

--