Counting Homomorphisms from $\mathbb{Z}_n$ to $\mathbb{Z}_m$

Question

My notes have a proof of the following claim:

Prove there are $\gcd(n,m)$ homomorphisms $\phi: \mathbb{Z}_n \rightarrow \mathbb{Z}_m$.

I was able to follow most of it but I got lost. I outline the proof below and highlight where I get lost:

First we note that $\phi$ is completely determined by the image of $1$. To see this note: $\phi(x) = \phi(1+1+1+1....+1) = x \phi(1)$ so that if $\phi(1) = a \in \mathbb{Z}_n$ then the task is to find all $a$'s such that $\phi(x) = ax$ is a homomorphism. Arguments (which I don't reproduce) show that $\text{ord}(\phi(1))|n$ and $\text{ord}(\phi(1))|m$, thus $\text{ord}(\phi(1))|\gcd(m,n)$. Now I get lost. My notes say:

Look at $\langle\frac{m}{\gcd(m,n)}\rangle$ in $\mathbb{Z}_m$. Observe $\phi(1) \in \langle\frac{m}{\gcd(m,n)}\rangle$.

Thus $\phi(1) = k \frac{m}{\gcd(m,n)}$ for any $1 \leq k < \gcd(m,n)$. Thus there are $\gcd(m,n)$ homomorphisms.

1. Why do I look at $\langle\frac{m}{\gcd(m,n)}\rangle$ in $\mathbb{Z}_m$?
2. How do I see that $\phi(1)$ must be in $\langle\frac{m}{\gcd(m,n)}\rangle$?

Answer 1

Any homomorphism $\phi :\Bbb Z_m\to \Bbb Z_n$ is determined by $\phi([1])$.

Now if $\phi(1)=a\implies \phi(m)=ma\implies 0=\phi(0)=ma\implies o(a)| m$

Also $a\in \Bbb Z_n\implies o(a)|n$

Combining $o(a)\mid \gcd(m,n)$ .

EDIT:

Now for each divisor $k$ of $n$, $\Bbb Z_n$ has a unique subgroup of order $k$ which has $\phi(k)$ many generators.

So for $a$ we have $\phi(k)$ many choices.

Hence total number of choices for $a$ will be $\sum_{k|\gcd(m,n)} \phi(k)$

It is a known result that $\sum_{k|\gcd(m,n)} \phi(k)=\gcd(m,n)$ Proof:Relation between $\gcd$ and Euler's totient function .

Answer 2

It is easy to see that $\phi(1)|\rm{gcd}(m,n)$, by Lagrange twice (and the homomorphism property).

But, for each divisor $k$ of $\rm{gcd}(m,n)$, there are $\varphi(k)$ different elements of order $k$. Thus we have $\sum_{k|{\rm{gcd}(m,n)}}\varphi(k)=\rm{gcd}(m,n)$ homomorphisms (by a result proved by Gauß, among others).