billy-wehring.com

What I would like to show you today is one very interesting property that Euler’s totient function satisfies, which was discovered by Gauss, so the theorem is kind of an Euler/Gauss team-up! As it turns out, if you sum $\phi(d)$ over every $d\mid n,$ then you get back $n.$ That is,

Where $\sum_{d\mid n}$ means “sum over positive divisors, $d,$ of $n$.”

When I first saw this result, I was surprised, and I hope you feel the same! Why would summing $\phi$ over divisors of $n$ total $n?$ By the end of this article, we will know why!

We will go through two proofs. One is longer, but I think it has merit to learn because the proof does not rely on any special property of $\phi,$ only $\phi's$ definition, whereas the second proof uses a few properties of $\phi.$ The second proof we will go through is a one-liner proof. Which is pretty nice.

Before we go through the proofs together, I recommend that you take some time to try to prove the theorem on your own before reading the proofs! Learning math(s) is always more fun when it’s hands-on! And the great thing is that this is only for fun! You’re not being tested or quizzed, so there is no time limit and no harm, no foul if you get stuck!

Just to make sure everyone is on the same page, here is the definition of Euler’s totient function, along with some of the properties we will need for the second proof. If you want to see a proof for the properties below, we proved these in Chapter 10 of Newbie at Number Theory, if you are interested!

Definition (Euler’s Totient Function): Let $n$ be a positive integer. Let the set $S_{\phi(n)}$ contain all integers that are less than $n$ and relatively prime to $n,$

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

Euler’s Totient Function $\phi$ is defined as the number of elements in the set $S_{\phi(n)}$,

$\phi(n) =\#S_{\phi(n)} .$

That is, $\phi(n)$ equals the number of positive integers less than $n$ that are relatively prime to $n.$

---

Theorem (Euler’s Totient Function Properties): Euler’s totient function, $\phi,$ satisfies the following properties:

1. $\phi(p^k) = p^{k-1}(p-1)$ if $p$ is prime and $k$ is a positive integer,
2. If $\gcd{(n,m)}=1$ then, $\phi(nm) = \phi(n)\phi(m) .$
3. If $n = p_a^{k_a}p_b^{k_b}\cdots p_m^{k_m},$ then $\phi(n) = n\left(1-\frac{1}{p_a}\right)\left(1-\frac{1}{p_b}\right)\cdots\left(1-\frac{1}{p_m}\right).$
4. An equivalent way to express 3. is the following,

$$\phi(n) =\Big(p_a^{k_a} – p_a^{k_a-1}\Big)\cdots \Big(p_m^{k_m} – p_m^{k_m-1}\Big)$$

Examples of $\phi$:

Consider $n=12.$ Then, $S_{\phi(12)} = \{1,5,7,11\}$ and therefore $\phi(12) = 4.$ We could also use property 3 to calculate $\phi(12)$ as well. Since $n=12 = 2^2 \cdot3^1,$

Now let $n=45.$ Then, $S_{\phi(45)} = \{1,\;2,\;4,\;7,\;8,\;11,\;13,\;14,\;16,\;17,\;19,\;21,\;22,\;23,\;26,\;28,\;29,\;31,\;32,\;34,\;37,\;38,\;41,\;43,\;44\}$ and therefore $\phi(45) = 24.$ Let’s use property 4 this time to check our work. Since $n=45 = 3^2\cdot 5,$ we have

Note that there are more efficient ways to calculate $\phi(n)$ and less efficient ways.

An Example of The Theorem

Before we go on to the proofs, let’s write out the statement and see an example.

Theorem (Gauss): Let $\phi$ be Euler’s totient function and $n\in \N.$ Then,

$$n = \sum_{d\mid n}\phi(d).$$

Where $\sum_{d\mid n}$ means “sum over positive divisors $d$ of $n$.”

Example: Let $n = 12.$ The set of the divisors of 12 is equal to $\{1,2,3,4,6,12\}.$ Thus,

How remarkable! Even though I know this has to work out, since we’re about to prove it together, I still love how the result falls out so nicely! This theorem is one of those “little things in life” that bring me joy.

If you want to, you can check the case with $n=45.$

