# How many solutions are there to the equation $na\equiv _m0$ for $0\leq a <m$? [duplicate]

I'm reading trough a proof that the number of (group) homomorphisms $$\mathbb{Z}_n\rightarrow \mathbb{Z}_m$$ is $$\text{gcd}(n, m),$$ and this is the only step that I'm not understanding, namely, that the number of solutions to the equation $$na\equiv _m0$$ for $$0\leq a is $$\text{gcd}(n,m)$$.

I would appreciate any help.

• Can you figure out which values of $a \in \Bbb Z$ will satisfy $na \equiv_m 0$? Try an example. I'd recommend $m = 8, n = 12$. – Ben Grossmann Jan 12 '20 at 20:08

Write $$n a \cong 0 \pmod{m}$$ as $$na = k m \text{.}$$ If $$n$$ and $$m$$ have a common factor, $$d$$, this reduces to $$(n/d)a = k(m/d)$$, equivalently a congruence with a smaller modulus $$(n/d)a \cong 0 \pmod{m/d}$$ Then there is a solution in each of the $$d$$ copies of the interval of length $$m/d$$ in the interval of length $$m$$. (In other words, the $$d$$ copies are $$[a]$$, $$[a]+m/d$$, $$[a]+2m/d$$, $$\dots$$, $$[a]+(d-1)m/d$$, where $$[a]$$ is the least nonnegative residue congruent to $$a$$ modulo $$m/d$$.) Therefore, there are $$d = \gcd(m,n)$$ solutions.

• \equiv, not \cong.... – Arturo Magidin Jan 12 '20 at 20:29
• @ArturoMagidin : Modular congruences are congruences. – Eric Towers Jan 12 '20 at 20:30
• Yes, but the usual symbol is $\equiv$ (\equiv), not $\cong$ (\cong)... – Arturo Magidin Jan 12 '20 at 20:31
• @ArturoMagidin : Not for the first half of my life, and I will never support the wrong notation for congruences. – Eric Towers Jan 12 '20 at 20:32
• @EricTowers Are you aware of anyone else that uses $\,a\cong b\,$ vs. the standard $\,a\equiv b\,$ for congruences in $\,\Bbb Z?\ \ \$ – Bill Dubuque Jan 12 '20 at 23:48