• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

How many Homomorphisms exist between Z/nZ and Z/mZ?

Contents

  • $m = n$
  • Distinct primes
  • Any $n$ and $m$
  • $(\mathbb{Z}/n\mathbb{Z}, \cdot)$
  • Related

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:

  1. $\varphi(M)$ is a group.
  2. $K_\varphi := \{m \in M | \varphi(m) = e_N\}$ is a group.
  3. Lagrange's theorem: $H \leq G \Rightarrow \#H | \# G$
  4. $\varphi(1)$ defines the complete homomorphism as $\varphi(n) = \varphi(1 + (n-1)) = \varphi(1) + \varphi(n-1)$
  5. $\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$ 012345
$\varphi(m) \in N$030303

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.

Related

  • Quick way to find the number of the group homomorphisms ϕ:Z3→Z6?

Published

Aug 27, 2013
by Martin Thoma

Category

Mathematics

Tags

  • Algebra 6

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor