Modular Arithmetic/Fermat's Little Theorem

Template:NavigationTemplate:Calculus/DefTemplate:ExampleRobox Let us look at the powers of a number under modulo arithmetic. We'll look at:

$3,3^2,3^3,3^4...$

and we're going to look modulo a prime number $p$. First we'll choose $p=7$. We could work out each number and then reduce, e.g.

$3^4=3\times 3\times 3\times 3=81\equiv 4\mathrm{m}\mathrm{o}\mathrm{d}7$

$3^5=3\times 3\times 3\times 3\times 3=243\equiv 5\mathrm{m}\mathrm{o}\mathrm{d}7$

but it is quicker just to work out $3^{n+1}$ from $3^n$ like so:

$3^1=3\equiv 3\mathrm{m}\mathrm{o}\mathrm{d}7$

$3^2=3\times 3=9\equiv 2\mathrm{m}\mathrm{o}\mathrm{d}7$

$3^3=2\times 3=6\equiv 6\mathrm{m}\mathrm{o}\mathrm{d}7$

$3^4=6\times 3=18\equiv 4\mathrm{m}\mathrm{o}\mathrm{d}7$

$3^5=4\times 3=12\equiv 5\mathrm{m}\mathrm{o}\mathrm{d}7$

$3^6=5\times 3=15\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}7$

$3^7=1\times 3=3\equiv 3\mathrm{m}\mathrm{o}\mathrm{d}7$

$3^8=3\times 3=9\equiv 2\mathrm{m}\mathrm{o}\mathrm{d}7$

it is quite clear that the pattern is repeating. That's because $3^6\equiv 1mod7$. Even without doing the calculation it is clear that the pattern has to repeat somewhere. There are at most 7 different possible numbers for $3^{n}mod7$ so if we calculate it for $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:

Template:Phprinciple

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 $3^a\equiv 3^{a+b}$ with a and b positive numbers. Then $3^a\equiv 3^a{3}^b$ and we can divide both sides by $3^a$ to get $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 $3^n\mathrm{m}\mathrm{o}\mathrm{d}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 $mod7$, the exponent of $8$ in $3^8$ cannot just be replaced by $1$ because $3^8\ne 3^{1}mod7$. The ones to watch are in exponents. In expressions like $1000xmod7$ and $(1000+x)mod7$ it is fine to replace the 1000 to get $6xmod7$ and $(6+x)mod7$ or even $-xmod7$ and $(x-1)mod7$.

Template:ExerciseRobox

• Now your turn. Do exactly the same thing as in the example, but this time for $p=11$

There is nothing special about 3 here. We could do exactly the same exercise for other numbers $a$ with $a=1,2,4,5or6$. We might reach $a^n\equiv 1$ sooner, we definitely will for $a=1$, but we would still have $a^{(p-1)}\equiv 1(\mathrm{mod}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.