How many zeros are in the Cayley table for multiplication mod n?

It is stated without proof that the number of zeros in the Cayley table for multiplication in $\mathbb{Z}/n\mathbb{Z}$ is given by the gcd-sum function $\sum_{k=1}^n \gcd(k,n)$, for all positive integers $n$.

I can show this is true for small values of $n$ and for $n$ prime, but proof for a general $n$ eludes me.

The number of zeroes in the Cayley table is $z_n:=|\{(x,y)\in(\mathbb{Z}/n\mathbb{Z})^2: xy=0\}|$. To obtain your formula let's count the cardinality of this set in a different way. Fix $x\in\mathbb{Z}/n\mathbb{Z}$, so $x$ can be identified with an element in $\{1,\dots,n\}$, we count the number of elements $y\in\{1,\dots,n\}$ such that $xy\equiv 0\pmod{ n}$.

We are done if we can show that this number is $\gcd(x,n)$. Let $k=\gcd(x,n)$ and assume $km=n$. Since $k=xr+ns$ for some $r,s\in \mathbb{Z}$, we have that if $xi\equiv 0\pmod{n}$ then $km=n\mid ki$, so $m\mid i$. This means that the additive order of $x$ is $m$, so the cardinality of $\langle x\rangle=\{xy\pmod{n}: y\in\{1,\dots, n\}\}$ is $m$. This implies that the cardinality of $\{y:xy\equiv 0\pmod{n}\}$ is $n/m=k=\gcd(x,n)$. Therefore $$z_n=\sum_{x=1}^n\gcd(x,n).$$