"On factors of Mersenne numbers" - Seiji Tomita

[cheesehead]

(Am I really the first to post about this item from Thursday's NMBRTHRY?)

Seiji Tomita has posted, on NMBRTHRY, the following:

On factors of Mersenne numbers.

Thursday, December 10, 2009 11:15 AM
From:
"Seiji Tomita" <fermat@M15.ALPHA-NET.NE.JP>
To:
undisclosed-recipients
Dear number theorists,

I show two properties about Mersenne number.
Euler showed the following theorem.

Theorem(Euler)

Let p = 3 (mod 4) be prime and q = 2p+1 is also prime.
Then q divides Mersenne number M(p) = 2^p-1.

In the same way as Euler,I show two properties.

Property 1.
Let p is prime and q = 6p+1 is also prime.
If q = 27x^2+y^2 and q = 7 mod 8,q divides Mersenne number M(p)=2^p-1.

Since q = 27x^2+y^2 and q = 7 mod 8,then
z^6 = 2 mod q has a integer solution z.(By cubic and quadratic
reciprocity law)

So,2^p = 2^{(q-1)/6} = z^(q-1) = 1 mod q.
Therefore,q = 6p+1 divides Mersenne number M(p) = 2^p-1.

Example: p < 1000
p q
37 223 = 27* 1^2 + 14^2 , 2^37 - 1=0 mod 223
73 439 = 27* 3^2 + 14^2 , 2^73 - 1=0 mod 439
233 1399 = 27* 3^2 + 34^2 , 2^233 - 1=0 mod 1399
397 2383 = 27* 9^2 + 14^2 , 2^397 - 1=0 mod 2383
461 2767 = 27* 7^2 + 38^2 , 2^461 - 1=0 mod 2767
557 3343 = 27* 9^2 + 34^2 , 2^557 - 1=0 mod 3343
577 3463 = 27* 11^2 + 14^2 , 2^577 - 1=0 mod 3463
601 3607 = 27* 3^2 + 58^2 , 2^601 - 1=0 mod 3607
761 4567 = 27* 13^2 + 2^2 , 2^761 - 1=0 mod 4567


Property 2.
Let p is prime and q = 8p+1 is also prime.
If q = 64x^2+y^2 for some odd x,q divides Mersenne number M(p) = 2^p-1.

Since q = 64x^2+y^2 for some odd x,then
z^8 = 2 mod q has a integer solution z.(By octic reciprocity law)

So,2^p = 2^{(q-1)/8} = z^(q-1) = 1 mod q.
Therefore,q = 8p+1 divides Mersenne number M(p) = 2^p-1.

Example: p < 1000
p q
11 89 = 64* 1^2 + 5^2 , 2^11 - 1 = 0 mod 89
29 233 = 64* 1^2 + 13^2 , 2^29 - 1 = 0 mod 233
179 1433 = 64* 1^2 + 37^2 , 2^179 - 1 = 0 mod 1433
239 1913 = 64* 1^2 + 43^2 , 2^239 - 1 = 0 mod 1913
431 3449 = 64* 5^2 + 43^2 , 2^431 - 1 = 0 mod 3449
761 6089 = 64* 5^2 + 67^2 , 2^761 - 1 = 0 mod 6089
941 7529 = 64* 5^2 + 77^2 , 2^941 - 1 = 0 mod 7529
857 6857 = 64* 7^2 + 61^2 , 2^857 - 1 = 0 mod 6857

Can we get a similar simple result on the higher power residue?

Seiji Tomita

Is this new?

[ewmayer]

I saw the original post on the NT mailing list ... looks to be new, the real question is, is it practically useful? As far at TF goes it seems not, since if e.g. q = 6p+1 or q = 8p+1 is prime it's going to pass the small-factor sieve and get tested for factor-hood, and pre-testing to see if the q's are genuine primes is more expensive than seeing if they divide M(p).

[R.D. Silverman]

Originally Posted by ewmayer

I saw the original post on the NT mailing list ... looks to be new, the real question is, is it practically useful? As far at TF goes it seems not, since if e.g. q = 6p+1 or q = 8p+1 is prime it's going to pass the small-factor sieve and get tested for factor-hood, and pre-testing to see if the q's are genuine primes is more expensive than seeing if they divide M(p).

The idea itself is quite old. The evaluation of the Artin symbol (for
reciprocity higher than quadratic) and the ideas behind cubic, quartic
reciprocity etc. are well covered in Serre's book: A course on Arithmetic
(caveat emptor if you read this book; it is dense). The ideas
behind the exact quadratic form to construct for 2kp+1 are covered in
Cox's book on quadratic forms and prime representations.

The exact quadratic forms given here seem new, but the math behind them
is known.

[ATH]

From empirical testing it seems to work the other way as well:

If q=6p+1 divides M_p=2^p-1 then q=7 (mod 8) and q=27x^2+y^2 for some positive x,y.
Of the 50,847,534 prime exponents p<10⁹, this works on all the 1,046,030 exponents where q=6p+1 is a factor (not counting 2⁵-1 as it's own factor q=6*5+1, but it works there too).

If q=8p+1 divides M_p=2^p-1 then q = 64x^2+y^2 for some positive x,y.
This works on all 773,708 prime exponents p<10⁹ where q=8p+1 is a factor.

[xilman]

Originally Posted by R.D. Silverman

(caveat emptor if you read this book; it is dense)

Caveat lector surely, unless you are suggesting that we go and out and buy a copy.



Paul

[R.D. Silverman]

Originally Posted by xilman

Caveat lector surely, unless you are suggesting that we go and out and buy a copy.



Paul

I bought a copy. It is a very useful book. As a reference. Don't
try to learn from it.

[philmoore]

Serre's book doesn't go beyond quadratic reciprocity. I think it is an excellent book to learn from, but is dense, as you say. A good introduction to quadratic reciprocity, p-adic numbers, quadratic forms, Dirichlet's theorem, and a brief but difficult introduction to modular forms. I reread it a few years ago and was amazed to read the annotations I had written in the book as a student, years earlier, because most of the material did not seem familiar at all to me! Just shows how much you can forget over the years!