# 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)(x^j) \; \; \; (1)$$

But assuming n < m we would get

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

So clearly we have to have $m | n.$

My questions are

1. Are there any other conditions on $n$ and $m$ besides $m |n.$

2. What exactly did I do wrong in $(1)$ ?

-
For the (1), What would happen if $i+j \ge m$? It always helps to define the map this way: $x^{i(n)} \mapsto x^{i(m)}$. Note that the map may not even be well-defined if $m \nmid n$. – user21436 Mar 16 '12 at 9:50
I'll write up a more detailed answer in an hour if it's still unanswered. This has its direct connection to the universal property of the quotient maps. – user21436 Mar 16 '12 at 9:52
I see that there are many contradictions if $m \not | n.$ My main concern is that $(1)$ seems like such a innocent algebraic manipulation that I would never suspect that something is wrong with it.I would like to hear an "aha" explanation on why one cannot apply the definition of a homomorphism on $f$ so blindlessly. – Jernej Mar 16 '12 at 10:02
– lhf Mar 16 '12 at 10:43
Well, either you use a homomorphism $\mathbb Z \rightarrow G$ (and talk about lifting that homomorphism) or you must face the fact that the Element $x^i$ does NOT determine the number $i$. – Blah Mar 16 '12 at 10:50

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.

-
I don't agree with your take on well-defined. The rule $x^i\mapsto y^i$ is well-defined in the set $\{x^0, x^1, \ldots, x^{n-1}\}$ because every element in this set has a single name. The problem is that this rule may not be a homomorphism because there is no guarantee that say $x^{2n-3}$ goes to $f(x)^{2n-3}=y^{2n-3}$. – lhf Mar 16 '12 at 16:47
@lhf: I agree that if we were specifying $0\leq i\lt n$, then the rule would yield a well-defined function. However, I don't see any such specification in the statement of the problem. It just says "sending $x^i$ to $y^i$", with no restrictions on $i$. Of course, checking that it is a homomorphism is important: I note it later in the post, I don't ignore it. – Arturo Magidin Mar 16 '12 at 16:58
Right, I assumed that $0\leq i\lt n$ was a natural implicit assumption. – lhf Mar 16 '12 at 17:04
@lhf: In that case, there is a different problem with the definition, which is that it would only make sense if $n\leq m$ (otherwise, $y^i$ for $i\geq m$ would be an "invalid name"). So we would end up with the conclusion that the map only makes sense and is a homomorphism when $m=n$; or else we need to treat the exponent differently in the domain (restricted to a special representation for the elements) but not the codomain, which seems somewhat perverse. – Arturo Magidin Mar 16 '12 at 18:21
I don't think $y^i$ is an invalid name. Just raise $y$ to $i$. The exponent is well defined, isn't it? – lhf Mar 16 '12 at 21:27

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)$?

-
+1 Why would anyone downvote this? Ok, it would be better to phrase it: "if $x^i=x^j$ does it follow that $y^i=y^j$?" It is somewhat dangerous to talk about values of $f$ before you know that $f$ is well defined. – Jyrki Lahtonen Mar 16 '12 at 14:07
it is perfectly acceptable to ask whether or not a definition of f makes f a function. – David Wheeler Mar 16 '12 at 15:22
@David, you're right, of course. I was just trying to guess, why there was a downvote for a little while. – Jyrki Lahtonen Mar 16 '12 at 15:44

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.

-
Will the down voter explain why? – user21436 Mar 16 '12 at 14:01
Why do you say that $y^{i+j}$ might not be an element of $H$? Of course it is an element of $H$! A group is a set closed under the group operation, so if $y$ is in there, so are all its powers. Also, are you sure that $i(m)$ is a standard notation for the remainder? Color my old-fashioned, but I think that binary mod should stay in programming classes. This last bit is just a pet-peeve of mine :-) – Jyrki Lahtonen Mar 16 '12 at 14:04
Well, $y^{i+j}$ is an element of the group. For example, if $H$ is a subgroup of the multiplicative group of complex numbers generated by the imaginary unit $i$, you seem to be saying that $i^5$ is not an element of $H$. Well, you are wrong: $$i^5=i^{4+1}=i^4\cdot i=1\cdot i=i.$$ Looks like it is in there! The same holds for all cyclic groups. I just picked a concrete one to make you realize your error. – Jyrki Lahtonen Mar 16 '12 at 14:16
No. I'm not prone to making a mistake. I check that my mappings are well-defined. If (granted, a big if in some cases) $y^i=y^j$ whenever $x^i=x^j$, then the mapping $x^i\mapsto y^i$ is trivially a homomorphism: $$f(x^i*x^j)=f(x^{i+j})=y^{i+j}=y^i*y^j=f(x^i)f(x^j)$$ AFTER I have checked that it is well-defined, then the above always makes sense, because in a cyclic group the power of an element is defined in such a way that we always have $y^{i+j}=y^i*y^j$ and so forth. – Jyrki Lahtonen Mar 16 '12 at 14:31
as a matter of fact, it IS true that $(i+j)$ (mod n) = $i$ (mod n) + $j$ (mod n). the problem is that $(i+j)$ (mod n) may not equal $i+j$ (mod m). – David Wheeler Mar 16 '12 at 15:32

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$.

-