Hi. In this video,

we're going to prove Euler's Theorem that

connects Euler's Totient function with modular exponentiation.

Euler's Theorem is a generalization of Fermat's Little Theorem for non-prime numbers,

and together with modular exponentiation,

it is used to encrypt and decrypt in RSA encryption system.

So the theorem states that if integer A is coprime with integer N,

then A to the power of five N is always equal to one

modular N. So this theorem is very similar to Fermat's theorem.

For example, if N is prime,

if N is equal to B,

then we know from the previous video that 5B is equal to B minus 1.

And if we prove this Euler's Theorem,

then in the case of prime N,

we'll get that if A is coprime with B,

that is, B doesn't divide A,

A to the power of B minus 1 is equal to one modular B.

And this is indeed Fermat's Little Theorem,

which we already proved before.

Now, let's prove this generalization.

Actually, the proof is going to be very similar to the proof of Fermat's Little Theorem.

So consider all the [inaudible] remainders modular N,

which are coprime with N. So instead of nonzero remainders modular B,

we're considering the remainders which are coprime with N.

Multiplying them by A is invertible because A is coprime with N,

and we know that from the previous module.

So the new remainder will also be coprime with N after multiplying by A.

So we can again build a graph of remainders which are coprime with N,

and we can again get an edge from R to A times R modular N. And again,

we will consider this graph and consider what happens if we start with some remainder,

R, and multiply it by A many times.

And as in the previous case,

if we multiply by A again and again,

at some point it will return back, and there will be a cycle.

Because in this graph all the incoming degrees are 1,

so we have to return to some vertex where we have already been,

but it has to be the initial vertex.

So again, we will get a cycle,

as in the proof of Fermat's Little Theorem,

and the cycle has length L. It means that A to the power of L is equal to one modular L,

because multiplying by A,

L times, doesn't change anything.

So A to the L is equal to one,

and all the cycle lengths have to be the same,

equal to L, and also these cycles don't intersect.

Otherwise, some incoming degree of some vertex would be more than one.

And these cycles cover all the remainders coprime with N,

because we can start with any such remainder,

and then generate some cycle.

So either as C cycles,

each of them has length, L,

and they cover all the remainders which are coprime with N.

Then C times L must be equal to the number of such remainders,

and the number of such remainders is Euler's function, 5N.

So in end, A to the power of 5N,

is equal to A to the power of C times L,

which we can rewrite as A to the power of L,

and all this to the power of C. A to the power of L is equal to one,

so this is equal to one to the power of C,

and that is, in turn, equal to one modular N. So we proved Euler's Theorem.

In conclusion, in this last lecture of this module,

we defined modular exponentiation.

We designed a fast algorithm to compute this modular exponentiation

in logarithmic time regarding to the exponent.

We proved Fermat's Little Theorem.

We defined Euler's totient function,

and we proved Euler's Theorem,

which is a generalization of Fermat's Little theorem.

In the next module,

using all these tools,

the Fermat's Little Theorem,

the Euler's function, the Euler's Theorem,

the Chinese Remainder Theorem,

we're going to use these building blocks to learn how to do public key cryptography.

And also, we'll learn how you can make it wrong and

how to break some secret codes if someone used cryptography in a wrong way,

and you will break some secret codes yourself.

So, I'm looking forward to see you in the next module.