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

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

Contents

  • How many Homomorphisms exist between Z/nZ and Z/mZ?
    • $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