20090828, 06:06  #1 
Jul 2009
11111_{2} Posts 
Number and identity of nth 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 discretelog 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. 
20090828, 06:30  #2  
Aug 2002
Ann Arbor, MI
433 Posts 
Quote:


20090828, 07:42  #3 
Aug 2002
Ann Arbor, MI
661_{8} Posts 
Actually, I'm not positive that the answer is gcd(p1,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. 
20090828, 08:17  #4  
Aug 2004
Melbourne, Australia
98_{16} Posts 
Quote:


20090828, 11:08  #5  
Nov 2003
2^{2}×5×373 Posts 
Quote:


20090828, 17:18  #6 
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! 
20090828, 18:02  #7  
Aug 2002
Ann Arbor, MI
433 Posts 
Quote:
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 nonzero 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 nonzero numbers and multiplication, instead of thinking about multiplying the numbers 1 through p1 (mod p), you can think about about adding exponents from 0 to p2 (mod p1). 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. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Bicurvious Identity  jcrombie  Miscellaneous Math  51  20130909 18:51 
Cpu Identity mismatch  only_human  Software  2  20120511 13:43 
I had my identity stolen by '24'  ewmayer  Lounge  12  20100204 21:26 
Useful Identity?  grandpascorpion  Math  2  20091110 20:44 
A missing identity  fivemack  Factoring  4  20080304 05:04 