0:00

From previous lessons, we've learned that the exponent in

Â a modular expression doesn't live in the same modular world as the expression itself.

Â We've also mentioned, largely in parsing,

Â that the world the exponent lives in is the totient of the modulus the expression lives

Â in provided that the base is relatively prime to the expression modulus.

Â And that the totient of a positive integer, N,

Â is the number of positive integers that are both less than and relatively prime to N.

Â This claim rests on what is known as Euler's Totient theorem,

Â that states that, any integer relatively prime to the modulus is

Â congruent to 1 when raised to the power of the totient of the modulus.

Â In this lesson, we're going to walk through a proof of Euler's totient theorem.

Â We are not going to develop Euler's totient function,

Â which is the function that returns the totient of a positive integer.

Â We'll do that in the next lesson.

Â In part, this is to keep the length of the lessons more

Â manageable but mostly it's to emphasize that

Â these are two different and only peripherally related topics.

Â As we go through the proof,

Â don't be too concerned about understanding

Â where the motivation for the approach comes from.

Â The basic approach itself is a quite common technique,

Â to find two sets based on certain properties

Â and then show that each set is a subset of the other,

Â which then proves that the two sets are in fact identical.

Â And then, you draw some conclusions based on that equality.

Â Picking the properties used to define the sets is where the art comes in.

Â And, Euler's totient theorem is a generalization of Fermat's little theorem.

Â Something that Pierre de Fermat himself,

Â one of history's greatest mathematicians,

Â failed to prove when he first proposed it in 1640.

Â Since then, several proofs have been devised from several branches of mathematics.

Â So, don't be disappointed if the reasoning that led to this approach escapes you.

Â It's more than sufficient to focus on understanding the validity of each step.

Â Personally, I don't know what the original motivation for the approach was.

Â Perhaps, it was pure inspired genius.

Â Definitely a possibility when talking about someone like Leonard Euler.

Â But, I would imagine that,

Â as is often the case,

Â astute empirical observations reveal the relationship

Â between the moduli of the exponent and that of the overall expression.

Â And, that likely guided many attempts to establish

Â a mathematical basis for the already observed relationship.

Â What is preserved in the history and what we will walk through

Â today is merely the one that panned out.

Â Euler's totient theorem claims that X raised to the totient of N

Â is congruent to one moduli N for any X that is relatively prime to N and where,

Â as we've already stated,

Â the totient of N is the size of the set, S,

Â consisting of all positive integers that are both less than and relatively prime to

Â N. Don't gloss over the requirement

Â that the base and the modulus must be relatively prime.

Â This is an easy and commonly forgotten caveat.

Â You can't just blindly reduce the exponent

Â by the totient of the modulus and be done with it.

Â Let's hold off dealing with whether the claim is valid and first make sure

Â we understand what is being claimed via a couple of simple examples.

Â Let's choose N=21 is our modulus.

Â What is the totient of 21?

Â We can just list the positive integers that are less than 21,

Â keeping only those that are not divisible by either 3 or 7.

Â We find that there are 12 of them.

Â So, the totient of 21 is 12.

Â Now, let's pick a value for X that is relatively prime to 21. Let's use 5.

Â The theorem therefore claims that 5 to the twelfth power is

Â congruent to 1 in a mod 21 world. Is it?

Â Let's practice our square and multiply technique and find out.

Â Our exponent of 12 has a binary representation of 1,1, 0,0.

Â So, we need to multiply 5 to the eighth and 5 to the fourth.

Â We can square and reduce our base of 5 until we get to 5 to the eighth,

Â then we just use the ones that we need in.

Â As expected, the result is congruent to 1.

Â But what about that caveat that the base has to be relatively prime to the modulus?

Â This is not just some form of fine print in the proof.

Â The claim simply does not hold if this constraint is not respected.

Â Let's repeat our previous example,

Â except use X=6, which is not relatively prime to 21.

Â Thus, 6 to the 12 is not congruent to 1 in a mod 21 world.

Â But that's fine because the claim doesn't claim that it is.

Â I've stressed this a few times already and

Â I'll revisit it from time to time in the future.

Â This is a critically important restriction and ignoring it can and has

Â resulted in crypto packages that just don't work.

Â Okay, so, now we get to the proof itself.

Â Our proof involves eight steps which can be summarized as follows.

Â First, we'll create a set, S,

