Modular Arithmetic/Fermat's Little Theorem

Fermat's Little Theorem

If $p$ is a prime number and $a$ is an integer, then:

$a^{p}\equiv a{\pmod {p}}$

Example: Powers of 3 Let us look at the powers of a number under modulo arithmetic. We'll look at: $\displaystyle 3,3^{2},3^{3},3^{4}...$ and we're going to look modulo a prime number $\displaystyle p$. First we'll choose $\displaystyle p=7$. We could work out each number and then reduce, e.g. $\displaystyle 3^{4}=3\times 3\times 3\times 3=81\equiv 4\,\mathrm {mod} \,7$ $\displaystyle 3^{5}=3\times 3\times 3\times 3\times 3=243\equiv 5\,\mathrm {mod} \,7$ but it is quicker just to work out $\displaystyle 3^{n+1}$ from $\displaystyle 3^{n}$ like so: $\displaystyle 3^{1}=3\quad \quad \quad \equiv 3\,\mathrm {mod} \,7$ $\displaystyle 3^{2}=3\times 3=9\equiv 2\,\mathrm {mod} \,7$ $\displaystyle 3^{3}=2\times 3=6\equiv 6\,\mathrm {mod} \,7$ $\displaystyle 3^{4}=6\times 3=18\equiv 4\,\mathrm {mod} \,7$ $\displaystyle 3^{5}=4\times 3=12\equiv 5\,\mathrm {mod} \,7$ $\displaystyle 3^{6}=5\times 3=15\equiv 1\,\mathrm {mod} \,7$ $\displaystyle 3^{7}=1\times 3=3\equiv 3\,\mathrm {mod} \,7$ $\displaystyle 3^{8}=3\times 3=9\equiv 2\,\mathrm {mod} \,7$ it is quite clear that the pattern is repeating. That's because $\displaystyle 3^{6}\equiv 1\,{\bmod {\,}}7$. Even without doing the calculation it is clear that the pattern has to repeat somewhere. There are at most 7 different possible numbers for $\displaystyle 3^{n}\,{\bmod {\,}}7$ so if we calculate it for $\displaystyle n=1,2,3,4,5,6,7,8$ there has to be a repeated answer somewhere in there. Note: This is a use of the pigeonhole principle - there are more pigeons than pigeonholes, so one pigeonhole must contain two pigeons. If you are interested, click on the pigeon icon to read more about the pigeonhole principle: Pigeons: Powers of 3 $\displaystyle {\bmod {\,}}7$. Pigeonholes: The seven possible remainders $\displaystyle {\bmod {\,}}7$. Once a number is repeated the sequence from there on must be the same as before, from the first occurrence of that number. We can even see that we will get a 1 followed by a 3 as where the repeat first happens. Why? Suppose we have some repeated number, in other words $\displaystyle 3^{a}\equiv 3^{a+b}$ with a and b positive numbers. Then $\displaystyle 3^{a}\equiv 3^{a}3^{b}$ and we can divide both sides by $\displaystyle 3^{a}$ to get $\displaystyle 1\equiv 3^{b}$, i.e. a repeat that happens sooner. Just a little care is needed. In modulo arithmetic it is not always allowed to divide by a common factor. We're allowed to do that division here because we earlier established it for modulo a prime using Euclid's algorithm. We know that $\displaystyle 3^{n}\,\mathrm {mod} \,7$ is not zero since otherwise 3 would be a factor of 7 and 7 is prime.

Something to watch out for with modular arithmetic, we cannot just reduce numbers wherever we see them. For example working $\displaystyle {\bmod {\,}}7$, the exponent of $\displaystyle 8$ in $\displaystyle 3^{8}$ cannot just be replaced by $\displaystyle 1$ because $3^{8}\neq 3^{1}\,{\bmod {7}}$. The ones to watch are in exponents. In expressions like $\displaystyle 1000x\,{\bmod {7}}$ and $\displaystyle (1000+x)\,{\bmod {7}}$ it is fine to replace the 1000 to get $\displaystyle 6x\,{\bmod {7}}$ and $\displaystyle (6+x)\,{\bmod {7}}$ or even $\displaystyle -x\,{\bmod {7}}$ and $\displaystyle (x-1)\,{\bmod {7}}$.

Exercise: Powers of 3 Now your turn. Do exactly the same thing as in the example, but this time for $\displaystyle p=11$

There is nothing special about 3 here. We could do exactly the same exercise for other numbers $\displaystyle a$ with $\displaystyle a=1,2,4,5\,or\,6$. We might reach $\displaystyle a^{n}\equiv 1$ sooner, we definitely will for $\displaystyle a=1$, but we would still have $\displaystyle a^{(p-1)}\equiv 1\,{\pmod {p}}$.

We will prove this several ways. The reason for making such a meal out of proving it, is that it helps to see different ways of proving a result. In this case, it's mainly a way to show the different notation that can be used. The third variant of the proof will also introduce the concept of multiplicative functions, which will be important later on.