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$:
\begin{align} \varphi(a) + \varphi(b) &= (ai \mod n) + (bi \mod n)\ &= ai + bi \mod n\ &= (a+b)i \mod n\ &= \varphi(a+b) \end{align}
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 \begin{align} \stackrel{(I)+(III)}{\Rightarrow} &# \varphi(M) | # N\ \stackrel{n \in \mathbb{P}}{\Rightarrow} &# \varphi(M) \in {1, n} \end{align}
and
\begin{align} \stackrel{(II)+(III)}{\Rightarrow} &# K_\varphi | # M\ \stackrel{m \in \mathbb{P}}{\Rightarrow} &# K_\varphi \in {1, m} \end{align}
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.