The Proofs

Proof #1: The Long Way Around

The advantage of this proof is that you only need to know the definition of $\phi$ and not all the properties (1)-(3).

Click to see the Proof:

The key idea in this proof is to partition the set $[n]= \{1,2,\cdots,n\}$ into subsets that we can easily determine the size of. Since we’re summing over divisors of $n,$ it makes sense that the relation we will use to set up our partitions will be divisor-related.

To get it out of the way, and for completeness, note that the statement holds for $n=1.$ With that said, we now consider $n\geq 2.$

Denote the set of all $m\in [n]$ such that $\gcd{(m,n)}=d$ by $S_d.$ That is,

$$S_d:=\{m \in \mathbb{Z}\;:\;\gcd{(n,m)} = d\;\;\mathrm{and} \;\;0\lt m \leq n \}\subseteq[n].$$

In this way $S_{\phi(n)} = S_1.$ We claim that as we let $d$ run over positive divisors of $n,$ the sets $S_{d}$ partition the set $[n].$ To see that this is the case, we must show that every $\ell\in [n]$ is in one and only one sets $S_{d}.$

With the goal in mind, suppose that $\ell\in S_{d_1}$ and $\ell\in S_{d_2}.$ It follows that $d_1 = \gcd{(\ell,n)} = d_2$ and hence $S_{d_1} = S_{d_2}.$ I’ll let you ponder why every $\ell\in [n]$ is in at least one set $S_{d}.$ We conclude the family of sets $\{S_{d}\;:\;d\mid n\}$ partition the set $[n].$

We now shift our attention to determining how many elements are in each of the sets $S_{d}.$

A key observation is that $m\in S_{d}$ if and only if $\gcd{\Big(\frac{m}{d}\;,\frac{n}{d}\Big)}=1$ and $0<\frac{m}{d} \leq \frac{n}{d}.$ Therefore, $m\in S_{d}$ is equivalent to $\frac{m}{d}\in S_{\phi(n/d)}.$

$$m\in S_{d} \;\;\;\iff\;\;\; \frac{m}{d}\in S_{\phi(n/d)}.$$

This is great! We know by definition that $\phi(n/d) = \# S_{\phi(n/d)}.$ Therefore, $\phi(n/d) = \#S_{d}.$

We have almost everything we need in place to finish up this proof! Our last claim needs proving is that summing over positive $d$ such that $d\mid n$ is the same as summing over positive $\frac{n}{d}$ such that $\frac{n}{d}\mid n.$ Can you see why? It has to do with the fact that $\frac{n}{d}$ will run through all the divisors of $n$ just as $d$ does.¹

Altogether, we are able to make the following deduction,

$$\sum_{d\mid n}\phi(d) = \sum_{d\mid n}\phi\Big(\frac{n}{d}\Big) = \sum_{d\mid n}\#S_{\phi(n/d)} =\sum_{d\mid n}\#S_{d}= n.$$

The final equality follows from the fact that the sets $S_{d}$ partition the set $[n].$

This concludes the proof.

Proof #2: Short and Sweet

Click for the Proof:

The one-liner version of the proof is the following:

$$\mathrm{Let}\;n = \prod_{m=1}^k p_m^{a_m}. \;\;\mathrm{Then}\;\; \sum_{d\mid n} \phi(d) = \prod_{m=1}^k\sum_{i=1}^{a_m}\phi(p_m^{i}) = \prod_{m=1}^k\sum_{i=1}^{a_m}\Big(p_m^{i}-p_m^{i-1} \Big) = \prod_{m=1}^kp_m^{a_m} =n.$$

However, let’s explain what’s happening.

---

This proof relies on the fact that $\phi$ is multiplicative, i.e., has the property that $\phi(mn) = \phi(m)\phi(n)$ whenever $\gcd{(m,n)}=1.$ Let’s begin!

To get it out of the way, and for completeness, note that the statement holds for $n=1.$ With that said, we now consider $n\geq 2.$

Let $n = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}.$ The key step is to note that each of the divisors of $n = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$ shows up as a term in the following sum once expanded,²

