mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-08-28, 06:06   #1
SPWorley
 
Jul 2009

3110 Posts
Default 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.
SPWorley is offline   Reply With Quote
Old 2009-08-28, 06:30   #2
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

433 Posts
Default

Quote:
Originally Posted by SPWorley View Post
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 is offline   Reply With Quote
Old 2009-08-28, 07:42   #3
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

433 Posts
Default

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.
Kevin is offline   Reply With Quote
Old 2009-08-28, 08:17   #4
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

23·19 Posts
Default

Quote:
Originally Posted by Kevin View Post
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.
Dougy is offline   Reply With Quote
Old 2009-08-28, 11:08   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by Kevin View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2009-08-28, 17:18   #6
SPWorley
 
Jul 2009

31 Posts
Default

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!
SPWorley is offline   Reply With Quote
Old 2009-08-28, 18:02   #7
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

6618 Posts
Default

Quote:
Originally Posted by SPWorley View Post
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.
Kevin is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Bi-curvious Identity jcrombie Miscellaneous Math 51 2013-09-09 18:51
Cpu Identity mismatch only_human Software 2 2012-05-11 13:43
I had my identity stolen by '24' ewmayer Lounge 12 2010-02-04 21:26
Useful Identity? grandpascorpion Math 2 2009-11-10 20:44
A missing identity 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.