mersenneforum.org I noticed that only prime mersennes are quad_residue's of 9, has this been noticed before?
 Register FAQ Search Today's Posts Mark Forums Read

 2021-04-18, 02:51 #1 LarsNet   Mar 2021 23×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**p-1 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 2021-04-18 at 03:05
 2021-04-18, 04:08 #2 srow7   Jul 2014 3×17 Posts what is quad_residue ? (the math and the subroutine)
 2021-04-18, 04:23 #3 LarsNet   Mar 2021 23×3 Posts srow7, Note this only works for mersenne numbers and can be increased in speed by 10-16x 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=(n-1)//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 Here is version that uses gmpy2, but isn't the quad residue version, it just produces the same result, an answer of 9 always for mersenne primes as opposed to non mersenne primes: Code: import gmpy2 def makersmark(n): z = 9 mask = gmpy2.mpz((1<>= 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(n-1): z = mer_rem(z * z, n) print(z) return z == 9 makersmark is as fast as lucas lehmer, and much faster than quad_residue, i just noticed that they are corollary. Last fiddled with by LarsNet on 2021-04-18 at 04:36
 2021-04-18, 04:43 #4 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2·3·337 Posts A PARI-GP version. I find it quite interesting. Well done, LarsNet! Code:  \\DXT-100-A forprime (p=2,19^4,{ primeFlag=1; iferr(qr = qfbprimeform(9, (2^p-1)), 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 It works for M2 as well. 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 2021-04-18 at 05:42
 2021-04-18, 05:47 #5 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2·3·337 Posts ETA IV, Please ignore ETA III, M11 passes with 121, but not with 9.
 2021-04-18, 06:29 #6 LaurV Romulan Interpreter     Jun 2011 Thailand 944510 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^p-1 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.
 2021-04-18, 06:29 #7 axn     Jun 2003 2·3·827 Posts Your check is 9^((Mp-1)/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.
2021-04-18, 06:41   #8
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2×3×337 Posts

Quote:
 Originally Posted by axn Since 9 is a perfect square, it is a quadratic residue to every number.
Do you mean every Prime-Number?
Code:
qfbprimeform(9, 19)
%3 = Qfb(19, 3, 0, 0.E-38)
(02:38) gp >
(02:38) gp >
(02:38) gp > qfbprimeform(9, 15)
***   at top-level: qfbprimeform(9,15)
***                 ^------------------
*** qfbprimeform: not an n-th power residue in primeform: Mod(9, 15).
Quote:
 Returns an error if x is not a quadratic residue mod p
https://pari.math.u-bordeaux.fr/dochtml/html-stable/

ETA: 121 is a perfect square and is a quadratic-residue for M11, while 9 is not.

ETA II: 9 as quadratic-residue-test passes all the Mersenne-primes from M2 to M23209 and none of the Mersenne-composites (not a single "pseudoprime").

ETA III As LarsNet has pointed out, the test is valid only for Mersenne-Numbers:

Code:
qfbprimeform(9, 91)
%7 = Qfb(91, 81, 18, 0.E-38)

Last fiddled with by a1call on 2021-04-18 at 07:05

2021-04-18, 07:14   #9
axn

Jun 2003

496210 Posts

Quote:
 Originally Posted by a1call Do you mean every Prime-Number?
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

Quote:
 Originally Posted by a1call ETA III As LarsNet has pointed out, the test is valid only for Mersenne-Numbers:
Test is valid for all numbers relatively prime to 9. It is merely a base-9 Euler pseudoprimality test. He stumbled upon it while checking out QR; but that's what it is.

Last fiddled with by axn on 2021-04-18 at 07:15

2021-04-18, 07:21   #10
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

202210 Posts

Quote:
 Originally Posted by axn No. Composite numbers as well. However, it must be relatively prime.
25 is coprime to 9 but it does not pass the test:

Code:
qfbprimeform(9, 25)
***   at top-level: 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 top-level: qfbprimeform(9,35)
***                 ^------------------
*** qfbprimeform: not an n-th power residue in primeform: Mod(9, 35).

Last fiddled with by a1call on 2021-04-18 at 07:24

2021-04-18, 07:39   #11
axn

Jun 2003

2·3·827 Posts

Quote:
 Originally Posted by a1call 25 is coprime to 9 but it does not pass the test:
I don't know what "the test" is but:
Code:
? kronecker(9, 25)
%1 = 1
Do you even know what qfbprimeform is supposed to do?
Code:
? ?qfbprimeform
qfbprimeform(x,p): returns the prime form of discriminant x, whose first coefficient is p.
OP's algorithm has nothing to do with qfbprimeform, so stop bringing it up.

Last fiddled with by axn on 2021-04-18 at 07:40

 Similar Threads Thread Thread Starter Forum Replies Last Post paulunderwood Miscellaneous Math 3 2019-01-24 03:14 carpetpool carpetpool 7 2017-01-05 04:36 Mini-Geek GPU to 72 3 2011-12-20 16:12 mdettweiler Conjectures 'R Us 7 2008-03-06 17:33 moo Hardware 4 2006-04-14 03:36

All times are UTC. The time now is 15:56.

Thu May 13 15:56:40 UTC 2021 up 35 days, 10:37, 2 users, load averages: 2.79, 2.45, 2.27