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.