Homomorphism between cyclic groups

I have some confusion in relation to the following question.

Let $\langle x \rangle = G$, $\langle y \rangle = H$ be finite cyclic groups of order $n$ and $m$ respectively.
Let $f : G \mapsto H$ be the mapping sending $x^i$ to $y^i$.
Determine the conditions on $n$ and $m$ so that $f$ is going to be a homomorphism.

In verifying the definition of a homomorphism I seem to be able to conclude that there is no restriction on $n$ and $m$ since the definition of a homomorphic mapping is satisfied:

$$ f(x^i x^j) = f(x^{i+j}) = y^{i+j} = y^i y^j = f(x^i) f(x^j) \tag{1} $$

But assuming $n < m$ we would get

$$f(x^n) = f(e) = e \not = y^n$$

So clearly we have to have $m \mid n.$

My questions are

  1. Are there any other conditions on $n$ and $m$ besides $m \mid n.$
  2. What exactly did I do wrong in $(1)$?

Solutions Collecting From Web of "Homomorphism between cyclic groups"

The discussion about “well-defined” is perhaps a bit obscure. Here’s the problem:

Remember that in general, an element of $G$ may have many different “names.” For example, if $n=10$, then the element $x^{11}$ is equal to $x$; in fact, $x$ has infinitely many different “names” as a power of $x$:
$$\cdots = x^{-9} = x^1 = x^{11} = x^{21} = \cdots$$

The problem is that the definition of $f$ as given depends on the name of the element! That is, if we are furiously working and somebody hands us a power of $x$, say, $x^{3781}$, we are supposed to, unthinkingly, map it to $y^{3781}$. The problem is that $x^{3781}$ is the same element as $x$, which we are supposed to send to $y^1$. That means that unless $y^1=y^{3781}$, what we have is not really a function: because the same input, $x$ (who, when being teased by bullies is called “$x^{3781}$”) may be sent to $y^1$ or to $y^{3781}$, depending on what “name” we just heard for it.

Checking that the value of the function is the same regardless of what name we are using for an element, even though the function is defined in terms of the name, is called “checking that the function is ‘well-defined.'”

An example of a function that is not well-defined would be one in which the input is an integer, and the output is the number of symbols used to express that integer. For example, $f(3)$ would be $1$ (because 3 is only one symbol), but $f(4-1)$ would be $3$ (because we are using 4, -, and 1). This is not well defined as a function of the integers, because $3$ is the same as $4-1$, but $f$ assigns it two different outputs.

So in order for the expression given to actually define a function, we need the following to be true:
$$\text{if }x^i=x^j,\text{ then }y^i = f(x^i)\text{ is equal to }y^j=f(x^j).$$
Now, $x^i=x^j$ if and only if $i\equiv j\pmod{n}$; and $y^i=y^j$ if and only if $i\equiv j\pmod{m}$. Therefore, we need:
$$\text{if }i\equiv j\pmod{m},\text{ then }i\equiv j\pmod{n}.$$
In other words: every number that is a multiple of $m$ must be a multiple of $n$.

This is equivalent to $n|m$.

In fact, you noticed that in what you wrote, because $x^n=e$, so we need $f(x^n)$ to be the same as $f(x^0)$.

Once we know that $n|m$, then $f$ is well defined. Once it is well-defined, we can start verifying that it is indeed a homomorphism (it is). Technically, it’s incorrect to start working to see if it is a homomorphism before you even know whether or not it is a function.

Note that the condition actually works if we allow $G$ or $H$ to be infinite cyclic groups, if we call infinite cyclic groups “groups of order $0$”. Then $i\equiv j\pmod{0}$ means $i=j$, every number divides $0$, but the only multiple of $0$ is $0$. So if $G$ is infinite cyclic then the value of $n$ does not matter; if $H$ is infinite cyclic then we must have $G$ infinite cyclic.

You may want to check first if the map is well defined, ie., if $x^i=x^j$ does it follow that $f(x^i)=f(x^j)$?

I am not sure if this completely explains why the naive calculations in $(1)$ are not valid. Here is my go at it:

I’ll list down several points of concern.

  • Firstly your map $x^i \mapsto y^i$ is very naive that it misses some essential details.

For convenience of notation, I prefer to look at this as $\varphi(\bar i)=\bar i$ if you’ll allow me to do so. This is also naive but to some extent captures what is happening.

So, an equivalence class $\bmod n$ is mapped to the same equivalence class $\bmod m$ under $\varphi$. This bit of information is missed in $x^i \mapsto y^i$. This explains my comment under your question that you will want to write your maps as $x^{i(n)} \mapsto y^{i(m)}$. This notation makes things more transparent.

That you have dicovered that $m \mid n$, it can be obtained through the universal property of the quotients, which I will write about later.

The quotient map $G \to G/H$ factors over $G \to G/K$ if and only if $K \subseteq H$. That is there is a map from $G/H$ to $G/K$ if and only if $K \subseteq H$.

Proof: Please Go through Dummit and Foote’s description in their Abstract Algebra in the section $\S3.3$ Isomorphism Theorems.

Now consider your cyclic groups as $\Bbb Z/n\Bbb Z$ and $\Bbb Z/m\Bbb Z$ and observe that above condition will tell you, $m\Bbb Z \subseteq n \Bbb Z$ whic happens if and only if…


As you had earlier in your comments observed, the map won’t even be well defined if $m \nmid n$.


I’ll leave it to you as a challenge to use this blooper to prove that two groups of same order are isomorphic, which really is not the case. Hint: Cyclic groups exist for any given order.

The rule $x^i\mapsto y^i$ gives a perfectly well-defined function in the set $\{x^0, x^1, \ldots, x^{n-1}\}$. However, for that rule to be a homomorphism we need that $x^{i+j} \mapsto y^{i+j}$ for all $i$ and $j$. To find where $x^{i+j}$ goes we need to reduce $i+j \bmod n$ to a $k$ in $\{0,1,\ldots,n-1\}$ and we need that $k \equiv i+j \bmod m$. In other words, we need $k \equiv k' \bmod n \implies k \equiv k' \bmod m$ and this can only happen when $m\mid n$.

THEOREM:

Define $f:\langle x \rangle \to \langle y \rangle$,
where the orders of
$\langle x \rangle$ and $\langle y \rangle$
are n and m respectively,
by $f(x) = y^u$. Then f is a well-defined homomorphism if and only if
$\frac{m}{\gcd(m,n)} \mid u$.

PROOF:
Suppose that the mapping
$f:\langle x \rangle \to \langle y \rangle$
is a well-defined homomorphism.

Let
$f(x) = y^u$ for some non negative integer u.

We must also have
$ 1 = f(x^n) = y^{un}$

Then
$ m \mid un$.
Let
$g = \gcd(m, n)$.
Then
$\frac m g \mid u \frac n g$.
It follows that
$\frac m g \mid u$.

The converse is pretty straightforward.

Suppose we define $f:\langle x \rangle \to \langle y \rangle$
by $f(x) = y^u$ where $\frac{m}{\gcd(m,n)} \mid u$

The only real problem with this definition is “Is it well defined?”
Since the order of $\langle x \rangle$ is $n$:

\begin{align*}
x^a = x^b &\Rightarrow a \equiv b \mod n \cr
&\Rightarrow ua \equiv ub \mod {un} \cr
&\Rightarrow ua \equiv ub \mod {\frac{mn}{\gcd(m,n)}} \cr
&\Rightarrow ua \equiv ub \mod {m} \cr
&\Rightarrow y^{ua} = y^{ub}\cr
&\Rightarrow f(x^a) = f(x^b)
\end{align*}

Linearity is pretty obvious, so $f$ is a well-defined homomorphism.

So, if you want $f(x^i) = y^i$, then you want $f(x) = y$.
You must therefore have $\frac{m}{\gcd(m,n)} \mid 1$. Which implies $m \mid n$.

Conversely, if $m \mid n$ and $f(x) = y$, it follows that $f(x^i) = y^i$.