Hi. In this video,

we're going to study Euler's Totient Function.

This is a key function for the RSA encryption,

which we're going to study in the next module.

It is easy to compute if factorization of integer n is known,

and no fast algorithms are known to compute it in factorization of n is unknown,

and no fast algorithms are known for factorization of integers,

and this is actually why we can use it to do some cryptographic algorithms,

because we want functions which are easily computable,

if we know something,

but which are very hard to compute if you don't know this secret.

This is the main foundation of cryptography.

The foundation of cryptography, basically,

is not in something we can do very well but in something we cannot do well,

and integer factorization is a problem for which humanity currently don't

know any fast algorithms and this is why we can cipher something,

and then be almost sure that no one can decipher it

unless there's someone actually knows how to factorize big integers fast.

For our knowledge, no one knows how to do

that and this is what allows us to do cryptography.

What is Euler's Totient Function?

It just counts integers between 0 and n- 1,

which are coprime with n. So,

Φ(n) is the number of such coprime integers

between remainders module n. Let's consider some examples,

for n=1, 0 is coprime with 1.

So Φ(1) is 1.

Well, it is actually a special case

of whether 0 is coprime with 1 or not because you know,

every integer divides 0,

and what does it mean?

That 0 is coprime with any number,

or basically the greatest common divisor of 0 and 1 is still 1,

because 1 only has one divisor 1.

So in this case indeed 0 is coprime with 1,

and there are no other remainders modulo 1,

so Φ(1) is equal to 1.

For n= 2, 0 is not coprime with 2,

because the greatest common divisor of 0 and 2 is 2,

and it is bigger than 1, and so 0 is not coprime with 2,

but 1 is coprime with 2.

So Φ(2) = 1,

because there is one number less than 2 which is coprime with 2.

3, 1 and 2,

are coprime with 3,

while 0 is not coprime with any number bigger than 1,

because the greatest common divisor of 0 and integer n is equal to

n. If n is more than 1 then 0 and n are not considered coprime.

So Φ(3) = 2,

because of 1 and 2 are coprime and 0 is not coprime with 3.

And for any constant, it turns out that 1, 3,

7 and 9 are all the integers less than 10 which are coprime with 10.

Others are either even or they can be divided by Φ.

So, others are not coprime with 10.

And so Φ(10) = 4.

Now let's see how to compute Euler's Totient Function for some particular cases.

For example, if p is prime then I say,

Φ(p) = p - 1. Why is that?

Well, zero is not coprime with p,

because p is more than one,

and their greatest common divisor is p,

which is more than 1, and all the other remainders, 1, 2,

3 and so on up to p-1,

of course they are coprime with p because p is prime.

So Φ(p)=p - 1,

and this is easy case.

Another case is when our integer n is a product of two different primes.

If p and q are primes and they are different then I say that

Euler's function of p times q is equal to (p -1) (q-1).

So, where to get this formula from.

So let us consider all the pq possible remainders modulo pq,

0, 1, 2 and so on up to pq -1.

We know by the Chinese Remainder Theorem,

from the previous lesson,

that each such remainder corresponds to some pair of remainders ( rp, rq),

rp modulo p, and rq modulo q.

So let us arrange all the pq remainders modulo pq

in the rectangular table with p rows and q columns.

Sides that remainder are will go into the cell with the number rp on the row,

and with number rq on the column.

We know that each remainder r corresponds to a unique pair.

So each remainder will go into a separate cell.

So now where are the remainders which are coprime with pq?

Those remainders are the remainders which don't have p or q among their divisors,

because p and q are the only divisors of pq,

that can be common divisors with r. So if r is coprime with pq,

then its remainder modulo p and modulo q must be non-zero.

So in this particular rectangular table,

all these remainders are in the rectangle highlighted by orange.

These are the cells which have row numbers from 1 to p - 1,

so non-zero row number,

and column numbers from 1 to q -1, non-zero column numbers,

because all the numbers in

the 0 row they can be divided by p so they are not coprime with pq.

All the numbers in the 0 column can be divided by q.

They're not again coprime with pq and

all the remainder is in this smaller rectangle p -1 times q - 1,

are indeed coprime with pq,

and so the number of such remainders,

number of such pairs,

is p -1 times q - 1,

and this is what we wanted to prove.

This is the value of Euler's Totient Function for n= pq.

And in the next video,

we're going to prove Euler's theorem that

connects Euler's Totient Function with modular exponentiation.