Problem: Show that for all positive integers $n$,
$$ \sum_{a=1, (a,n)=1}^{n} (a-1, n) = d(n)\phi(n)$$
where $(a, b)$ stands for $\text{gcd}(a, b)$ and $d, \phi$ are the divisor and Euler's totient function, i.e., number of numbers co-prime to n and less than n = $\phi(n)$.
I find this one really fascinating because of $a-1$. This problem is from Niven and Zuckermann 'Introduction to the Theory of Numbers'.
My approach is to show that the L.H.S. is a multiplicative function. because it is easy to compute it for powers of primes.
Let $d_1d_2=n$ where $(d_1, d_2)=1$
I want to show that
$ \sum_{a=1, (a,n)=1}^{n} (a-1, n) = (\sum_{a=1, (a,d_1)=1}^{d_1} (a-1, d_1))( \sum_{a=1, (a,d_2)=1}^{d_2} (a-1, d_2)) $ but I am not able to proceed other than showing that some terms are cancelling. THe main problem is that there are $x$ such that $(x, n)=1$ but $x > d_1, d_2$.
Please help. Any hints are appreciated.
Best Answer
For a divisor $d|n$, the number of $a>1$ such that $gcd(a-1,n)=d$ is equal to $|\{1 \leq q \leq \dfrac{(n-1)}{d}|(qd,n)=d\}|=|\{1 \leq q \leq \dfrac{(n-1)}{d}|(q,n/d)=1\}|=\varphi(n/d)$. Now there's a multiplicative function. Also, it is known that if $f$ is multiplicative, then $\sum_{d|n}f(d)$ is also muliplicative, so having an expression of this form is useful.