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.