Modular Arithmetic/Fermat's Little Theorem

Modular Arithmetic
 ← Problem Solving with Modular Arithmetic Fermat's Little Theorem Euler's Theorem → 
Example: Powers of 3

Let us look at the powers of a number under modulo arithmetic. We'll look at:

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

but it is quicker just to work out from like so:

it is quite clear that the pattern is repeating. That's because . Even without doing the calculation it is clear that the pattern has to repeat somewhere. There are at most 7 different possible numbers for so if we calculate it for 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 .
  • Pigeonholes: The seven possible remainders .

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 with a and b positive numbers. Then and we can divide both sides by to get , i.e. a repeat that happens sooner. Just a little care is needed. In modulo arithemtic 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 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 , the exponent of in cannot just be replaced by because . The ones to watch are in exponents. In expressions like and it is fine to replace the 1000 to get and or even and

Exercise: Powers of 3
  • Now your turn. Do exactly the same thing as in the example, but this time for

There is nothing really special about 3 here. We could do exactly the same exercise for other numbers with . We might reach sooner, we definitely will for , but we would still have .

We're going to 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.