0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Andrew Thompson Mar 16 '14 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.