Question on cyclic groups (addition mod n)

[vertices]

I am trying to show show that there is no homomorphism from Zp1 to Zp2. if p1 and p2 are different prime numbers.

(Zp1 and Zp2 represent cyclic groups with addition mod p1 and p2 respectively).

I am not sure how to do this but here are some thoughts;

For there to be a homomorphism we require:

F(g.h)=F(g)F(h) *

where F maps Zp1 to Zp2.

From the information in the question - we can say the following (not sure if it is relavent): Since p1 is a prime number, from Lagranges Theorem, there are no (non trivial) subgroups in Zp1, so every pair of elements in this group must satisfy *. And because z1 and z2 are unequal, the homomorphism must be such that more than one element of one group maps to just one element of the other.

Any thoughts on where to go from here?

 

[jambaugh]

Consider the mapping:
$$f: \mathbb{Z}_p \to \mathbb{Z}_q$$
where
$$f(z) = 0_q$$
for $$z \in \mathbb{Z}_p$$
and $$0_q$$ being the additive identity in $$\mathbb{Z}_q$$
It is a homomorphism so your hypothesis is false as it stands.
[Edit: This by the way is a homomorphism between any two groups so its a very handy example!]

So I assume you are looking for a proof that there is no non-trivial homomorphism.

I would suggest you first consider the case where you do have a homomorphism but that p and q (or p1 and p2) are not necessarily prime and distinct. Then see what you can do with that.

Also recall that the 1 element in each cyclic group generates all the elements, i.e. it is an element of order p in Zp. So that's probably your starting point for any proofs or derivations.

Also recall that the "product" is typically written as + for abelian groups such as these cyclic groups which corresponds to the . in the abstract expression of a homomorphism. That may initially confuse you if you're worrying about the bigger issues. So using + we translate the homomorphism definition to:
f(a+b) = f(a) + f(b).

I would also suggest you look at "[URL Theorem[/URL].

Think in terms of the relationship between the order of an element and the order of its image under a homomorphism. (They won't always be identical!)
I think it will be very useful in this endeavor.

 

[vertices]

Many thanks for your reply jambaugh:)

Can I ask a couple of not very clever questions to clarify some of things you said (I tend to do loads of these):

Consider the mapping:
$$f: \mathbb{Z}_p \to \mathbb{Z}_q$$
where
$$f(z) = 0_q$$
for $$z \in \mathbb{Z}_p$$
and $$0_q$$ being the additive identity in $$\mathbb{Z}_q$$

Why does $$f(z) = 0_q$$ for any z in $$Z_p$$?

say p=5 and q=7

then Zp={0.1.2.3.4} and Zq={0,1,2,3,4,5,6} (ie the same elements as Zp as well as 5 and 6.

Surely any element in p would just map to the corresponding element in q, eg. 2 in p would map to 2, not to 0?

in the abstract expression of a homomorphism. That may initially confuse you if you're worrying about the bigger issues. So using + we translate the homomorphism definition to:
f(a+b) = f(a) + f(b).

Yes, thanks for pointing this out.

Can I ask though (more like check), is a.b = (a+b)modp (a,b are elements in Zp)

and is f(a.b)=f((a+b)modp)=[(a+b)modp]modq

And if f really is a non trivial homomorphism, ie. if

f(a.b)=f(a).f(b)

does the RHS equal amodq + bmodq? (ie is the composition on the addition mod q?)

thanks.

 

[JSuarez]

You might also remember that the image of an homomorphism is always a subgroup. Now combine this with Lagrange's theorem.

 

[wofsy]

I am trying to show show that there is no homomorphism from Zp1 to Zp2. if p1 and p2 are different prime numbers.

(Zp1 and Zp2 represent cyclic groups with addition mod p1 and p2 respectively).

I am not sure how to do this but here are some thoughts;

For there to be a homomorphism we require:

F(g.h)=F(g)F(h) *

where F maps Zp1 to Zp2.

From the information in the question - we can say the following (not sure if it is relavent): Since p1 is a prime number, from Lagranges Theorem, there are no (non trivial) subgroups in Zp1, so every pair of elements in this group must satisfy *. And because z1 and z2 are unequal, the homomorphism must be such that more than one element of one group maps to just one element of the other.

Any thoughts on where to go from here?

Think about this question. Is the image of a homomorpism a subgroup?

 

[vertices]

You might also remember that the image of an homomorphism is always a subgroup. Now combine this with Lagrange's theorem.

Think about this question. Is the image of a homomorpism a subgroup?

I am tempted to argue that Lagrange's theorem implies that neither Zp nor Zq have any subgroups of orders of less than p and q respectivly (as they p and q are prime numbers), but if F is a homomorphism we require that the images of Zp belong to a subgroup of Zq, and since there are no subgroups in Zq - we can't have a homomorphism.

However, can't the whole group, Zq, be classed as a subgroup (a "trivial subgroup") of Zq? I seem to recall that it can...

 

[JSuarez]

The trivial $$\left\{0\right\}$$ subgroup and the whole group $$\mathbb Z_q$$ are indeed subgroups of $$\mathbb Z_q$$(the term is "improper" subgroups). And the homomorphism's images doesn't only belong to a subgroup, they are a subgroup.

But, excluding the trivial (identical to 0) homomorphism, is it possible that the whole group $$\mathbb Z_q$$ be the image of an homomorphism? What happens if $$p<q$$ (easy)? And if $$q<p$$ (a little harder).

 

[vertices]

The trivial $$\left\{0\right\}$$ subgroup and the whole group $$\mathbb Z_q$$ are indeed subgroups of $$\mathbb Z_q$$(the term is "improper" subgroups). And the homomorphism's images doesn't only belong to a subgroup, they are a subgroup.

But, excluding the trivial (identical to 0) homomorphism, is it possible that the whole group $$\mathbb Z_q$$ be the image of an homomorphism? What happens if $$p<q$$ (easy)? And if $$q<p$$ (a little harder).

Okay: If p<q the images of Zp are a subset of Zq (as they only map to p out of q elements in Zq). From Lagrange's theorem, the subset is not a subgroup, hence there is no homomorphism.

If p>q, the elements of Zp must map to all the elements of Zq (if I understand correctly), hence the images are an improper subgroup of Zq, so there can be a non trivial homomorphism from Zp to Zq...

 

[JSuarez]

The first part is OK. The second, not so much.

 

[wofsy]

The trivial $$\left\{0\right\}$$ subgroup and the whole group $$\mathbb Z_q$$ are indeed subgroups of $$\mathbb Z_q$$(the term is "improper" subgroups). And the homomorphism's images doesn't only belong to a subgroup, they are a subgroup.

But, excluding the trivial (identical to 0) homomorphism, is it possible that the whole group $$\mathbb Z_q$$ be the image of an homomorphism? What happens if $$p<q$$ (easy)? And if $$q<p$$ (a little harder).

right. You can always have the trivial homomorphism or the subgroup could be the whole group which you know is impossible. Using the definition of a homomorphism it is immediate that its image is a subgroup.

 

[jambaugh]

Many thanks for your reply jambaugh:)
...
Surely any element in p would just map to the corresponding element in q, eg. 2 in p would map to 2, not to 0?

Why should it? A mapping can map anything to anything it wants. For the mapping to be a homomorphism it need only satisfy the homomorphism property. Thus f:Z->Z where f(n)=2n is a homomorphism of Z as an additive group. e.g. f(3+4) = 2(3+4)=2(3) +2(4) =f(3)+f(4).

Can I ask though (more like check), is a.b = (a+b)modp (a,b are elements in Zp)

right where . is "abstract product" and + is arithmetic addition.

and is f(a.b)=f((a+b)modp)=[(a+b)modp]modq

And if f really is a non trivial homomorphism, ie. if

f(a.b)=f(a).f(b)

does the RHS equal amodq + bmodq? (ie is the composition on the addition mod q?)
thanks.

Careful there, f(a + b modulo p) = f( a + b modulo p) modulo q. You don't loose the function...
you then get f(a+b mod p) = f(a)+f(b) modulo q.
[assume a and b are in the set so no need to mod by p themselves but when adding you mod p. Assume likewise f(anything) is in the other set so no need to mod q but when adding you do.]

Now to better understand the theorem you are trying to prove look at some non-prime examples.
Consider $$\mathbb{Z}_{12}$$
What is the order of the element 2? (equivalent to what is the order of the group it generates.)
{0, 2, 2+2=4, 2+2+2=6, 2+2+2+2=8, 2+2+2+2+2=10}
the next element is 2+2+2+2+2+2 = 12 = 0 mod 12 so we're repeating ourselves.

So the order of 2 (and the subgroup it generates) is 6 which by Lagrange's theorem must divide the order of $$\mathbb{Z}_{12}$$ which of course is 12.

