mersenneforum.org > Math Number and identity of n-th roots of 1 mod p
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2009-08-28, 06:06 #1 SPWorley   Jul 2009 3110 Posts Number and identity of n-th roots of 1 mod p How can you count (and/or compute) the solutions for the relationship a^n ==1 mod p where p is prime, n is fixed? Obviously for some n, the answer is easy. If n=2, this is the square root, so a=1, a=-1 are the two solutions. This is likely elementary number theory, but I can't figure out how to attack it. Using a whole discrete-log attack seems like overkill, I'm hoping since these are the roots of unity there is some better theory. I can feel that the behavior when n is itself prime or composite will matter.
2009-08-28, 06:30   #2
Kevin

Aug 2002
Ann Arbor, MI

433 Posts

Quote:
 Originally Posted by SPWorley How can you count (and/or compute) the solutions for the relationship a^n ==1 mod p where p is prime, n is fixed? Obviously for some n, the answer is easy. If n=2, this is the square root, so a=1, a=-1 are the two solutions. This is likely elementary number theory, but I can't figure out how to attack it. Using a whole discrete-log attack seems like overkill, I'm hoping since these are the roots of unity there is some better theory. I can feel that the behavior when n is itself prime or composite will matter.
The primitive element theorem tells you that the multiplicative group (Z/Zp)* is isomorphic to the additive group (Z/Z(p-1)), where 1 in the multiplicative group corresponds to 0 in the additive group. This means your solutions of a^n=1 in (Z/Zp)* correspond to solutions of nb=0 in (Z/Z(p-1)). This in turn tells you that you should have gcd(n,p-1) solutions.

 2009-08-28, 07:42 #3 Kevin     Aug 2002 Ann Arbor, MI 433 Posts Actually, I'm not positive that the answer is gcd(p-1,n), but it's something very similar that should be easy to work out. And just to make it clear (too far after to edit), this means you can find all the solutions explicitly by finding a primitive element. I don't know if there's a more direct way that would require less computation.
2009-08-28, 08:17   #4
Dougy

Aug 2004
Melbourne, Australia

23·19 Posts

Quote:
 Originally Posted by Kevin The primitive element theorem tells you that the multiplicative group (Z/Zp)* is isomorphic to the additive group (Z/Z(p-1)), where 1 in the multiplicative group corresponds to 0 in the additive group. This means your solutions of a^n=1 in (Z/Zp)* correspond to solutions of nb=0 in (Z/Z(p-1)). This in turn tells you that you should have gcd(n,p-1) solutions.
That proof sounds fine to me. I checked quite a few cases on the computer to make sure.

2009-08-28, 11:08   #5
R.D. Silverman

Nov 2003

26×113 Posts

Quote:
 Originally Posted by Kevin Actually, I'm not positive that the answer is gcd(p-1,n), but it's something very similar that should be easy to work out. And just to make it clear (too far after to edit), this means you can find all the solutions explicitly by finding a primitive element. I don't know if there's a more direct way that would require less computation.

 2009-08-28, 17:18 #6 SPWorley   Jul 2009 31 Posts Kevin, wow, thanks very much. This is not an answer I expected... my amateur gut feeling was leading me in a very wrong direction. Thanks for the fast and expert answer. Now I have yet a new direction to explore (and learn about..) Even reading the description of the primitive element theorem online makes me hear "whooshing" noises as it flies over my head. But I can see how it has to do with the intersections of different sets in a field, so it helps with counting that set, and that's what I was originally asking for, so at least I see a tiny thread linking them now. Thanks yet again!
2009-08-28, 18:02   #7
Kevin

Aug 2002
Ann Arbor, MI

6618 Posts

Quote:
 Originally Posted by SPWorley Kevin, wow, thanks very much. This is not an answer I expected... my amateur gut feeling was leading me in a very wrong direction. Thanks for the fast and expert answer. Now I have yet a new direction to explore (and learn about..) Even reading the description of the primitive element theorem online makes me hear "whooshing" noises as it flies over my head. But I can see how it has to do with the intersections of different sets in a field, so it helps with counting that set, and that's what I was originally asking for, so at least I see a tiny thread linking them now. Thanks yet again!
Luckily we covered this exact question in one of my classes last semester. I don't think it's the kind of thing most people would come up with on their own, but it's a simple and powerful tool for these kinds of questions once you've seen it.

The basic idea behind the primitive element theorem is that if you're working mod p, you can always find some number whose powers generate all the non-zero elements. So for example, if you're working mod 11, 2 is a primitive element because you have (2^0,2^1,2^2,2^3,2^4,2^5,2^6,2^7,2^8,2^9)=(1,2,4,8,5,10,9,7,3,6). But 2 wouldn't be a primitive element working mod 7, because the only powers of 2 you get are 1,2,4. So when you're looking at the non-zero numbers and multiplication, instead of thinking about multiplying the numbers 1 through p-1 (mod p), you can think about about adding exponents from 0 to p-2 (mod p-1). It may seem a bit convoluted at first, but it really makes sense in theoretical situations like this because it let's you change a question about exponention in a multiplicative group (where the answer isn't immediately obvious) to a question about multiplication in an additive group (where things are more familiar and the answer becomes immediately apparent). In that sense, you think of this method as a kind of logarithm.

 Similar Threads Thread Thread Starter Forum Replies Last Post jcrombie Miscellaneous Math 51 2013-09-09 18:51 only_human Software 2 2012-05-11 13:43 ewmayer Lounge 12 2010-02-04 21:26 grandpascorpion Math 2 2009-11-10 20:44 fivemack Factoring 4 2008-03-04 05:04

All times are UTC. The time now is 11:46.

Sat Nov 28 11:46:21 UTC 2020 up 79 days, 8:57, 3 users, load averages: 1.13, 1.10, 1.14