$\char"1F511\qquad \Big(1+p_1+p_1^2+ \cdots + p_1^{a_1}\Big)\Big(1+p_2+p_2^2+ \cdots + p_2^{a_2}\Big)\cdots \Big(1+p_k+p_k^2+ \cdots + p_k^{a_k}\Big). \qquad \char"1F511$

Therefore, using the fact that $\phi$ is multiplicative, all we need to do is evaluate $\phi$ on all the terms in the sum. We deduce that

$$\sum_{d\mid n} \phi(d) = \Big(\phi(1)+\phi(p_1)+\phi(p_1^2)+ \cdots + \phi(p_1^{a_1})\Big)\cdots \Big(\phi(1)+\phi(p_k)+\phi(p_k^2)+ \cdots + \phi(p_k^{a_k})\Big)$$

As a check, notice that every term we get when we expand the product on the right-hand side is of the form $\phi(p_1^{r_1})\phi(p_2^{r_2})\cdots \phi(p_k^{r_k} ) = \phi(p_1^{r_1} p_2^{r_2}\cdots p_k^{r_k}).$ And, since we already know that the expanded sum in our $(\char"1F511)$ gives every divisor of $n,$ we know that the above product does indeed equal $\sum_{d\mid n} \phi(d).$

Next, we use property (4.) to write the above product as a product of telescoping sums,

$$= \Big(1+(p_1-1)+(p_1^2 – p_1)+ \cdots + (p_1^{a_1}- p_1^{a_1-1})\Big)\cdots \Big(1+(p_k-1)+(p_k^2 – p_k)+ \cdots + (p_k^{a_k}- p_k^{a_k-1})\Big).$$

The great thing about telescoping sums is that we get lots of cancellations. Once done, we arrive at

$$\sum_{d\mid n} \phi(d) = \Big( p_1^{a_1}\Big)\cdots \Big( p_k^{a_k}\Big) = n.$$

Just like that, we’re done!

Closing Thoughts

I find both proofs fun for different reasons. The first is more intuitive and really shows you why the theorem is true. The second hides some of what’s happening with its slickness. But the second proof foreshadows methods that are useful for more advanced problems in number theory. For instance, we used the fact that $\phi$ is multiplicative to be able to use $(\char"1F511)$ to rewrite our sum $\sum_{d\mid n}\phi(d)$ as a product of sums $\sum_{m=1}^{a_i}\phi(p_i^{m}),$ one for each prime divisor. This was useful because each of the sums $\sum_{m=1}^{a_i}\phi(p_i^{m})$ were easier to handle than the original sum. For those who are interested in learning more about these types of sums, you can search for arithmetic functions, Dirichlet convolution, and the Möbius inversion formula.

A Gift for You!

I would like to leave you with your own problem to solve. Let $\sigma(n)$ denote the sum of the divisors of $n.$ That is,

Definition (Euler’s Sigma Function): Let $n$ be a positive integer. Euler’s sigma function $\sigma$ is defined as,

$$\sigma(n):= \sum_{d\mid n}d.$$

Note that $\sigma(n)$ equals the sum of positive divisors of $n.$

As the name suggests (but does not guarantee), $\sigma(n)$ is another function that was invented (or discovered) by Euler. As an example, let $n = 12.$ Then,

Your challenge to prove the following: Let $n = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}.$ Then,

With all this said, thank you for taking the time to read this little article. I hope you found it helpful. I would appreciate it if you found that any part of this could have been explained better, and if there were any mistakes/typos to mention them in the comments.

---

Footnotes:

1. An easier way to think about this might be found by noticing the following two sets are equal:
   
   $$\Big\{d\in [n]\;:\;d\mid n\Big\} = \Big\{\frac{n}{d}\in [n]\;:\;d\mid n\Big\}$$ ↩︎
2. For example, let’s take $n=2^3 \cdot 5^2 = 200.$
   
   $$(1+2+2^2+2^3)(1+5+5^2) = 1 + 2 + 2^2+2^3+2\cdot 5+2^2\cdot 5+2^3\cdot 5^2+2\cdot 5^2+2^2\cdot 5^2+2^3\cdot 5^2$$Notice how the sum contains all the divisors of 200, which I leave you to verify. ↩︎