# All homomorphisms from Z_n to Z_m

1. May 21, 2013

### ArcanaNoir

1. The problem statement, all variables and given/known data

Describe all group homomorphisms from $\mathbb{Z}_n$ to $\mathbb{Z}_m$.

2. Relevant equations

$\mathbb{Z}_n = {[0],[1],\dots ,[n-1]}$ with addition.

A homomorphism is an operation preserving map, ie $\phi (a\ast b)=\phi (a) \# \phi (b)$.

One especially important homomorphism property is that $\phi (a^k) = \phi (a)^k$.

We can describe each homomorphism entirely by its action on any element that generate the group.

3. The attempt at a solution

I am pretty sure there are $\text{gcd}(n,m)$ homomorphisms from $\mathbb{Z}_n$ to $\mathbb{Z}_m$.

Based on some examples I worked out, I believe the solution is:

let $[a]$ be any element which generates $\mathbb{Z}_n$

$$\phi ([a]) = \frac{n}{\text{gcd}(n,m)}\cdot k [a]$$ where $0\le k < \text{gcd}(m,n)$

2. May 21, 2013

### I like Serena

You are correct, but your "description" can use improvement and I believe it contains a mistake.

Let's simplify your generator a bit.
Instead of picking [a], it's easier to pick [1] as a generator.

Then candidates for the homomophisms are the ones defined by ϕ([1]).
The restriction is that ϕ(n[1]) = n ϕ([1]) = 0 mod m.
In other words m | n ϕ([1]).

Now let g = gcd(m,n), then there are numbers a and b such that $m=ga, n=gb, \gcd(a,b)=1$.

Then:
$$ga\ |\ gbϕ([1]) \\ a\ |\ bϕ([1]) \\ a\ |\ ϕ([1])$$
Do you see why?

So you're left with the question which and how many values of ϕ([1]) meet with the condition that $\frac m {\gcd(m,n)}$ divides ϕ([1]).

3. May 21, 2013

### ArcanaNoir

I did have [1] in mind for [a], but it should work on any generator.

I'm not sure what you are getting at with your last statement.

You mentioned you thought there was a mistake, but you also said I was correct?

4. May 21, 2013

### I like Serena

I believe the number of homomorphisms is indeed $\gcd(m,n)$, but the formula you gave for ϕ([a]) is not entirely correct.

Last edited: May 21, 2013
5. May 21, 2013

### ArcanaNoir

So are you saying some of the maps specified by my formula are redundant, some are missing, or some are plain wrong?

6. May 21, 2013

### I like Serena

Oh bollocks! I'm saying it should be:
$$\phi([1]) = \frac m {\gcd(m,n)} k[1]$$
with $0 \le k < \gcd(m,n)$.

Can you still smile? :shy:
This should be fun.

7. May 21, 2013

### ArcanaNoir

Oops. Thanks :)

8. May 21, 2013

### I like Serena

I guess of the choices offered, it fits "plain wrong".

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted