1. ## Group homomorphism

Hello,

I am trying to find a group homomorphism from $( \mathbb{Z} /7 \mathbb{Z})^x \rightarrow \mathbb{Z} / 6 \mathbb{Z}$

After looking at it for a while, I noticed that $\phi = ln(x)$ works

i.e $ln(x * y) = ln(x) + ln(y)$

This is a property of logarithms. Can I just justify it that way?

Also if the homorphism went from $\mathbb{Z} / 6 \mathbb{Z} \rightarrow \mathbb{Z} /7 \mathbb{Z})^x$ , we have $\psi = e^x$?

2. ## Re: Group homomorphism

Hey Jame.

What kind of expectations does your lecturer or TA have for proofs?

3. ## Re: Group homomorphism

I think we would have to show that the function we supply satisfies the definition of group homomorphism (which it does).

4. ## Re: Group homomorphism

I'm just wondering if the logarithm is in the natural base or some other base?

5. ## Re: Group homomorphism

e, the natural one

6. ## Re: Group homomorphism

Won't you have non-integer values in one of the spaces?

7. ## Re: Group homomorphism

That's what I was worried about. I was not sure if the final value had to be in the group.

8. ## Re: Group homomorphism

Yeah it has to (remember the closure axiom of a group).

9. ## Re: Group homomorphism

you're sort of on the right track, what you are looking for is called a discrete logarithm. what you really need to finish this idea is a generator for $(\mathbb{Z}/7\mathbb{Z})^{\times}$

obviously 1 won't work, since 1 has order 1. how about 2? let's try it:

22 = 4 <--2 isn't order 2
23 = 8 = 1 (mod 7) <--2 has order 3. darn.

ok, now let's try 3:

32 = 9 = 2 (mod 7) <--3 isn't order 2.
33 = 27 = 6 (mod 7) <--3 isn't order 3.

since $(\mathbb{Z}/7\mathbb{Z})^{\times}$ has order 6, this means 3 must be of order 6, so 3 is a generator.

so the isomorphism you need is:

30 = 1<--->0
31 = 3<--->1
32 = 2<--->2
33 = 6<--->3
34 = 4<--->4
35 = 5<--->5

we can write this as $k \to \log_3(k)$ as long as we understand that "log3" means something DIFFERENT in the group $(\mathbb{Z}/7\mathbb{Z})^{\times}$.

the inverse function is, of course: $n \to 3^n$

10. ## Re: Group homomorphism

I see. It seems like the important thing to recognize here is that the group of units mod 7 is generated by powers of 3.

For (Z mod nZ)^x, would we need $\phi(n)$ powers of the generator to get the whole group? (By $\phi$ I mean the Euler totient function)

EDIT: Wait, I mean it seems like this would generally be the same for $(\mathbb{Z} / p \mathbb{Z})^x \rightarrow \mathbb{Z} / (p-1) \mathbb{Z}$ or vice versa

(p is prime)

11. ## Re: Group homomorphism

yes this only works for the units of Zp. for example, the units of Z8 are not cyclic.

finding a primitive element (generator) for Zp is harder than it seems. this is because it's hard to predict in advance what φ(p-1) is going to be.the odds are pretty good, though, of finding one (a generator) in your first few tries. usually 2 or 3 works, sometimes you have to use 5, or 7, or 6. you have to have a fairly large p before one of these will not work.

once you have one, however, you can then use it to create a discrete log table, which allows you to multiply numbers in Zp, by adding numbers in Zp-1. this is how a lot of computers actually compute modular arithmetic (mod p), since storing the look-up table for the discrete log actually allows bigger numbers to be stored with a smaller register. this is useful when doing linear algebra over a finite field, which is often employed in various types of coding schemes that use "checksums" to ensure data is not corrupted (this, for example, is one way cash registers that use UPC codes ensure that manual entries are not accidentally "mis-keyed" by the cashier, and how certain disk data systems safeguard data in the event of disk failure).

so prime numbers (and group theory) turn out to be very practical things after all.