What kind of expectations does your lecturer or TA have for proofs?
I am trying to find a group homomorphism from
After looking at it for a while, I noticed that works
This is a property of logarithms. Can I just justify it that way?
Also if the homorphism went from , we have ?
Thank you for your help.
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
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 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 as long as we understand that "log3" means something DIFFERENT in the group .
the inverse function is, of course:
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 powers of the generator to get the whole group? (By I mean the Euler totient function)
EDIT: Wait, I mean it seems like this would generally be the same for or vice versa
(p is prime)
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.