-1
$\begingroup$

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 <m$ is $\text{gcd}(n,m)$.

I would appreciate any help.

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$ – Ben Grossmann Jan 12 '20 at 20:08
0
$\begingroup$

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.

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

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