Multiplicative Groups of Order (p-1)Date: 05/12/2000 at 09:47:12 From: Jeff Olbrys Subject: Multiplicative groups of order (p-1), p = prime I have seen several passing references that multiplicative groups of order (prime-1) are cyclic, but can't find a proof. Euler's generalization of Fermat's theorem gives us a^(p-1) = 1 (mod p) but (p-1) is not necessarily minimal. In Z mod 7, 3 and 5 are the generators of the multiplicative group. In Z mod 11, the generators are 2, 6, 7 and 8. I don't see a pattern here to suggest an approach. Date: 05/12/2000 at 15:07:39 From: Doctor Schwa Subject: Re: Multiplicative groups of order (p-1), p = prime Finding the generators is difficult, but proving that it's cyclic is not so hard. There's a nice theorem which says: in the integers mod m there will be exactly phi(d) elements of order d, for each d that divides phi(m). If you need some help on how to prove this, please write back. - Doctor Schwa, The Math Forum http://mathforum.org/dr.math/ Date: 11/30/2000 at 08:39:45 From: Jeffrey Olbrys Subject: Re: Multiplicative groups of order (p-1), p = prime Dr. Schwa, Thanks for your earlier help. After reading your reply, I went back to my Number Theory book (we used Stark's) and filled in the details. I now need a topic for a little research paper. I was wondering about the question of finding those generators - the theorem proves existence, and provides not a clue about how to actually find one. (For small p, brute force calculation will work, but I'd hate to have to do that for large p.) Do you think this is an interesting question? Can it lead me to about 10 pages worth of "meaty" math? Thanks in advance for your consideration. Jeff Olbrys Date: 11/30/2000 at 15:14:57 From: Doctor Schwa Subject: Re: Multiplicative groups of order (p-1), p = prime Jeff, I'm glad my small hint was enough. Sounds like it took some research on your own. Well done. I think there's a LOT more than 10 pages of meaty math in actually finding the generators (mod p). In fact, I worked on this problem for quite a while when I took number theory. The answer wasn't in my text, and I'm sure I generated FAR more than 10 pages in trying to figure it out (unsuccessfully, I might add). Once you have one generator, of course, the powers of it give you all the rest. (That is, the generator raised to powers that are relatively prime to p-1.) On the Web, I found some Mathematica code that determines the generator: Help With PrimitiveRoot - MathGroup archive http://hilbert.math.hr/arhive/mathgroup/1998/10/0135.html but unfortunately I'm not fluent enough in Mathematica to figure out what algorithm they're using. There's something recursive going on, to find the generator for the group of units mod p^k in terms of the one mod p, but I can't quite understand exactly what's going on when it gets down to that base case. I'll do a little more research and see if I can get you pointed in the right direction. Anyway, the problem of finding a generator for the cyclic group of multiplication mod p is certainly hard enough; I wonder if it might be too hard. I'd prefer to find a generator for the additive group ;-). I found some interesting problems on the net here and there, including these from a course on group theory: Math 302: Group Theory Dr. Ken Pledger, School of Mathematical and Computing Sciences, Victoria University of Wellington, New Zealand http://www.mcs.vuw.ac.nz/courses/MATH302/assignments/ass_4/ass_4.html Assignment 4 Solutions: http://www.mcs.vuw.ac.nz/courses/MATH302/assignments/sol_4/sol_4.html which might well give you other ideas for a project. - Doctor Schwa, The Math Forum http://mathforum.org/dr.math/ Date: 12/01/2000 at 10:19:25 From: Doctor Rob Subject: Re: Multiplicative groups of order (p-1), p = prime Thanks for writing to Ask Dr. Math, Jeff. The matter of finding a primitive root modulo n is of some interest. Yes, it could lead to 10 pages of meaty math. The proof that primitive roots exist modulo p goes as follows. Let (a,p) = 1, and let h be the least exponent such that a^h = 1 (mod p). Then h is called the order of a modulo p. By Lagrange's theorem on the order of elements and the order of a group, h | p-1. Now a^i for i = 1, ..., h are all distinct, by the definition of h. a^i has order modulo p exactly h/(i,h). That means that the ones with order h modulo p have (i,h) = 1. By the definition of the Euler phi function, there are exactly phi(h) of these with order h modulo p. Thus for each h dividing p-1 there are either phi(h) or 0 elements of order h modulo p. Let n(h) be that number. Then, since every nonzero element modulo p has some order dividing p-1, p - 1 = SUM n(h) <= SUM phi(h) = p - 1 h|p-1 h|p-1 with equality if and only if n(h) = phi(h) for all h | p-1. Since equality is evident, we have that for all h | p-1, there are exactly phi(h) elements of order h modulo p. In particular, there are exactly phi(p-1) elements of order p-1 modulo p, that is, phi(p-1) primitive roots modulo p. phi(n) is always positive, so primitive roots always exist. The finding of a primitive root modulo p depends on knowing the complete prime-power factorization of p-1. If this is not known, then you cannot prove that any particular number is a primitive root. That means that for most very large values of p, we cannot solve the problem. We assume below that the prime factorization of p-1 is known: r p - 1 = PRODUCT q(i)^e(i) i=1 Any particular integer x with 1 <= x <= p-1 is a primitive root if and only if for every i with 1 <= i <= r, x^[(p-1)/q(i)] =/= 1 (mod p) Proof of this one way is easy: if the ith of these powers were congruent to 1 modulo p, then the order of x would be at most (p-1)/q(i) < p - 1, so x would not be primitive. Proof the other way is also easy. If the order of x were h < p - 1, then pick an i such that q(i) | (p-1)/h. Then x^[(p-1)/q(i)] = (x^h)^([p-1]/[q(i)*h]) (mod p) = 1^([p-1]/[q(i)*h]) (mod p) = 1 (mod p) This fact is how you test a number for being a primitive root. The obvious, brute-force approach to finding a primitive root is to try x = 2, 3, 4, 5, ... in order to see if any of them is a primitive root. Actually, this is quite a good method, because there are so many primitive roots that you are likely to find one quickly. Furthermore, you can speed this up a little by skipping x's which are perfect powers, like 4, 8, 9, 16, 25, 27, 32, 36, etc. You can do this because if x = y^k for some k, then the order of x is a divisor of the order of y, which is < p-1 (or you would have stopped on finding y < x). Another systematic way is as follows. Set z = p-1. Pick a random x, 1 < x < p. Determine for which i values you have q(i) | z and x^[(p-1)/q(i)] =/= 1 (mod p) Then for each such i, divide z by q(i)^e(i), and compute s(i) = x^[(p-1)/q(i)^e(i)] (mod p) Each s(i) is picked so that its order is exactly q(i)^e(i). If z > 1, pick another random x, and repeat the above. When z = 1, compute r a = PRODUCT s(i) (mod p) i=1 and that will be your primitive root (because its order will be the product of the powers q(i)^e(i), which is p-1). Example: Find a primitive root modulo 109. The prime factorization of 108 is 2^2 * 3^3. Thus q(1) = 2, q(2) = 3, e(1) = 2, e(2) = 3, and r = 2. Set z = 108. Start with x = 23. It turns out that 23^(108/2) = 23^54 = 108 (mod 109) 23^(108/3) = 23^36 = 1 (mod 109) Thus we divide z by 2^2, so z = 27. We also compute s(1) = 2^27 = 33 (mod 109). (Observe that the order of 33 is 4 modulo 109.) Since z = 4 < 108, we continue with x = 83. It turns out that 83^(108/3) = 83^36 = 63 (mod 109) Thus we divide z by 3^3, so z = 1. We also compute s(2) = 83^(108/27) = 48 (mod 109) (Observe that the order of 48 is 27 modulo 109.) Since z = 1, we stop, and find the primitive root a = s(1)*s(2) = 33*48 = 58 (mod 109) If we had done a brute-force search, we would have had to try four values, x = 2, 3, 5 and 6 before finding that x = 6 is also a primitive root. I hope that this has been helpful. If you have further questions, please write again. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/