More fun in 2016, Part 7

Number Theory Level 2

Find $\sum_{d|2016}\phi(d).$

Clarifications

This sum is taken over all 36 positive integer divisors $d$ of 2016.
$\phi(d)$ denotes Euler's totient function .

The answer is 2016.

2 solutions

Alan Yan
Dec 20, 2015

It is well-known for any $n$ , $\sum_{d |n}\phi(d) = n$

A proof of this is by Gauss, who considered the rational numbers: $\frac{1}{n}, \frac{2}{n}, ... , \frac{n}{n}$

Note that there are $n$ numbers in the list and in simplest terms, the denominators are all factors of $n$ . If $d | n$ , then there will be exactly $\phi(d)$ numbers in the list with a denominator of $d$ . Thus the result follows.

Yes, exactly! (+1)

When we say that a mathematical result is "well-known", we must keep in mind that it is only a tiny fraction of the general population or even of math majors that is actually aware of stuff like this. With my post, I'm hoping to introduce a few more people to this elegant and simple result.

As a fan of roots of unity, I like to think of this result in these terms: There are $n$ $n$ th roots of unity; each of them is a primitive root of unity for some divisor $d$ of $n$ ; and there are $\phi(d)$ primitive $d$ th roots of unity.

Otto Bretscher - 5 years, 5 months ago

i did it using multiplicative functions properties. i think there should be a wiki on these sort of summations. it is a good idea to introduce people to these elegant and simple results. i want to write one but it might give away a lot of your problems....

Aareyan Manzoor - 5 years, 5 months ago

Don't worry about "giving away" my problems... this is all about spreading the message.

Otto Bretscher - 5 years, 5 months ago

@Otto Bretscher – thanks! i will try making one after i finish the current wiki i an working on.

Aareyan Manzoor - 5 years, 5 months ago

Sir can you please explain the proof.. From the fact that there are exactly phi d numbers with d as the denominators, how does the result follow?????

Ankit Kumar Jain - 5 years, 5 months ago

Thus, we have $\sum_{d|n}\phi(d)$ numbers. But since we have $n$ rational numbers by construction, we have the result.

Another proof:

It is well-known $X^n - 1 = \prod_{d|n}\Phi_d(x)$ the result follows from equating the degrees of the LHS and RHS.

Alan Yan - 5 years, 5 months ago

Thank you sir......

Ankit Kumar Jain - 5 years, 5 months ago

Daniel Liu
Dec 20, 2015

Note that since $\phi (x)$ is a Multiplicative Function , $\sum_{d\mid 2016}\phi (d) = \sum_{d\mid 2^5\cdot 3^2\cdot 7}\phi (d) = \left(\sum_{d\mid 2^5}\phi(d)\right)\left(\sum_{d\mid 3^2}\phi(d)\right)\left(\sum_{d\mid 7}\phi(d)\right)=32\cdot 9\cdot 7 = \boxed{2016}$

This is also another method to proving the identity $\displaystyle\sum_{d\mid n}\phi (d) = n$ : using the idea of Multiplicative Number Theory.

Here's another example: Find $\sum_{d\mid 2016}\sigma(d)$ where $\sigma(n)$ is the sum of the divisors of $n$ .

One can simplify this argument by pointing out that the function $f(n)=\sum_{d|n}\phi(d)$ itself is multiplicative, being the Dirichlet convolution of $\phi$ and the constant function 1. Now it suffices to observe that $f(p^k)=p^k$ for primes $p$ .

Otto Bretscher - 5 years, 5 months ago

Right, I forgot to mention that. However, if you read my solution from your perspective it still works; you can interpret the second equality sign as using multiplicity of the convolution of $\phi(n)$ and $1(n)$ .

Daniel Liu - 5 years, 5 months ago

More fun in 2016, Part 7

The answer is 2016.

2 solutions

0 pending reports