 mersenneforum.org > Math "On factors of Mersenne numbers" - Seiji Tomita
 Register FAQ Search Today's Posts Mark Forums Read 2009-12-13, 02:26   #1

"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts "On factors of Mersenne numbers" - Seiji Tomita

Seiji Tomita has posted, on NMBRTHRY, the following:

Quote:
 On factors of Mersenne numbers. Thursday, December 10, 2009 11:15 AM From: "Seiji Tomita" 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?   2009-12-14, 20:05 #2 ewmayer ∂2ω=0   Sep 2002 República de Califo 22·2,939 Posts 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).   2009-12-14, 23:24   #3
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101110100112 Posts Quote:
 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.   2009-12-15, 00:31 #4 ATH Einyen   Dec 2003 Denmark 27·33 Posts 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   2009-12-15, 11:20   #5
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2E6F16 Posts Quote:
 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   2009-12-15, 11:48   #6
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

3·5·509 Posts Quote:
 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.   2009-12-15, 17:45 #7 philmoore   "Phil" Sep 2002 Tracktown, U.S.A. 19·59 Posts 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!  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post pinhodecarlos NFS@Home 2 2015-07-04 11:18 Flatlander Linux 3 2011-02-21 02:32 James Heinrich Marin's Mersenne-aries 8 2004-05-17 11:09 Moloch Lounge 9 2004-03-28 05:56 antiroach Lone Mersenne Hunters 6 2003-07-16 23:35

All times are UTC. The time now is 03:04.

Thu Oct 5 03:04:38 UTC 2023 up 22 days, 46 mins, 0 users, load averages: 0.87, 0.80, 0.84

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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔 