# What is the no. of injective group homomorphisms from $\mathbb Z_m$ to $\mathbb Z_n$ ( when $m \le n$)?

What is the no. of injective group homomorphisms from $\mathbb Z_m$ to $\mathbb Z_n$ ( when $m \le n$) ? I know it should not exceed $\gcd(m,n)$ , but I cannot calculate the exact number . Please help. Thanks in advance

The image of an injective homomorphism $C_m \to C_n$ must be a subgroup of order $m$.

By Lagrange's theorem, this is only possible when $m$ divides $n$, and in this case there is only one possible image because $C_n$ contains exactly one subgroup of each order dividing $n$.

The question then reduces to where we can send the generator of $C_m$.

We must send it to an element of order $m$ in $C_n$. There are exacty $\phi(m)$ such elements.

Therefore, there are $\phi(m)$ injective homomorphism $C_m \to C_n$ when $m$ divides $n$ and none otherwise.

($\phi$ here is Euler's totient function.)

Firstly, every element of $G= \mathbb{Z}_n$ has an order that divides $n$, and every element of $H= \mathbb{Z}_m$ has an order that divides $m$. Therefore, if $\varphi: H\to G$, then for $h\in H$, $\varphi(h)$ has an order that divides both $n$ and $m$, so it divides $g= \gcd (n, m)$.

Let $n = n' g$ and $m = m'g$. The elements that have the possible orders in $G$ are $\{n'i\ :\ i\in\{0,\dots, g-1\}\}$, and this subset is isomorphic to $K=\mathbb{Z}_g$. So, now we have to work out the number of homomorphisms from $H$ to $K$, which feels a bit more straightforward. Furthermore, the image of $1\in H$ (that's not the identity, its the element $1$) determines the entire homomorphism. And, if $\varphi(1) = k\in K$ ($k$ some integer), then the map $\varphi_k(i) = i\cdot k\ (\text{mod}\ g)$ is a homomorphism.

So, there are exactly $g$ homomorphisms.

But, you want the ones that are injective. So, for which $k$ is the map $\varphi_k$ injective? Well, we want $\varphi^{-1}( 0 )= \{0\}.$ Now, $i\cdot k = 0$ if and only if $g | i\cdot k$. So, for a given $m$, $n$ and $k$, is there an $i\in \{0,\ldots , m-1\}$ such that $i\cdot k = 0$? If $\gcd(k , g)\neq 1$ then $i = g/\gcd(k , g)$ will work, so $k$ must be relatively prime to $g$. Furthermore, is $m\geq g$, then $i=g$ works, so unless $m=g$, there are no such maps.

Therefore, if $m \not| n$ then there are no maps, and if $m | n$ there are $\phi(m)$ such maps, where $\phi$ is the totient function.

• The OP wants injective homomorphisms. – lhf Dec 18 '15 at 11:51
• Right you are my good sir/madam. – user24142 Dec 18 '15 at 11:52