I want to know how to compute this function: 


$f : \mathbb{Z}\_m \rightarrow \mathbb{N}$


$f(z) = |\{ (x, y) \in \mathbb{Z}\_m^2 \mid xy \equiv z \}|$



How many pairs of numbers between 0 and n-1 are equal to z mod n?
Although this is by far not research level, I cannot keep myself from posting a very simple solution which somehow has not been mentioned in the comments above.


I use the basic fact that the congruence $ax\equiv b\pmod m$ has exactly $(a,m)$ solutions if $(a,m)\mid(b,m)$, and does not have any solutions otherwise. As a result,
 $$ f(z) = \sum\_{y\in{\mathbb Z\_m}\colon (y,m)\mid(z,m)} (y,m) = \sum\_{d\mid(z,m)} d\varphi(m/d) $$
(the number of those $y\in\mathbb Z\_m$ with $(y,m)=d$ is $\varphi(m/d)$). This can be further re-written, for instance, as
 $$ f(z) = m \sum\_{d\mid(z,m)} \prod\_{p\mid m/d} \Big(1-\frac1p\Big). $$


