A Kick in the Discovery

Ok, so what is this strange sounding function? (We know it must be important since it has Euler’s name attached to it.) It’s simply a function that, when given an integer , spits out how many positive integers less than are relatively prime to .

Euler’s Totient Function: Let be a positive integer. Then, is Euler’s Totient Function and is defined by,

$\phi(n) =\{m \in \mathbb{Z}\;:\;\gcd{(n,m)} = 1\;and \;0\lt m \leq n\}.$

This needs an example, doesn’t it?

Let’s let . We want to know how many integers between 1 and 12 are relatively prime to 12.

We’ll 2, 4, 6, 8, 10 12, all share 2 as a factor with 12. So let’s get rid of those.

And 3 and 9 share 3 as a factor with 12. This leaves,

Thus, .

Likewise, you can check that and Also note when , then .

Euler’s totient function has many wonderful and beautiful properties. Here are a few:

if and only if is prime,

if is prime and is a positive integer,

If then,

If , then .

Here we go!

The first one:

---

Proposition: if and only if is prime.

Proof: (Click in the Discovery)

Proof: This is an if and only if statement, so we have to do each direction separately

Forward: If then, is prime.

This can be seen from the facts that (i) there are p-1 integers less than p and (ii) . Thus, we deduce that every integer less than shares no factors with . Hence, it’s prime.

Backward: If is prime then,

Well, if is prime, then every number less than it is relatively prime to it! Since there are integers in the set 1, 2, 3, … , p-1 we have, .

Second One:

---

Proposition: if is prime and is a positive integer.

Proof: We are going to count the number of multiples of less than or equal to . From there, we subtract this off the total number of positive integers less than .

Step 1: How may multiples of are in the set of integers 1, 2, 3, … ?

Well, are the multiples we want. So there are of them.

Step 2: How many positive integers are less than or equal to ?

There are integers.

Step 3: Subtract step 2 and step 1.

We get: as desired.

*Note we could have done this formally with induction on

Third One

Proposition: If then,

Vocabulary alert: When an integer function has the property that when , we call it multiplicative. Hence, Euler’s Totient function is multiplicative.

Proof: (Click in the Discovery)

Proof: Let . First, right off the back we know that there are integers less than and relatively prime to . Let’s denote these by

Consider, some number of the form in the set of positive integers less than ,

Observe that, (I challenge you to prove this, however, I will put a short proof in this footnote¹). So, if , then This motivates breaking up the above set into different subsets using the different from earlier.

And since every is relatively prime to we deduced that every integer in the sets above is relatively prime to TAKEAWAY: for every integer and for

We want integers relatively prime to both and But, if we can show that every set , like the ones above, have integers that are relatively prime to , then we’d be done! Since we’d have integers in each of the sets and as a result we’d have integers relatively prime to both and

To this end, focus on the set B (we’re going to drop the subscripts for now), where ,

We want to find out how many integers in B are relatively prime to , ie how many integers are such that .

First, observe that every one of the n-1 integers in B are different (mod n). To see this, consider,

Where With some modular arithmetic we deduce,

But recall that we have , so we know that we can safely divide by and get,

Together with the fact that and are less than we deduce we get what we wanted. (This follows from for some integer And since ,it must be that: Thus )

Using that every number in B is different (mod n) and that there are (n-1) of them we deduce that if we reduced all the numbers in B (mod n) we’d end up with the set 1, 2, 3, …, (n-1) in some order. We will now show that there are integers in B that are relatively prime to

We know that there are positive integers less than relatively prime to . Let be one of these integers and let We claim this implies

To see this, let Since we deduce,

for some integer Solving we see,

which shows since we already know that and . But, and imply since it was assumed that

Therefore, there is integers relatively prime to for every set like . And since there are such sets, there are positive integers less than, relatively prime to

Fourth One:

Theorem: If where are non-negative integers, then .

Remark: This simply says that, given some prime factorization we can compute using the formula above. For example, . We know Thus, by the above formula:

Which you can check!

Proof: I challenge you to finish this one! As a hint, use what we have shown so far. For example,

By induction and continue from here.

Concluding Remarks

Euler’s totient function is a wonderful and useful tool for much of number theory. We will see how we can use this tool to generalize Farmat’s Little Theorem! It’s so awesome! Until next time!

Footnote:

1. I hope you gave it a go! Even if you couldn’t prove it it’s great that you tried!
   So our goal is to show: assuming are integers. We’ll do this by first focusing on . Since divides both and , we conclude and thus, . This means that . Therefore, (why?).
   Turning our attention to , we know divides both , , and , we conclude or . Thus, and since , it must be . ↩︎