In the previous lesson, we saw that the exponent in a modular expression lives in a different modular world than the expression itself. And that the relationship between the two is that the modulus for the exponent is the totient of the modulus for the overall expression. For completeness, we also saw that this is only valid when the base of the exponent is relatively prime to the expression modulus. We've also seen that the totient of a positive integer is equal to the number of positive integers that are both less than, and relatively prime to, the number. In this lesson, we'll see how to actually calculate the totient of a number, other than by brute force enumeration, of all positive integers that are less than and relatively prime to it. The key lies in the fundamental theorem of arithmetic, which you might recall states that every integer greater than one can be written as a unique product of prime factors. We can write this, very compactly, as a product expression, in which each unique prime factor is raised to a corresponding exponent. In theory, we could specify that the ith prime factor is the ith prime number. Starting with 2 as being p1, 3, p2, 5 being p3, and so on, up through the largest number that less than N. Actually we only have to go up to the square root of n, but that's a distinction we can ignore. With any prime number that does not divide N, we just have a exponent of 0. But in practice, there are almost always way too many prime factors, and nearly all of them have 0 exponents. So it's almost always understood that the product only includes the specific prime numbers that divide N. While the order of the prime factors doesn't matter, we usually think of them being ordered from smallest to largest. Without proof, let's look at the equation for the totient function. This says that if I know the prime factors of N, that to find the totient, I merely multiply N by a series of fractions, each of which is the ratio of 1 less than one of the prime factors, divided by that prime factor. Notice that the prime factor is repeated, I don't need to know how many times it's repeated, I only need to know the distinct prime factors of N. Before we set out to prove this, let's look at a few special cases. The simplest case is when our number is prime, in this situation the totient is one less than the number. This is actually quite obvious, since the fact that it is prime number means that every positive integer less than it is relatively prime to it. This result is sufficiently obvious that we can go ahead and consider this case proven. So for example, since 89 and 97 are both prime numbers, the totient of 89 is 88, while the totient of 97 is 96. What about when N is a product of prime numbers, without any repeats? In that case, the product of all the prime factors that builds up in the denominator is equal to N, cancelling it out. The result is that the totient is the product of factors, each equal to 1 less than the corresponding prime factor. The fact that this is correct isn't immediately obvious, but it's not too hard to reason out. However the approach we will take in a little bit will make this result an obvious special case. Using the two prime numbers from our previous example, the totient of 8633, which is the product of 89 and 97, is 8448, the product of 88 and 96. The product of the first ten prime numbers, which is all prime numbers less than 30, is 6 billion, and a bunch of change, and its totient is little over 1 billion. As you can see, our numbers can get very large, very quickly. In fact the growth of the product of the first k primes grows at a rate on the order of, but not quite as fast as, the factorial function, which makes sense if you think about it. What about a value of N that is an integer power of a prime number? This means that we have a single prime factor, and so our totient function reduces to one of several useful forms. The one that is probably the most useful for us is the first one, since it will be the one that is the easiest to prove when we get there in a bit. Consider the totient of an integer power of 2, it turns out that this is exactly half of the integer. For instance, the totient of 1024, which is 2 to the 10th, is 512. This make sense considering that if the only prime factor of a number is 2, then any even number is not relatively prime to it, while every odd number is. Hence, exactly half of the numbers less than 2 to the k are relatively prime to it. But don't fall into the trap of thinking that the totient of p to the k is always p raised to the k-1, this is true only for p equals 2, and that's just because 2 minus 1 is 1. Let's consider 7 raised to the k, here we see that we pick up an extra factor of 6, making the totient of 343 equal to 294. Meaning that more than 85% of the numbers less than 343 are relatively prime to it. Let's look at one final example, before we turn to deriving the totient formula itself. We can take our formula for the totient function, and combine it with the fundamental theorem of arithmetic. To get the result that the totient of an arbitrary number N can be expressed as the product of totients of the individual prime powers that are the factors of N. This is a consequence of the multiplicative property of the totient function, which says that the totient of the product of two positive integers is the product of the totient of the two integers. But it only applies when the two integers are relatively prime. However, we know it applies here, because if a and b are both prime powers of different prime numbers, then by definition they are relatively prime. By way of example, let's find the totient of 1100, which has prime factors 2, 5, and 11. Using the first form of the totient function we get a result of 400. Not surprisingly, this matches the result we get if we use the multiplicative property. Now, which form is easier to use? Well that depends on the situation, and having both forms available gives us greater flexibility in doing our work. As we now turn our attention to proving our formula for the totient function, we see that we really only have to do two things. First, we have to prove that the totient function is true for the special case of a prime power, and second we have to prove that the multiplicative property is true. Everything else are, then, simply special cases. To prove our formula for the totient of a prime, p, raised to an integer power k. We only need to subtract the number of integers less than N that are not relatively prime to N, from the number of integers that are candidates. Since any strictly positive integer x that is less than N is a candidate for being relatively prime to N, the number of candidates is N-1. Next, we need to identify the number of these integers that are not relatively prime, meaning those values of x for which the gcd(x,N) is greater than 1. Since N only has a single prime factor, if x is not relatively prime to N, it must also have the same prime factor, meaning that x is a multiple of p. The values that m can take on, and keep x within the allowed range, is anything from 1, up to 1 less than the ratio of N/p, since p times N/p is N, which is not a candidate. Next, we just take the difference of these two quantities, and by writing N in terms of p and k, we get the result that we expect. Next we need to show that the totient function is multiplicative when finding the totient of the product of two relatively prime numbers, P and Q. Keep in mind that P and Q do not need to be prime themselves, only relatively prime to each other. There are a number of ways to do this proof, and perhaps the most straightforward is using the Chinese Remainder Theorem. But since we haven't gone through that yet, we'll take a somewhat less elegant approach. We know that the integers we need to consider are 1 through N-1, giving us a total of N-1 integers that are candidates. If it makes things more convenient for us, we can include either 0 or N as a potential integer candidate, and since neither is relatively prime to N, nothing changes. So to make the bookkeeping easier, we will include 0 by considering all of the nonnegative integers less than N. By using two indices, lowercase p and q, that can take on values from 0 up to, but not including, uppercase P and Q, respectively. We can generate all of the allowed values of x as a linear combination of our two indices. If we tabulate this in a two-dimensional table, where each row represents a particular value of p, and each column represents a particular value of q, we get this. Here's where things start to get a little tricky, so follow along closely. If we choose a value of little p that is not relatively primed to big P, then little p and big P can both be written in terms of a common factor, which we'll call c. Using our equation for x, in terms of little p and little q, we can factor out c, which means that every integer on that row is divisible by c, which is a factor of big P and hence a factor of N. So none of the integers on that row count toward the totient of the N. Therefore the only rows that we need to consider are the rows for which little p is relatively prime to big P. The number of such rows is, by definition, the totient of big P. Now let's consider an arbitrary row, and see how many of the integers on that row are relatively prime to big Q. If you thought the last part was tricky, get ready for a bit of a mind bender. As we go across each row, we add big P to the previous value. Since we know that big P and big Q are relatively prime, and since we have big Q columns, each integer in the row is in a different residue class, and each residue class is present exactly once. At this point you might be asking, how do we know this? How do we know at don't have repeats of some residue classes, and others that aren't represented at all? We've actually done proofs like this before, particularly in the lesson on the totient theorem. The key is to assume that there does exist two integers on the same row, that are in the same residue class. And use the fact that the difference between any two integers has to be a multiple of big P, combined with the fact that big P and big Q relatively prime, to show that this results in a contradiction. I'll leave doing that proof up to you, since you can use the totient theorem lesson as a template. Once we know that every integer on a row must be in a different residue class mod Q, we can use the pigeonhole principle to establish that every residue class is represented exactly once. Once we are at that point, we can ask how many of those elements are relatively prime to big Q, with the answer being that it is the totient of big Q. Note that this is therefore the same number for every row. Bringing this together, we have the totient of P rows that contains any elements relatively prime to N, and each of those rows contains the totient of Q such elements. Thus the total number of elements is the torsion of P times the totient of Q, thereby proving our multiplicative property of the totient function, when the two factors are relatively prime. We can easily extend this multiplicative property to an integer that is the product of m relatively prime factors, by induction. Since any partitioning of the factors into two groups results in two overall factors of N, that are relatively prime. This completes our proof of the formula for Euler's totient function.
