Number and identity of n-th roots of 1 mod p

[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.

[Kevin]

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.

[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.

[Dougy]

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.

[R.D. Silverman]

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.

Your answer is correct.

[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!

[Kevin]

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.