Return to Revisions

As Gerhard Paseman has commented, more general problems were studied by D.H. Lehmer in his paper The distribution of totatives. In particular, see section 5 of the paper. From his work it follows that $D(n)$ is a multiplicative function defined on prime powers as follows: $D(p^k)=0$ if $p\equiv 1\pmod 4$ for all $k\ge 1$; $D(p^k)=-2$ if $p\equiv 3\pmod 4$ and for all $k\ge 1$; and finally $D(2)=-1$, and $D(2^k)=0$ for all $k\ge 2$. The proofs are based on the simple sieve of Eratosthenes, and clearly this formula establishes that all $D(n)$ are zero or a power of $2$ in magnitude; the other assertions in the problem also follow easily.