

Thread Tools 
20210418, 02:51  #1 
Mar 2021
2^{3}·3 Posts 
I noticed that only prime mersennes are quad_residue's of 9, has this been noticed before?
I noticed that only prime mersennes are quad_residue's of 9, (as opposed to non mersenne primes) has this been noticed before?
I didn't find it on a google search so wanted to ask here. Code:
In [396]: for x in (2**p1 for p in range(3,608)): ...: xx = quad_residue(9, x) ...: if xx == 1: print(x.bit_length()) ...: 3 5 7 13 17 19 31 61 89 107 127 521 607 Last fiddled with by LarsNet on 20210418 at 03:05 
20210418, 04:08  #2 
Jul 2014
110011_{2} Posts 
what is quad_residue ?
(the math and the subroutine) 
20210418, 04:23  #3 
Mar 2021
2^{3}×3 Posts 
srow7, Note this only works for mersenne numbers and can be increased in speed by 1016x by using gmpy2. The code is in python as i haven't written a c version yet ( it is the math from https://en.wikipedia.org/wiki/Quadratic_residue ):
Code:
def quad_residue_mersenne(a,n): mask = n def mer_rem(x, bits): # Below is same as: return x % mask while True: r = 0 while x != 0: r += x & mask x >>= bits if r == mask: r = 0 if r < mask: return r x = r #checks if a is quad residue of n l=1 q=(n1)//2 x = q**l if x==0: return 1 a =a%n z=1 while x!= 0: if x%2==0: a=mer_rem((a **2), n.bit_length()) x//= 2 else: x=1 z=mer_rem((z*a), n.bit_length()) return z Code:
import gmpy2 def makersmark(n): z = 9 mask = gmpy2.mpz((1<<n)1) def mer_rem(x, bits): # Below is same as: return x % mask while True: r = gmpy2.mpz(0) while x != 0: r += x & mask x >>= bits if r == mask: r = gmpy2.mpz(0) if r < mask: return r x = r z = gmpy2.mpz(z) n = gmpy2.mpz(n) for x in range(n1): z = mer_rem(z * z, n) print(z) return z == 9 Last fiddled with by LarsNet on 20210418 at 04:36 
20210418, 04:43  #4 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2×1,009 Posts 
A PARIGP version.
I find it quite interesting. Well done, LarsNet! Code:
\\DXT100A forprime (p=2,19^4,{ primeFlag=1; iferr(qr = qfbprimeform(9, (2^p1)), E,primeFlag=0;next();); print ("M",p); }) Code:
M2 M3 M5 M7 M13 M17 M19 M31 M61 M89 M107 M127 M521 M607 M1279 M2203 M2281 M3217 M4253 M4423 M9689 M9941 M11213 M19937 M21701 M23209 ETA II You don't happen to be a Baháʼí now, do you? ETA III It seems to work perfectly with other values than 9 such as 49, 81. 121. Last fiddled with by a1call on 20210418 at 05:42 
20210418, 05:47  #5 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2018_{10} Posts 
ETA IV, Please ignore ETA III, M11 passes with 121, but not with 9.

20210418, 06:29  #6 
Romulan Interpreter
Jun 2011
Thailand
5×1,889 Posts 
That's a red herring, kind of. For any prime m, there are only two solutions of the x^2=1 (mod m), which are 1 and 1, regardless of the fact that m is mersenne or not. If m is not prime, there are more solutions, and the determinant does not exist. If you make m=2^p1 for some prime p, yeah, the determinant still exists only when m is prime.
For example for p=11, you have four solutions, +/1 and +/622, when you square them you get 1 (mod 2047). It is all about the roots of 1. 
20210418, 06:29  #7 
Jun 2003
1362_{16} Posts 
Your check is 9^((Mp1)/2) == 1 (mod Mp) or alternately, 9^((Mp+1)/2)==9 (mod Mp).
This is nothing but a Euler pseudoprimality test Since 9 is a perfect square, it is a quadratic residue to every number. 
20210418, 06:41  #8  
"Rashid Naimi"
Oct 2015
Remote to Here/There
3742_{8} Posts 
Quote:
Code:
qfbprimeform(9, 19) %3 = Qfb(19, 3, 0, 0.E38) (02:38) gp > (02:38) gp > (02:38) gp > qfbprimeform(9, 15) *** at toplevel: qfbprimeform(9,15) *** ^ *** qfbprimeform: not an nth power residue in primeform: Mod(9, 15). Quote:
ETA: 121 is a perfect square and is a quadraticresidue for M11, while 9 is not. ETA II: 9 as quadraticresiduetest passes all the Mersenneprimes from M2 to M23209 and none of the Mersennecomposites (not a single "pseudoprime"). ETA III As LarsNet has pointed out, the test is valid only for MersenneNumbers: Code:
qfbprimeform(9, 91) %7 = Qfb(91, 81, 18, 0.E38) Last fiddled with by a1call on 20210418 at 07:05 

20210418, 07:14  #9 
Jun 2003
2·3·827 Posts 
No. Composite numbers as well. However, it must be relatively prime.
Code:
? kronecker(9,14) %1 = 1 ? kronecker(9,15) %2 = 0 ? kronecker(9,16) %3 = 1 ? kronecker(9,17) %4 = 1 ? kronecker(9,18) %5 = 0 Test is valid for all numbers relatively prime to 9. It is merely a base9 Euler pseudoprimality test. He stumbled upon it while checking out QR; but that's what it is. Last fiddled with by axn on 20210418 at 07:15 
20210418, 07:21  #10  
"Rashid Naimi"
Oct 2015
Remote to Here/There
2·1,009 Posts 
Quote:
Code:
qfbprimeform(9, 25) *** at toplevel: qfbprimeform(9,25) *** ^ *** qfbprimeform: not a prime number in Fl_sqrt [modulus]: 25. ETA: 35 is coprime to 9 but it does not pass the test: Code:
qfbprimeform(9, 35) *** at toplevel: qfbprimeform(9,35) *** ^ *** qfbprimeform: not an nth power residue in primeform: Mod(9, 35). Last fiddled with by a1call on 20210418 at 07:24 

20210418, 07:39  #11 
Jun 2003
2·3·827 Posts 
I don't know what "the test" is but:
Code:
? kronecker(9, 25) %1 = 1 Code:
? ?qfbprimeform qfbprimeform(x,p): returns the prime form of discriminant x, whose first coefficient is p. Last fiddled with by axn on 20210418 at 07:40 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Possible obfuscation for Mersennes  paulunderwood  Miscellaneous Math  3  20190124 03:14 
Composite integers n satisfying prime exponents of Mersennes  carpetpool  carpetpool  7  20170105 04:36 
DC completion not noticed  MiniGeek  GPU to 72  3  20111220 16:12 
Looks like PrimeGrid's noticed us....  mdettweiler  Conjectures 'R Us  7  20080306 17:33 
Noticed something on wiki  moo  Hardware  4  20060414 03:36 