Something else to always remember. Any homomorphism must always map the identity to the identity. With that in mind consider the order of z and the order of f(z), what is the relationship between how long it takes to return to the identity in each string:
0, f(0)=0
z, f(z)
z+z, f(z+z) = f(z)+f(z)
z+z+z, f(z)+f(z)+f(z)
and so on...
Supposing the order of z is say k, then what can you say for certain about the order of f(z)?
[EDIT: Test your answer on my trivial homomorphism from the first post.]

[EDIT 2: BTW If you haven't covered Lagrange's theorem yet you probably shouldn't invoke it directly. It is very easy to prove itself for the special case of cyclic groups.

 

[vertices]

Why should it? A mapping can map anything to anything it wants. For the mapping to be a homomorphism it need only satisfy the homomorphism property. Thus f:Z->Z where f(n)=2n is a homomorphism of Z as an additive group. e.g. f(3+4) = 2(3+4)=2(3) +2(4) =f(3)+f(4).

right where . is "abstract product" and + is arithmetic addition.

Careful there, f(a + b modulo p) = f( a + b modulo p) modulo q. You don't loose the function...
you then get f(a+b mod p) = f(a)+f(b) modulo q.
[assume a and b are in the set so no need to mod by p themselves but when adding you mod p. Assume likewise f(anything) is in the other set so no need to mod q but when adding you do.]

Thanks for making this clear.

Supposing the order of z is say k, then what can you say for certain about the order of f(z)?

Aahhh.

z+z+z+(..k times) = 0_p

so f(z+z+z (k times) ) = f(0_p) = 0_q (from the fact that the identity of Z_p must map to the identity of Z_q)

So if there is a homormorphism, the LHS is f(z)+f(z)+f(z)+ (..k times)=0_q. Hence the order of f(z) must be a multiple of k.

I think I can give a more complete proof of the original problem now:

If p and q are prime numbers, then:

If we have z+z+z+z+.. (q times)

=>f( z+z+z+z+.. (q times) )= f(z)+f(z)+f(z)+.. (q times) (if there is a homomorphism)

The RHS is 0_q.

Now, the LHS we can write as f(z*p+(q-p)*z)=f(z*p)+f((q-p)*z) (by the homomorphism property)

But z*p=0_p (as we return to the identity), therefore f(z*p)=0_q.

Therefore, there is a homomorphism between Zp and Zq if and only if f((q-p)*z)=0.

Since q and p are different prime numbers, q-p cannot be a multiple of q and hence we can't return to the identity if we only add 'q-p' copies of of z together.

 

[wofsy]

Thanks for making this clear.



Aahhh.

z+z+z+(..k times) = 0_p

so f(z+z+z (k times) ) = f(0_p) = 0_q (from the fact that the identity of Z_p must map to the identity of Z_q)

So if there is a homormorphism, the LHS is f(z)+f(z)+f(z)+ (..k times)=0_q. Hence the order of f(z) must be a multiple of k.

I think I can give a more complete proof of the original problem now:

If p and q are prime numbers, then:

If we have z+z+z+z+.. (q times)

=>f( z+z+z+z+.. (q times) )= f(z)+f(z)+f(z)+.. (q times) (if there is a homomorphism)

The RHS is 0_q.

Now, the LHS we can write as f(z*p+(q-p)*z)=f(z*p)+f((q-p)*z) (by the homomorphism property)

But z*p=0_p (as we return to the identity), therefore f(z*p)=0_q.

Therefore, there is a homomorphism between Zp and Zq if and only if f((q-p)*z)=0.

Since q and p are different prime numbers, q-p cannot be a multiple of q and hence we can't return to the identity if we only add 'q-p' copies of of z together.

This may help you summarize youjr proof.
The image of a homomorphism is a subgroup.
The homomorphic image of a cyclic group of prime order is either the trivial group or another copy of the same cyclic group of prime order.

The order of a subgroup divides the order of the group.

 

[jambaugh]

...
So if there is a homormorphism, the LHS is f(z)+f(z)+f(z)+ (..k times)=0_q. Hence the order of f(z) must be a multiple of k.

Careful there! Try it with f(z) = 2z where both p and q are 6.

1+1+1+1+1+1=6 =>0₆

f(1)+f(1)+f(1)+f(1)+f(1)+f(1) = 0 likewise
but 2+2+2=6 so 2 has order 3. 3 is not a multiple of 6.

 

[vertices]

Careful there! Try it with f(z) = 2z where both p and q are 6.

1+1+1+1+1+1=6 =>0₆

f(1)+f(1)+f(1)+f(1)+f(1)+f(1) = 0 likewise
but 2+2+2=6 so 2 has order 3. 3 is not a multiple of 6.

Yes, sorry, ofcourse I meant factor not 'multiple'.