Number of homomorphisms between two cyclic groups.

Let us consider homomorphisms $\mathbb Z_m\to\mathbb Z_n$. Let us denote $d=\gcd(m,n)$.

Since $1$ is generator of $\mathbb Z_m$, the choice of $f(1)=a\in\mathbb Z_n$ uniquely determines all values of $f$. Namely we get $$f(k) = f(k\times 1)= k\times f(1) = k\times a.$$ (Here $k\times b$ denotes the addition $\underset{\text{$k$-times}}{\underbrace{b\oplus b\oplus \dots\oplus b}}$, where $\oplus$ denotes the addition in the given group, in this case either $\mathbb Z_m$ or $\mathbb Z_n$. I chose this notation to distinguish it from the usual addition of integers.)

But not all choices of $a$ are possible. We definitely need $$f(0) = f(m\times 1) = m\times a = 0.$$ I.e., $ma \equiv 0 \pmod n$.

This gives us that $ma=nb$ for some integer $b$. If we divide both sides by $d$, we get $$\frac md a = \frac nd b.$$ Since $\frac nd$ and $\frac md$ are coprime, this implies that $$\frac nd \mid a.$$

But there are exactly $d$ such numbers in $\mathbb Z_n$, namely the numbers $0,\frac{n}d, \frac{2n}d,\dots, \frac{(d-1)n}d$.

So we see that there are at most $d$ homomorphisms $\mathbb Z_m\to\mathbb Z_n$.

It remains to check somehow that for any choice of $a$ such that $m\times a=0$ (i.e., one of the $a$'s described above) the function given by $$f(k) = k\times a$$ is indeed a homomorphism.

If $k,l\in\mathbb Z_m$, then we want to check whether $$f(k\oplus l) = f(k) \oplus f(l),$$ i.e., whether $$((k+l)\bmod m)\times a = (k\times a + l\times a)\bmod n.$$ We can write $$((k+l)\bmod m)\times a \overset{(1)}= (k+l)\times a \overset{(2)}= k\times a \oplus l\times a \overset{(3)}= (k\times a + l\times a)\bmod n.$$ $(1)$ is true since $m\times a=0$
$(2)$ follows simply from properties of groups. (I will link to a similar proof for rings. But the basic idea is the same and this should be fairly obvious.)
$(3)$ is simply the definition of the operation $\oplus$ on the group $\mathbb Z_n$.

Set $d=\gcd(m,n),\enspace n'=\dfrac nd$. $\DeclareMathOperator{\Hom}{Hom}\Hom(\mathbf Z/m\mathbf Z,\mathbf Z/n\mathbf Z)$ is in bijection with \begin{align*}\{x+n\mathbf Z\,; m(x+n\mathbf Z)=n\mathbf Z \}&=\{x+n\mathbf Z\,; n\mid mx \} =\Bigl\{x+n\mathbf Z\,; \dfrac n{\gcd(m,n)}\,\Big\vert\, x \Bigr\}\\[1ex]&=n'\mathbf Z/n\mathbf Z=n'\mathbf Z/n'd\mathbf Z\simeq\mathbf Z/d\mathbf Z. \end{align*}

This can be proved with the help of these theorems.

1)Lagrange's Theorem.

2)If $\phi$ is a homomorphism from $G$ to $\hat G$ and let $g\in G$. Then if $|g|=k$, then $|\phi(g)|$ divides $k$.

3)$\gcd(n,m)=\sum_{d|n\,and\,d|m}\varphi(d)$, $\varphi$ being the Euler's totient function.

4)If $d$ is a positive divisor of $k$, the number of elements of order $d$ in a cyclic group of order $k$ is $\varphi(d)$.

Every cyclic group of order $k$ is isomorphic to $Z_k$.If $\phi$ is a homomorphism from $Z_m$ to $Z_n$ observe that once we know $\phi(1)$ we know $\phi(k)$ for any $k,$ because $\phi(k)=\phi\underbrace{(1+1+\cdots+1)}_{k \text{ terms}}=\underbrace{\phi(1)+\phi(1)+\cdots \phi(1)}_{k \text{ terms}}=k\phi(1).$ Hence a homomorphism from $Z_m$ to $Z_n$ is completely determined by the image of $1 \in Z_m$. If $1$ maps to $a$, by $(2)$ and $(1)$ respectively $|a|$ should divide both $m$ and $n$; so that $|a|$ is a common divisor of $m$ and $n$.

Now the problem breaks down to finding the no. of elements in $Z_n$ such that their orders divide both $m$ and $n.$

Let $d$ be any positive common divisor of $m$ and $n$. The number of elements of order $d$ in $Z_n$ is $\varphi(d)$ by $(4)$. Thus the number of candidates for $a$ is $\sum_{d|m\,and\,d|n}\varphi(d)$. Invoking $(3)$, this is nothing but $\gcd(m,n)$.

Hint: $f:Z/m\rightarrow Z/n$, set $f([1])=[p]$, $f(m[1])=f([m])=0$. this implies $m[p]=0$ in $Z/n$ thus $mp=0 $ mod $n$, thus ${n\over {\gcd(n,m)}}$ divides $p$. The number of morphisms between $Z/m$ and $Z/m$ is the order of the subgroup of $Z/n$ generated by $[{n\over {\gcd(n,m)}}]$ which is $\gcd(n,m)$.