mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-12-13, 02:26   #1
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

718810 Posts
Default "On factors of Mersenne numbers" - Seiji Tomita

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

Seiji Tomita has posted, on NMBRTHRY, the following:

Quote:
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?
cheesehead is offline   Reply With Quote
Old 2009-12-14, 20:05   #2
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

22×33×7×13 Posts
Default

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).
ewmayer is offline   Reply With Quote
Old 2009-12-14, 23:24   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1C4016 Posts
Default

Quote:
Originally Posted by ewmayer View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2009-12-15, 00:31   #4
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

BA316 Posts
Default

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

If q=6p+1 divides Mp=2p-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<109, this works on all the 1,046,030 exponents where q=6p+1 is a factor (not counting 25-1 as it's own factor q=6*5+1, but it works there too).

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

Last fiddled with by ATH on 2009-12-15 at 00:32
ATH is offline   Reply With Quote
Old 2009-12-15, 11:20   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2·3·1,699 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
(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
xilman is offline   Reply With Quote
Old 2009-12-15, 11:48   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2009-12-15, 17:45   #7
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

22·32·31 Posts
Default

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!
philmoore is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
NFS@Home "Status of numbers" page to update pinhodecarlos NFS@Home 2 2015-07-04 11:18
"factors.txt.u1conflict..." files Flatlander Linux 3 2011-02-21 02:32
P-1 factoring != "Mersenne numbers to factor"? James Heinrich Marin's Mersenne-aries 8 2004-05-17 11:09
What is a quick way to "rule out" 10mil digit numbers? Moloch Lounge 9 2004-03-28 05:56
trial factoring of "small" mersenne numbers antiroach Lone Mersenne Hunters 6 2003-07-16 23:35

All times are UTC. The time now is 05:07.

Thu Nov 26 05:07:24 UTC 2020 up 77 days, 2:18, 3 users, load averages: 2.00, 1.73, 1.52

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.