A sum expression that I am not able to simplify I got this question from a friend. I am not able to solve it.
Is there an expression in terms of $k$ for the following: $\sum_{x=0}^{k-1}\sum_{y=0}^{k-1}(xy\mod{k})?$
It seems that for odd $k,$ this is equivalent to $\frac{k(k-1)^2}{2}.$ However, I am not able to prove this is true, it is simply something that I found after checking a few values of $k.$ I cannot find any such expression for even $k,$ even after trying out a few values.
 A: Fix an $x$ and consider the inner sum over $y$.  The $y=0$ term of course drops out, as does any other $y$ such that $k \mid xy$.  Note that if $xy \bmod k = a$ with $a>0$ then $x(k-y) \bmod k = k-a$.  So when $k$ is odd the non-zero terms pair up to average out to $k/2$.  Even when $k$ is even the same principle applies to the middle term $y=k/2$: it’s either exactly $k/2$ or $0$.
Therefore the inner sum is exactly $\frac k2 \#\{ 1 \le y \le k-1: xy \not \equiv 0 \pmod k \}$.  This second factor is simply $k - \gcd(x,k)$.
When $k$ is prime (not when $k$ is odd), the gcd term is always $1$, except when $x=0$, so we get $\frac k2 (k-1)^2$.  In the general case, we get:
$$\frac k2 \sum_{x=0}^{k-1} k - \gcd(x,k) = \frac k2 (k^2 - a(k)),$$
where $a(k)$ is known as Pillai’s arithmetic function.  There appears to be a number of papers studying it so I doubt it can be expressed compactly in terms of other functions. At least a more efficient expression is $a(k) = \sum_{d\mid k} d \varphi(\frac kd)$.
