# Proving that $mx \equiv 0 \pmod n$ has $\gcd(m, n)$ solutions in the interval $[0, n-1]$

I wish to prove, using my own intuition, that there are $\gcd(m, n)$ group homomorphisms from $\mathbb{Z}_m$ to $\mathbb{Z}_n$. I have reduced(?!) the problem to proving that there are $\gcd(m, n)$ solutions to the equation $$mx \equiv 0 \pmod n$$ in the interval $[0, n-1]$. Having little to no training in congruence-arithmetic, I am not sure how to proceed. I know that $0$ always will solve it, supporting the result of always a trivial group homomorphism, but other than that I am kind of at loss.

Two remarks: Do not prove that there are $\gcd(m,n)$ group homomorphisms from $\mathbb{Z}_m \to \mathbb{Z}_n$ (using other methods), as I feel like that will ruin the experience I am currently trying to obtain. Secondly, if answering the question requires Fermat's Little Theorem or Euler's Generalization, please just hint me in the right direction, and I will try to complete the proof myself.

Let $d = \gcd(m,n)$, write $m= da$ and $n=db$. We want the number of solutions to the equation $dax \equiv 0 \mod db$ in the interval $[0,db-1]$, where $a$ and $b$ are relatively prime. The equation simplifies to $ax \equiv 0 \mod b$, that is $b \mid ax$. Since $b$ and $a$ are relatively prime, this is equivalent to $b \mid x$. Can you finish it from here?
• I will try for a while before asking any more questions, but is the main idea that this implies that $\frac{n}{gcd(m, n)}$ divides $x$? – Andrew Thompson Mar 16 '14 at 17:50