Sum of entries of Cayley table for $(\mathbb Z_n, \times)$ I've conjectured a general form of the sum of entries in the Cayley table for $(\mathbb Z_n, \times)$, though I'm not sure how to prove it:
$$\frac{n^2(n-1)}{2} - \frac{n}{2} \sum_{i=1}^{n-1} \gcd (i,n)$$
seems to work for small values of $n$. Is this right, and how can it be proven?
 A: That is true.
We can compare the multiplication table with another "imaginary" table, where every row contains an copy of $0,1,\cdots, n-1$ each.
The sum of the entry of the table we constructed is simply $n(0+1+\cdots+(n-1)) = \frac{n^2(n-1)}{2}$, which is your first term. Hence, we just need to show that the difference between the multiplication table and our imaginary table is $$\frac n2\sum_{i=1}^{n-1}\gcd(i,n).$$
We can consider three cases:
The row $\times 0$: since all entries in the multiplication table are $0$, the difference to our imaginary table is $$0+1+\cdots+(n-1) = \frac n2(n-1).$$
The row $\times k$, with $\gcd(k,n) = 1$: You can see that it is just an rearrangement of $0, 1, \cdot, n-1$. For instance, if $n=15, k=7$, the row becomes $$0,7,14,6,13,5,12,4,11,3,10,2,9,1,8.$$
So the multiplication table and the imaginary table are essentially the same, i.e, the difference is $$0 = \frac n2(1-1)$$.
The row $\times k$, with $\gcd(k,n) = d > 1$: We know that the modular equation $kx \equiv t \pmod n$ has no solution when $d \not | \ t$ and $d$ solutions when $d | t$. For instance, if $n=15, k=6$, then $d = 3$ and the row becomes $$\color{red}{0,6,12,3,9},0,6,12,3,9,0,6,12,3,9.$$
In this case, the difference between the multiplication table and the imaginary table will be $$\frac nd(0+1+\cdots + (d-1)) = \frac nd\frac{d(d-1)}{2} = \frac n2(d-1).$$
All the nonzero rows (there are $n-1$ of them) corresponds to either the second or third case, so after compensating the first case to the lase two cases you get
$$
\frac n2(n-1) + \sum_{i=1}^{n-1} \frac n2(\gcd(i,n)-1) = \sum_{i=1}^{n-1} \frac n2\gcd(i,n).
$$
A: Some minor comments. The sequence you are after is
$$
a_n=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}n\ \{ij/n\}
$$
where $\{\,\cdot\,\}$ denotes the fractional part.
This is known to be given by the expression in the OP, cf. A160255,
$$
a_n\equiv\sum_{i=0}^{n-1}\frac{1}{2} n (n-\gcd (i,n))=0, 1, 6, 16, 40, 63, 126,\dots
$$
More generally, one expects a similar result for
$$
a_n(f)=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}f(n\ \{ij/n\})
$$
where $f\colon\mathbb N\to\mathbb R$ is an arbitrary function. I find
$$
a_n(f)\equiv\sum_{i=0}^{n-1}f(i)T_{i,n}
$$
where $T_{i,n}$ "is the number of occurrences of the digit $n-1$ as least significant digit in the base-$i$ multiplication table", cf. A095026.
