Hi. In this video,

we're going to prove Fermat's Little Theorem.

This theorem is a key result for cryptography using modular exponentiation operation.

This is also a key result for

fast algorithms testing whether a large integer is prime or not,

and it can also be used to make modular exponentiation even

faster than what we came up with in the previous video,

and I'm going to show you this in the end of this video.

So, the statement is very simple.

If a prime number p doesn't divide some integer a,

then a to the p minus one is equal to one modulo p. Let's prove this theorem.

Consider all p - 1 non-zero remainders modulo p: one,

two and so on up to p - 1.

So multiplying any such non-zero remainder by a is invertible,

since p doesn't divide a.

So the new remainder will also be non-zero.

So we can actually build a graph on non-zero remainders and

we draw an edge from non-zero remainder r to a times r.

Where a time r is correspond to the remainder of ar modulo p. And in such graph,

all incoming and outgoing degrees are one.

All outgoing degrees are one because we only draw

an edge from any r to a times r. This is just one edge,

and the incoming degrees are one because the multiplying by a is invertible.

And so, if there is some edge from somewhere to ar,

then it is only from r. We can just revert this multiplication by a to get r back.

So this is a particular kind of a graph where

all incoming and outgoing degrees of vertices are all equal to one.

So now, let's see what happens if we start with some remainder r,

multiplied by a, take remainder modulo p,

and repeat this many, many times.

What will happen?

So, in this graph,

we start with the vertex corresponding to remainder r,

then we go to the vertex which corresponds to a times r. From there,

we'll go to the vertex corresponding to a squared times r,

then to the a cubed times r and so on.

We're going to repeat this for sometime,

but at some point,

we have to return to some vertex where we've

already been because there is only a finite number of such vertices,

only p minus one.

So, what if we return,

for example, to these vertex.

I claim that this cannot happen. Why is that?

Well, because in this case,

this vertex woulh have incoming degree of two,

and we know that all the incoming degrees of all vertices are equal to one.

And so, this is actually not possible.

And so, the only case in which we can return and not break

this property that any incoming degree is one is if we return to the initial vertex.

So we get the cycle which starts from r,

goes to ar, a squared r and so on.

And after some l-iterations,

it returns to the same vertex r. What this means is that by multiplying r by a, l times,

we'll return to r. And this in turn the means that a to the power of l,

multiplying by a to the power l doesn't change anything,

so a to the power of l is equal to one modulo p. Now,

let's consider what would happen if we started with some different remainder r prime.

First, we'll go to a times r prime,

then to a squared r prime,

then to a cubed r prime and so on.

And then, as we already know,

at some point we'll get a cycle.

And the length of this cycle has to be the same because we

already know that a to the power of l is equal to one modulo p,

a to any smaller degree is not equal to one modulo p. And also,

we know that these two cycles won't intersect.

So they either are two same cycles or they

don't intersect because if they intersect by some one vertex,

this vertex will have incoming degree more than one,

it will have an incoming degree from first cycle and incoming edge from the second cycle.

So this is not possible,

either two cycles coincide completely or they don't intersect.

And this is key to prove the Fermat's Little Theorem.

So, we know that starting with any remainder r,

we get the cycle of some length l. And then we conclude that this means a to the power of

l is equal to one modulo p. And starting with any other remainder r prime,

we also get a cycle of the same length l. And also these cycles don't intersect.

And these cycles in total contain all p minus one non-zero remainders.

We can start with any non-zero remainder and

some cycle will contain this particular remainder.

So if there are exactly c cycles for some c,

then cl = p - 1 because each cycle has length of l that contains l remainders.

There are c cycles, they don't intersect,

so in total, they contain c times l remainders.

And from the other hand, there are exactly p minus

one non-zero remainders and all of them are in the cycle.

So, cI = p - 1.

And then a to the power of p minus one is equal to a

to the power of c times l. This we can rewrite as to

the power of l and all of this to the power of c. We know

that a to the power of l is equal to

one modulo p. So this is equal to one to the power of c,

and one to the power of c is cyclical to one modulo p.

So we proved that a to the p minus one is equal to

one modulo p. And this can be used for optimizing further modular exponentiation.

Indeed, for a number a such that p doesn't divide a,

we know that a to the power of p minus one is equal to

one modulo p. And from this it follows that for any integer n,

a to the power of n is equal to a to the power of n modulo p minus one modulo p.

Because any p minus one multiplication by a result in multiplying by one.

So instead of making many,

many useless multiplications by groups of p minus one,

we just compute the remainder of n modulo p minus one,

and do these number of multiplications by a,

and then we get the same remainder modulo p. And if number a such that p divides a,

and then a in any power will be equal to zero.

And so, this property that a to the power of n is

equal to a to the power of n modulo p minus one,

modulo p still holds.

So, actually for any integer a and any integer n,

a to the power of n is equal to a to the power of n modulo p minus

one modulo p. And it means that instead of computing very,

very large powers of a modulo p,

we can compute only powers which are up to p minus one.

If we need to compute some power which is even bigger,

we divide this power by p minus one,

compute the remainder, and then compute the corresponding power of a.