factoring zero in modulo n Let $m,n\in \mathbb{N}$. How many different classes $\overline{y}\in\mathbb{Z}_n$ are there, so that
$$\overline{m}\cdot \overline{y}=\overline{0}$$
Each element is either invertible or a factor of the zero. I know that there are $n-\phi(n)$ zero factors in $\mathbb{Z}_n$ ($\phi$ is the Euler's totient function). I have some trouble finding out how many different ways is there to factor a random element $\overline{m}$.
 A: Hint: If you know the prime factorization of $m$, then you have that the set of $y$ is generated by the element that has the complement prime factorization so that when you multiply $y$ and $m$ you get all prime factors of $n$ (with their multiplicity).
A: For fixed $1 \le m \le n$ you need to find all $1 \le y \le n$ such that $my$ is $0$ modulo $n$, that is $n \mid my$. 
Now if $m \mid n$, then this is equivalent to $ (n/m) \mid y$, so you have  $(n/m), 2(m/n), \dots, m(n/m) $, that is $m$ classes.
In general, let $m' = \gcd(n,m)$ then $n \mid my$ if and only if $(n/m') \mid y$, so you have $m'$ classes. 
Thus, in any case the reply is $\gcd(m,n)$. 
Practical note: computing the GCD is a lot simpler than factoring (for large numbers). 
A: Let $d=\gcd(m,n)$, and let $m=dm_1$ and $n=dn_1$. We want the number of integers $y$ in the interval $[0,n-1]$ such that $n$ divides $my$, that is, such that $dn_1$ divides $dm_1y$, that is, such that $n_1$ divides $m_1y$. Since $m_1$ and $n_1$ are relatively prime, we want to find the number of integers $y$ in our interval such that $n_1$ divides $y$. There are $d$ such integers. 
