Today I've wondered how many homomorphisms are between the groups \((\mathbb{Z}/n\mathbb{Z},+)\) and \((\mathbb{Z}/m\mathbb{Z},+)\) with \(m, n \geq 2\). Does it make a difference if I use + or \(\cdot\) as operators?

Let \(M := (\mathbb{Z}/m\mathbb{Z},+)\) and \(N := (\mathbb{Z}/n\mathbb{Z},+)\) be groups and \(\varphi: M \rightarrow N\) be a group homomorphism. Let \(H := \{\varphi: M \rightarrow N\}\)

Some fundamental theorems (which I'm not going to prove) are:

- $\varphi(M)$ is a group.
- $K_\varphi := \{m \in M | \varphi(m) = e_N\}$ is a group.
- Lagrange's theorem: $H \leq G \Rightarrow \#H | \# G$
- $\varphi(1)$ defines the complete homomorphism as $\varphi(n) = \varphi(1 + (n-1)) = \varphi(1) + \varphi(n-1)$
- $\varphi(1) = 0$ is always a homomorphism (that maps everything to 0).

## $m = n$

**Theorem**: \(n=m \Rightarrow |H|=n\)
**Proof**:
You can map \(1\) to \(n\) values \(\stackrel{(IV)}{\Rightarrow}\) there can't be more than \(n\) homomorphisms.

For every \(i \in \{0, \dots, n-1\}\) exists an homomorphism \(\varphi_i(1) = i\):

This means, that all of them are actually homomorphisms. For different \(i,j \in \{0, \dots, n-1\}\) the homomorphisms \(\varphi_i\) and \(\varphi_j\) are different. So we really have \(n\) homomorphisms \(\blacksquare\)

My first thought was that it's only a permutation, but

$m \in M$ | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|

$\varphi(m) \in N$ | 0 | 3 | 0 | 3 | 0 | 3 |

is not a permutation, but a homomorphism.

## Distinct primes

**Theorem**: \(n, m \in \mathbb{P}, n \neq m \Rightarrow |H| = 1\)
**Proof**:

Let \(n, m \in \mathbb{P}, n \neq m\).

__Part 1__: \(1 \leq |H|\)

This follows directly from (V).

__Part 2__: \(|H| \leq 1\)

We know that

and

Case 1: \(m > n\)

Now the kernel can't be trivial anymore, so \(\# K_\varphi = m\). This means that everything is mapped to 0. There is only one homomorphism that does so.

Case 2: \(m < n\)

Now the image \(\varphi(M)\) can't be all of \(N\). This means \(\varphi(M) = 1\) which is again the 0-mapping \(\blacksquare\)

## Any $n$ and $m$

**Theorem**: \(|H| = gcd(n, m)\)
**Proof**:

First a sanity check: The theorems above are special cases of this theorem. Let's try to prove it.

Let \(n\) be composed of primes \(p_1, \dots, p_x\) (where \(p_i = p_j\) is allowed). Then \(N = \mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/p_1\mathbb{Z} \times \mathbb{Z}/p_2\mathbb{Z} \times \cdots \times \mathbb{Z}/p_x\mathbb{Z}\) according to the Chinese remainder theorem. The same is true for \(M\). As there are \(p_i\) homomorphisms between \(\mathbb{Z}/p_i\mathbb{Z}\) and \(\mathbb{Z}/p_j\mathbb{Z}\) with \(p_i = p_j\) and as you can take a \(p_i\) from the left and a \(p_j\) from the right you can combine the different homomorphisms. So it is basically a combinatoric problem. As everything (except for same primes) will only have 1 homomorphism, you have to multiply the number of homomophisms for each pair \((p_i, p_j)\). But this is simply the gcd \(\blacksquare\)

## $(\mathbb{Z}/n\mathbb{Z}, \cdot)$

What changes when we use \((\mathbb{Z}/n\mathbb{Z}, \cdot)\) and \((\mathbb{Z}/m\mathbb{Z}, \cdot)\)?

Well, first of all \(m\) and \(n\) have to be primes. Otherwise, not every element would have an inverse. Second, you have to exclude 0. Which means we only use units:

\((\mathbb{Z}/n\mathbb{Z}, \cdot)^\times\) and \((\mathbb{Z}/m\mathbb{Z}, \cdot)^\times\)

According to the German Wikipedia (source):

$(\mathbb{Z}/n\mathbb{Z})^\times$ is cyclic $:\Leftrightarrow n \in \{p^r, 2p^r | p \in \mathbb{P}, r \in \mathbb{N}_{\geq 1}\}$

So there is no simple way to reduce it to the same proofs. But I've created a little script that automatically finds homomorphisms.