12.2. Understanding Fermat's Little Theorem

Hello everyone, welcome to this lecture, so the plan for this lecture is as follows: in this lecture, we will discuss about Fermat's little theorem, and we will see its application to primality testing, and we will also discuss about Carmichael numbers. So let us begin with Fermat's little theorem so, the theorem says that, if p is a prime number and if a is an integer such that p does not divide a. So, this notation means does not divide: ∤, in other words, a is co-prime to p, then the theorem says that ap - 1 ≡ 1 modulo p. And this is true for every integer a, which is co-prime to p. So, that is the Fermat's little theorem attributed to Fermat.

Fermat's Little Theorem states a fundamental principle in number theory regarding prime numbers. It tells us that if you have a prime number (let's call it 'p') and an integer 'a' that is not divisible by 'p' (meaning 'a' is co-prime to 'p'), then when you raise 'a' to the power of (p-1) and divide by 'p', the remainder will be 1. This means mathematically, ap - 1 ≡ 1 (mod p). This theorem serves as an essential building block in number theory and has applications such as checking the primality of numbers. Essentially, this statement confirms a certain behavior of integers concerning prime numbers, making it a 'theorem' in mathematical terms.

Think of this theorem like a special password system, where 'p' is like a unique key and 'a' is any number you want to use. If your number 'a' does not share any factors with your key 'p', after using your key to lock (raise a to the power of p-1) the number, you should always be able to unlock it (get a remainder of 1) when you divide by your key. This system ensures that numbers behave consistently when interacting with primes.

So, assume for the moment that this theorem statement is true. The corollary is ap ≡ a modulo p for every integer a and prime p. And we can divide the proof into cases depending upon whether p│a or not. If p│a, then since a is divisible by p any multiple of a is also divisible by p. So hence, ap is completely divisible by p. And that means I can say that ap gives you the same remainder, which a gives you on getting divided by p namely the remainder 0. Whereas if p ∤ a, then we can apply the Fermat's little theorem.

This corollary of Fermat's Little Theorem states that for any integer 'a' and a prime number 'p', if you take 'a' raised to the power of 'p' and reduce it modulo 'p', you should get the same result as simply reducing 'a' modulo 'p'. It has two cases: first, if 'p' divides 'a' (meaning 'a' is divisible by 'p'), then both ap and 'a' will give a remainder of 0 when divided by 'p'. In the second case, if 'p' does not divide 'a', we can use Fermat's theorem to show that ap ≡ a (mod p) again.

Imagine you have a basket containing fruits (represented by 'a'). If the total number of fruits is divisible by ten (the prime 'p'), then when you count them in groups of ten, you won't have any leftover fruits (the remainder is zero). However, if the total number of fruits is not divisible by ten, arranging them into groups of ten will still mean you can only have either no leftovers or exactly the same number of leftover fruits as you started with, since everything aligns in the same pattern under modular reduction.

So now let us come back to Fermat's little theorem and we prove it. So, we want to prove that you take any integer a, which is co-prime to p, then ap - 1 ≡ 1 modulo p that is what we want to prove. The proof is as follows: consider the first p - 1 multiples of a, namely, 1 times a, 2 times a, ..., p - 1 times a. The claim is that all these multiples of a give you distinct, non 0 remainders when divided by p.

The proof of Fermat's Little Theorem relies on creating distinct multiples of 'a' (from 1 to p-1). These multiples, when divided by 'p', will yield unique non-zero remainders. The proof utilizes contradiction: if two distinct multiples of 'a' yielded the same remainder, we'd find that 'p' divides the difference of those two multiples, contradicting the assumption that 'a' is co-prime with 'p'. Since the multiples must give distinct remainders, we can conclude that they can all be reduced modulo 'p', which lays the groundwork necessary to derive that ap - 1 ≡ 1 (mod p).

Think of it like having a unique set of keys (the multiples of 'a'). Each key opens a different locker (the remainders when divided by 'p') and because you have a unique key for each locker, no two keys can open the same locker, which shows that they remain distinct and non-zero.

So now let us see some of the applications of this theorem it has this Fermat's little theorem has got tremendous applications. For instance, if I want to compute the value of 7222 modulo 11 using Fermat's little theorem, I can substitute a = 7 and p = 11 since GCD(7, 11) is 1, then 710 ≡ 1 modulo 11 provides a shortcut for calculating larger exponents by breaking them down.

Fermat's Little Theorem can be used to simplify the calculation of powers when computing numbers modulo a prime. For example, by knowing that 710 ≡ 1 (mod 11), you can reduce the exponentiation of '7' to more manageable parts (like calculating 7222 = 710 * 710 * 710 * 72) leading to quick results without high computational burden. Each term can be calculated modulo '11' resulting in easy multiplication of 1's and the last term, providing a quick method for computations in modular arithmetic.

Imagine you're piling up blocks, and each block can only be stacked up to a certain height (which represents the prime number). Instead of trying to build a giant stack all at once, you can build smaller stacks of blocks that meet the height requirement without it toppling, giving you manageable sections to work with instead of one huge, cumbersome tower.

--