20040307, 13:48  #1 
Mar 2004
29 Posts 
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^x1 for x>2? In other words: If 2^x1 is prime is then Ord 3 (mod 2^x1) always 2^x2 = 2(2^(x1)1)? Sorry, I already posted it, but by accident in the programming forum and I think this is a better place for this question :o) I guess if my suspicion is right I guess this has already been proofed. Thank you in advance Juergen 
20040308, 14:22  #2  
Nov 2003
16100_{8} Posts 
Quote:


20040308, 19:12  #3 
"Phil"
Sep 2002
Tracktown, U.S.A.
2^{2}×3^{2}×31 Posts 
I don't think juergen has them confused, as he stated in the programming thread that he had tested all exponents up to 127. However, I just checked that Ord 3 (2^13  1) = 910, not 8190 according to his conjecture. So he may have overlooked something in doing his computations.
Last fiddled with by philmoore on 20040308 at 19:13 
20050307, 04:07  #4 
Mar 2005
2^{3} Posts 
yes
3^(2^(p1)) = 3 (mod 2^p1) if 2^p1 is prime.
This translates to 3^(2^p2) = 1 (mod 2^p1); square and multiply by 3^2. This congruence is necessary for 2^p1 to be prime, but I don't know yet whether it is sufficient. Last fiddled with by abiessu on 20050307 at 04:10 
20050307, 21:01  #5  
∂^{2}ω=0
Sep 2002
República de California
9,791 Posts 
Quote:
3^(2^(p1)  1) = 1 (mod 2^p1) The exponent of 3 on the lefthand side is just (2^p1)/2, i.e. what one would expect in an EPT of 2^p1. More generally, Euler's criterion says for q an odd prime and a positive integer A which is not a multiple of q, A^((q1)/2) == (Aq) mod q where (Aq) is the Legendre symbol, i.e. the righthandside = +1 or 1, depending on whether A is a quadratic residue mod q or not, respectively. In the problem at hand we need to see whether or not 3 is a QR modulo 2^p1. It is wellknown that for 3 to be a QR modulo q, the modulus in question must have the form q = 12*k + 1 for some integer k, i.e. q == +1 modulo 12. Now it's simple to show that moduli q = 2^p1 cannot have this form for *any* positive exponent p > 1, whether it be odd or even, prime or nonprime. For p=2, 2^p = 4, i.e. 2^p1 == 3 modulo 12. Going back to 2^p, multiplying this by 4 gives 16, which is again == 4 modulo 12, and thus it's clear that for any even power, 2^p1 == 3 modulo 12. We proceed analogously for odd p's starting with p=3, and quickly establish that for any odd exponent p, 2^p1 == 7 mod 12, so 3 is not a QR modulo 2^p1, which is why an EPT of a Mersenne prime always yields 1. (And why your version of the test always yields 3). Except for numbers of special form (e.g. Fermats), the EPT is necessary but not sufficient to establish primality. Thus you would expect the result to apply for all known Mersenne primes, but cannot rule out the possibility that there are some primes p for which the congruence holds but for which 2^p1 is nevertheless composite. 

20050308, 03:12  #6 
Mar 2005
1000_{2} Posts 
necessary but not sufficient?
Hmm... please explain why it is not sufficient. I understand that (given a single a) a^p = a mod p is necessary but not sufficient...
There's two special considerations I'm giving this congruence: 1) The power series used to establish the congruence could be p1 steps (square, mod by M_p), or it could be (p1)/2 steps (square twice, mod by M_p). Any chance that the latter is 'twice as fast', computationally (or even theoretically)? 2) 3 is the only prime known (so far) to have the property that it is a quadratic nonresidue mod M_p for any prime M_p > 3. Even better, if 3 is a quadratic residue mod M_p, then M_p is not prime. 
20050308, 13:26  #7  
Nov 2003
2^{6}×113 Posts 
Quote:
It is not sufficient because there exists composite values of 2^p1 that satisfy the congruence. Why is this difficult? There is not only ZERO chance that it would be faster than the LL test, it would actually be slower. (Hint: look at the binary representation of 2^n1; each iteration would be more than a simple squaring) It is probably true that 3 is the only known QNR for all Mersenne primes. 

20050308, 18:00  #8  
May 2004
2^{4}×5 Posts 
Quote:
Dave 

20050308, 20:41  #9  
∂^{2}ω=0
Sep 2002
República de California
9,791 Posts 
I'll only comment on the numberofiterations point  abiessu, I urge you to invest in a decent introductory text on number theory, preferably one that also discusses computational aspects (either Riesel or Crandall/Pomerance would be a good choice, IMO) if you want to understand things like the properties of the common compositeness tests, false primes, etc.
Quote:
However, even assuming you can do each iteration as fast as one of the LL test, this saves you nothing in terms of number of modular squarings needing to be done. To test q = 2^p  1 for primality, the LL test needs (p2) squarings modulo q; we've just established that the Euler test needs the same number. Note that the factor of two in the modular powering you seem so fascinated with amounts to just a *single* iteration, i.e. to evaluate 3^((2^p2)/2) mod q (Euler compositeness test) needs (p2) modsquares, whereas 3^(2^p2) mod q (Fermat compositeness test) needs (p1) modsquares, but of course that difference is completely negligible in terms of runtime for p large. In other words, cutting the exponent of the modular powering in half saves just *one* iteration, not half of them, as you hoped. 

20050309, 04:06  #10  
Mar 2005
2^{3} Posts 
"there exist..."
My apologies for making wild conjectures... I'll look into a number theory book or two.
Quote:
3^(2^(p1)) = 3 (mod 2^p  1) where p is prime and 2^p  1 is not prime. (Or written as an Euler pseudoprime test as desired.) Again, I haven't seen such a p yet, and others have mentioned that none exist up to p = 132049 (the limit checked at that time). Otherwise, I'm done. My apologies for not studying more carefully beforehand. 

20050309, 04:35  #11  
Mar 2005
2^{3} Posts 
(edit limit exceeded...)
Sorry... one thing I missed...
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primitive Root of Mersenne Numbers  PawnProver44  Miscellaneous Math  7  20160418 23:49 
Primitive roots for a set of primes  mart_r  Math  0  20130720 12:23 
Finding the square root of a large mersenne number  Fusion_power  Math  29  20101014 17:05 
Primitive root question  __HRB__  Math  0  20090710 00:41 
Is 3 always a primitive root for mersenne primes?  juergen  Programming  9  20050308 03:51 