0:00

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.

Â 0:23

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.

Â 1:45

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.

Â 2:15

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.

Â 3:57

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.

Â 5:13

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.

Â 6:26

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.

Â 6:46

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.

Â 7:56

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.

Â 8:47

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.

Â 9:15

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.

Â 9:31

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.

Â 10:00

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.

Â 11:09

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.

Â 11:32

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.

Â