Group homomorphism

**Jame** · February 11th 2013, 05:05 PM

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

Thank you for your help.

**chiro** · February 11th 2013, 05:21 PM

Hey Jame.

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

**Jame** · February 11th 2013, 05:27 PM

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

**chiro** · February 11th 2013, 05:39 PM

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

**Jame** · February 11th 2013, 05:41 PM

e, the natural one

**chiro** · February 11th 2013, 05:53 PM

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

**Jame** · February 11th 2013, 06:05 PM

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

**chiro** · February 11th 2013, 06:06 PM

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

**Deveno** · February 11th 2013, 11:12 PM

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:

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

ok, now let's try 3:

3² = 9 = 2 (mod 7) <--3 isn't order 2.
3³ = 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:

3⁰ = 1<--->0
3¹ = 3<--->1
3² = 2<--->2
3³ = 6<--->3
3⁴ = 4<--->4
3⁵ = 5<--->5

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

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

**Jame** · February 12th 2013, 08:00 AM

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)

**Deveno** · February 12th 2013, 11:31 AM

yes this only works for the units of Z_p. for example, the units of Z₈ are not cyclic.

finding a primitive element (generator) for Z_p 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 Z_p, by adding numbers in Z_p-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.

Thread: Group homomorphism

LinkBack

Thread Tools

Display