PROFESSOR: The elements that have inverses modulo and will be particularly important to us. And so the first question is how many of them are there, which is what Euler's function tells us.
So the definition of Euler's function, phi of n, is it's the number of integers in the remainder interval from 0 to n minus 1 such that k is relatively prime to n. So remember, there's the notation for the remainder interval that includes 0 and excludes n. And another way to say relatively prime to n is to say the gcd of k and n is 1.
So let's define that set of numbers that we're interested in-- gcd1 of n [? be ?] those numbers that have a gcd of 1 with n. That is, the numbers that have inverses and the numbers that are cancellable modulo n. So what it means is that phi of n is precisely equal to the size of gcd1 of n.
Now, some authors call gcd1 n star. I didn't find that a very informative notation and so I'm not using it. phi of n is also, for your information, called Euler's totient function, but we'll just stick to calling it phi or Euler's phi.
So let's look at an example-- gcd1 of 7. The numbers that are relatively prime to 7 are all the positive numbers less than 7 because 7 is prime. So it's the set 1, 2, 3, 4, 5, 6. gcd1 of 12 is the numbers that have no factor in common with 12. They are the numbers in green below. And the other red numbers do have a number in common with 12-- do have a prime in common with 12. The pattern here is not so apparent.
Anyway, phi of 7 is the size of gcd1 of 7-- namely the size of the set 1 through 6, which is 6. gcd 12 determines phi of 12. phi of 12 is the number of green elements, which is 4.
OK. A simple rule for calculating phi. When phi is prime we've already indicated, namely, everything-- every positive number less than p is relatively prime to p. And so phi of p is simply p minus 1.
Let's look at a more important example, or illustrative example-- namely, phi of 9. Well, OK. So there are the candidate numbers from 0 through 8, and which ones are relatively prime to 9?
Well, it's relatively prime to 9 if and only if it's relatively prime to 3. Now, which numbers in this interval are relatively prime to-- are relatively prime to 3, or, rather, are not relatively prime to 3? Well, it's every third number that's divisible by 3.
So, those are the bad ones. If we subtract the bad ones, we're left with the good ones-- the ones that are relatively prime.
So a phi of 9 is simply the set of all the numbers minus 1/3 of 9, which is the bad one-- bad one's namely 6. This generalizes to a power of a prime. If k is a positive integer then phi of p to the k-- the reasoning is that a number is relatively prime to the p to the k if and only if it's relatively prime to p.
p divides every pth number, so one pth of the numbers in the interval are bad, which means that phi of p is the good ones minus 1 pth of p to the k. Namely, phi of p to the k is p to the k minus p to the k over p, which can also be expressed in a more standard form-- p to the k minus p to the power k minus 1. And that knocks off the story of phi to the p for powers of primes.
Well, suppose you're dealing with a number that's not a power of a prime. And there's one very elegant little fact about phi that explains how to deal with non powers of primes. Namely, if a and b are relatively prime, then phi of a b is simply gotten by computing phi of a and multiplying it by phi of b.
This property of phi is called multiplicativity, by the way. It comes up a lot in number theory. A function is multiplicative when its value at a product of relatively prime numbers is the product of the values at those two relatively prime numbers. So phi is multiplicative.
Now, the proof of that-- one proof is on problem set 5, and there's another proof that we'll see in a couple of weeks when we get into counting the inclusion-exclusion principle. Let's just use this fact about phi-- the multiplicity of phi-- multiplicativity of phi to see how it lets us calculate phi of an arbitrary number.
So, in particular, phi of 12-- which looked complicated earlier-- well, 12 is 3 times 4. So that means that phi of 12 is phi of 3 times phi of 4. But now I'm in great shape because 3 is a power of a prime, namely 3 to the 1. And 4 is a power of a prime, namely 2 squared. So applying the power of prime formulas, I get that phi of 3 is 3 times 1 times 2 squared minus 2 to the 2 minus 1, which simplifies to 4, which is the answer that we saw before.
And the punchline for why we're examining phi is Euler's theorem, which tells us how powers of numbers in gcd1 of n behave. Namely, that if k is relatively prime to n, then if you raise k to the power phi of n, it's congruent to 1 mod n.
And that will lead us. In the next section we will look at the proof of Euler's theorem.