mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2004-03-06, 21:14   #1
juergen
 
Mar 2004

29 Posts
Default Is 3 always a primitive root for mersenne primes?

Hello,

the subject sais it all.

Is 3 always a primitive root for primes of the form 2^x-1 for x>2?
In other words:

If 2^x-1 is prime is then

Ord 3 (mod 2^x-1) always 2^x-2 = 2(2^(x-1)-1)?

I checked this up to 127, okay thats not a lot, but I guess that this is really right and I wonder if there is already a proof for that.

kind regards J├╝rgen
juergen is offline   Reply With Quote
Old 2005-03-07, 04:15   #2
abiessu
 
Mar 2005

810 Posts
Default yes

Actually, it's that 'ord 3 (2^p-1) divides 2^p-2'. But there's an even better congruence:

3^(2^(p-1)) = -3 (mod 2^p-1).
abiessu is offline   Reply With Quote
Old 2005-03-07, 06:28   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25×7×11 Posts
Default

Quote:
Originally Posted by abiessu
Actually, it's that 'ord 3 (2^p-1) divides 2^p-2'. But there's an even better congruence:

3^(2^(p-1)) = -3 (mod 2^p-1).
The first follows from Lagrange's theorem. The second follows from the fact that 3 is a quadratic non-residue (mod 2^p-1) for Mersenne primes with odd p. Neither answers the original question.

Alex
akruppa is offline   Reply With Quote
Old 2005-03-07, 10:04   #4
abiessu
 
Mar 2005

810 Posts
Default ehh...

Sorry, I meant it like this:

'yes, 2^p-2 is always an order of 3 mod 2^p-1 given the conditions you've described, and it just so happens that...'

I got a little carried away, new to the forum and all...

But... umm... doesn't that answer the original?
abiessu is offline   Reply With Quote
Old 2005-03-07, 10:11   #5
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25·7·11 Posts
Default

The order of an element a is the smallest positive integer n so that a^n == 1. You showed that 2^p-2 is a multiple of the order of 3 (which is what Lagrange's theorem states, the order of an element divides the order of the group), but not that 2^p-2 is equal to the order of 3.

Alex
akruppa is offline   Reply With Quote
Old 2005-03-07, 14:56   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

723210 Posts
Default

Quote:
Originally Posted by akruppa
The order of an element a is the smallest positive integer n so that a^n == 1. You showed that 2^p-2 is a multiple of the order of 3 (which is what Lagrange's theorem states, the order of an element divides the order of the group), but not that 2^p-2 is equal to the order of 3.

Alex
Disproof by counter-example.

A short search reveals that 3^910 = 1 mod (2^13-1).

Thus, 3 is not primitive.

What compels people to make such speculations without even a minimal
attempt at some numerical verification?
R.D. Silverman is offline   Reply With Quote
Old 2005-03-07, 19:46   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11100010000002 Posts
Thumbs down

Quote:
Originally Posted by R.D. Silverman
Disproof by counter-example.

A short search reveals that 3^910 = 1 mod (2^13-1).

Thus, 3 is not primitive.

What compels people to make such speculations without even a minimal
attempt at some numerical verification?
Another example: Let P = 2^61-1, then 3^( (P-1)/3) = 1 mod P.

Enuf said?????
R.D. Silverman is offline   Reply With Quote
Old 2005-03-07, 22:23   #8
Primeinator
 
Primeinator's Avatar
 
"Kyle"
Feb 2005
Somewhere near M50..sshh!

2·3·149 Posts
Default

Please pardon me, I'm only a sophomore in an american high school. Could someone please explain to me what a primitive root is? (I know what square roots and cubic roots and 4th roots, etc etc are).
Primeinator is offline   Reply With Quote
Old 2005-03-07, 23:13   #9
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

22×32×31 Posts
Default

Suppose p is prime. Then the congruence classes 1, 2, 3, ..., p-1 form a group under multiplication. (Example: p = 11, then 2*7 = 14 = 3 mod 11.) A primitive root is a congruence class that generates all the other congruence classes when you take its powers. So the consecutive powers of 2 mod 11 are: 2, 4, 8, 5, 10, 9, 7, 3, 6, and 1, so 2 is a primitive root mod 11. On the other hand, the powers of 3 mod 11 are: 3, 9, 3, 4, 1, 3, 9, 3, 4, 1, etc., so 3 is not a primitive root.
philmoore is offline   Reply With Quote
Old 2005-03-08, 03:51   #10
abiessu
 
Mar 2005

816 Posts
Default mis-use of terms?

Quote:
Originally Posted by R.D. Silverman
Disproof by counter-example.

A short search reveals that 3^910 = 1 mod (2^13-1).

Thus, 3 is not primitive.

What compels people to make such speculations without even a minimal
attempt at some numerical verification?
(No, I'm not saying that you mis-used terms.)

I think I missed the point the original poster was aiming at. My apologies.
abiessu is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primitive Root of Mersenne Numbers PawnProver44 Miscellaneous Math 7 2016-04-18 23:49
Primitive roots for a set of primes mart_r Math 0 2013-07-20 12:23
Finding the square root of a large mersenne number Fusion_power Math 29 2010-10-14 17:05
Primitive root question __HRB__ Math 0 2009-07-10 00:41
Is 3 always a primitive root for mersenne primes? juergen Math 12 2005-03-09 08:18

All times are UTC. The time now is 18:55.

Tue Oct 27 18:55:00 UTC 2020 up 47 days, 16:05, 1 user, load averages: 2.32, 2.27, 2.17

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.