Question

True or false.

$\sum _{d\mid n}\phi \left(d\right)=n,$ where $\phi$ denotes Euler's to tient function. .( Enter $1$ if true or $0$ if false)

Answer 1

The Euler's totient function $\left(n\right)$ denotes the number of positive integers less than or equal to $n$ and relatively prime to $n$, that is, the number of elements of the set $k1kn\$,and\$gcd(k,n)=1$.If the prime decomposition of the positive integer n is $n={p^{a_1}}_1{p}^{a_2}\mathrm{2...}{p}_k^{a_k}$,then $\left(n\right)=n\left(1\frac{1}{p_1}\right)\left(1\frac{1}{p_2}\right)\left(1\frac{1}{p_k}\right)$,and, using this formula, a computational proof of our assertion is possible. However, we will present a simpler proof, based on counting arguments.Consider the fractions $\frac{1}{n},\frac{2}{n},\frac{3}{n},,\frac{n1}{n},\frac{n}{n}$. Obviously, there are n such fractions (this is not a silly observation; just the first way to count them). Now, consider the same fractions in their lowest terms. Obviously, their denominators are divisors of n.How many of them have still the denominator equal to n? Clearly, those whose numerator was relatively prime to n, that is,$\left(n\right)$. How many have now the denominator equal to some d, where d is a divisor of n? In every such fraction, the numerator has to be less than or equal to d and relatively prime to d,hence there are $\left(d\right)$ such fractions. We thus obtained $dn\left(d\right)=n$, as desired.