Â of all positive integers less then and relatively prime to the modulus.

Â Next, we will count the number of elements in this set

Â and assign that to a parameter M. Then,

Â we will arbitrarily pick an integer that is also relatively prime to the modulus.

Â In our fourth step,

Â we'll create a second set of integers by multiplying each element of our

Â first set by X and reducing the product moduli N. Next,

Â we'll establish four properties that are two sets possess.

Â Those properties will let us show that the two sets are in fact identical.

Â In the seventh step,

Â we'll form the products of all the members in each set

Â separately based on how the two sets were created.

Â Finally, we will use the fact that these two products must be

Â equal to establish the relationship claimed by Euler's totient theorem.

Â At each step, we will work both with

Â generic algebraic relationships and also with a specific concrete example.

Â So, without further ado let's get going.

Â We've already done the first few steps in our earlier examples so,

Â there's not much to be gained belaboring these points.

Â For our first step, we define a set, S,

Â that consists of all positive integers K,

Â such that K is less than N and relatively prime to it.

Â For a concrete example,

Â let's use our old friend n=21 which results in this set for S. In this step,

Â we merely assign the number of elements in set S,

Â known as its cardinality,

Â to the parameter M. For our example, M=12.

Â We'll arbitrarily call this number the totient of N. Okay.

Â It's not really very arbitrary.

Â But, the point is that totient is nothing more than

Â a made up name for the size of the set of integers constructed this way.

Â The Greek character, phi,

Â is often used for this function name but when we don't have access to

Â Greek fonts we usually just use either TOT or the word totient as the function name.

Â Next, we'll pick any integer X with the only restriction that it

Â be relatively prime to N. Notice that this restriction,

Â while allowing X to be negative,

Â precludes it from being 0 since N divides 0 according to our definition of divisibility.

Â And thus, 0 is not relatively prime to any other integer.

Â Also, note that since we are working in a modian world,

Â we can reduce our chosen integer Mod N without loss of generality which

Â coincidentally will leave us with a member of the set S. For our example,

Â let's stick with what we know and choose X=5.

Â In this step, we create a new set that we arbitrarily call R,

Â that consists of our chosen value for x multiplied in turn by each member of the set S,

Â and reduced modulo N. Taking our example set,

Â we get this for R after the reduction,

Â keeping them in the order they were generated just for clarity.

Â Now, it is time to establish the four properties that will let us conclude

Â that the sets S and R must be identical, other than ordering.

Â For our specific example,

Â all we can really do is verified by inspection that each property actually holds.

Â The first property is that the elements of S are distinct,

Â meaning that there are no repeats.

Â This is self-evident because of the way S was constructed,

Â since only distinct positive integers less than

Â the modulus and relatively prime to it were included.

Â The second property is that both S and R contain the same number of elements.

Â This is also self-evident since each element in S was used to

Â create exactly one element in R. Now it's possible that,

Â after the modular reduction,

Â that we have some repeats,

Â but we'll deal with that in a bit.

Â For now, we just care that both sets have the same number of elements,

Â namely m. The third property is that every element in

Â R is also an element in S. If we can establish this,

Â then that establishes that R is a subset of

Â S. We'll prove this by contradiction by assuming that

Â some element of R exists that is not also

Â an element of S. The final property is that all in all,

Â elements of R are distinct, that there are in fact,

Â no repeats even after the modular reductions are performed.

Â This proof is also done by contradiction by assuming that

Â there do exist two elements in R that are not distinct.

Â We constructed R by performing some math and reducing the result

Â modulo N. This means that all elements in R are

Â non-negative integers strictly less than N. And since

Â all such integers that are relatively prime to N are contained within S,

Â that means that if all elements of R are relatively prime to N,

Â then they must also be in S. So we will assume that there is

Â some element R that is not relatively prime to N. Meaning that there is some element,

Â we'll call it j, that has a divisor in common with N that is greater than one.

Â We'll call the greatest such divisor,

Â D. The element j was generated using the relation,

Â j = k*x mod N,

Â using one of the elements K from set S. By our defining relation for modular arithmetic,

Â we know that j = k*x + q*N,

Â where j is greater than or equal to zero,

Â but less than N. If j is not relatively prime to N,

Â that means that it can be written as the product of d and some other integer.

Â We'll call it c1.

Â Likewise, our modulus can be written as the product of d and some other integer, c2.

Â Dividing both sides by c,

Â since we're not working in a modular world, division is allowed,

Â we have the result that an integer is equal to the sum of two terms,

Â the second of which is clearly an integer.

Â This means that the first term,

Â which involves division, must also be an integer.

Â However, k and x were specifically chosen such they were relatively prime to N,

Â meaning that they must also be relatively prime to any factors of N,

Â including d. The result is that kx divided by d cannot be an integer,

Â unless the d is exactly equal to one.

Â This is our contradiction,

Â because this requires that j and N be relatively prime,

Â which we assumed was not the case.

Â Hence, j must be a positive integer,

Â less than and relatively prime to N.

Â Meaning that it is a member of the set S, by definition.

Â And thus, R is a subset of S. The proof that all members of R,

Â as generated, are distinct,

Â is also by contradiction.

Â We assume that two different elements of R are the same.

Â Since all elements in R were generated from distinct elements in S,

Â if R contains two identical elements,

Â they had to be generated using two different elements of

Â S. Assume that elements were k1 and k2.

Â The corresponding elements in R,

Â are j1 and j2,

Â and are related to k1 and k2 as shown.

Â Clearly, if j1 and j2 are equal to each other,

Â then they are also congruent mod N,

Â which requires that k1*x and, k2*x,

Â also be congruent mod N. Since x and N are relatively prime,

Â x has a multiplicative inverse mod N. This allows us

Â to cancel x from both sides, yielding this result.

Â Since k1 and k2 are both positive integers less than N,

Â and all such integers are in distinct residue classes,

Â the only way for k1 and k2 to be congruent is for them to be equal,

Â which contradicts our assumption that they are distinct.

Â Therefore, j1 and j2 cannot be congruent,

Â and must also be distinct elements of R.

Â Recapping the four properties from the prior step,

Â we have that all elements of S are distinct,

Â there are the same number of elements in S and R,

Â all elements in R are also in S,

Â and all elements in S are distinct.

Â If the sets S an R each contain the same number of distinct elements,

Â and R is a subset of S,

Â then the pigeonhole principle requires that every element

Â in S is equivalent to one of the elements in R,

Â making S a subset of R. If two sets are each subsets of each other,

Â then the two sets must be equivalent, i.e.,

Â they contain the same elements varying only in the ordering of them.

Â The two sets in our example clearly exhibit this property as verified by inspection.

Â Next, we simply form the product of all of the elements within each set.

Â P_sub_S is the product of all the K values in S,

Â while P_sub_R is the product of all the j values in R. For our two example sets,

Â those products are a large,

Â and largely meaningless number.

Â The fact that the two products must be equal is, however, self-evident.

Â Since the two sets are equivalent,

Â the products of all their elements must be

Â equal regardless of ordering since multiplication is commutative.

Â Writing the elements of R,

Â in terms of the elements of S that produce them,

Â we have this relation.

Â We can pull out the m factors of x leaving us with this.

Â Since each k is relatively prime to N,

Â it has a multiplicative inverse.

Â Multiplying both sides by each of these inverses,

Â we get our final result that one is congruent to x,

Â raised to the m mod N. Recall that M is,

Â by definition, the totient of N. All that is left is to formally show that

Â the exponent in a modular expression lives in

Â a modulo world given by the totient of the modulus.

Â This is quite straightforward.

Â Choose an arbitrary exponent, y.

Â By our defining relationship for modular arithmetic,

Â this can be written in terms of our totient m,

Â as some quotient Q times m plus R, where R is,

Â y mod N. By the additive property of exponents,

Â we can write this as the product of two factors.

Â And by the multiplicative property of exponents,

Â we can write the first factor as an integer power of x

Â to the m. When we take this into a mod N world,

Â we can replace m with the totient of the modulus.

Â If x is relatively prime to N,

Â then x to the m is congruent to one.

Â And since any integer powered one is one,

Â we are left with our final result.

Â Remember that, in general,

Â this relationship is not true.

Â It is not true that the exponent in modular expressions can

Â always be reduced modulo to the totient of the expression modulus,

Â despite our recent result.

Â That result is only valid when x is also

Â relatively prime to N. This point simply cannot be stressed enough,

Â primarily because it is such a tempting trap to fall into.

Â Next step, we'll develop Euler's Totient function,

Â to actually calculate the totient of the modulus.

Â