Euler's φ-function measures the number of positive integers equal to or less than n,
which are relatively prime to n.
Compute the following:
∑ φ(d)
d|n
Prove this is correct.
The only observation I've made so far is that this must be a multiplicative function.
Let be a cyclic group of order and be the generator .
We have exactly , by Lagrange's Theorem , we know . We now show that for a given order , the number of elements in of this order is :
Suppose , then and since it is a cyclic group , let , so and
we have , otherwise thus .
Moreover , to avoid repetition , let because if , by writing we can show that where .
Therefore , the number of elements of order is the number of numbers not exceeding and prime to it :
Note that is any divisor of and each element in the group must have its order , by equating the number of elements we obtain
One more proof:
We use the fact that is multiplicative function.
If
If , we look on the following function:
since is multiplicative function, easily prooved that also is multiplicative function.
Let
so,
for every
Hence: