mersenneforum.org > Math studies on largest prime factor ?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2011-04-07, 12:53 #1 kurtulmehtap   Sep 2009 1001002 Posts studies on largest prime factor ? Dear All, I am looking for papers on the largest prime factor of a mersenne number. As far as I know the largest prime factor has to be less than the square root of the mersenne number. Are there any tighter bounds? Thanx in advance
2011-04-07, 12:57   #2
ET_
Banned

"Luigi"
Aug 2002
Team Italia

113718 Posts

Quote:
 Originally Posted by kurtulmehtap Dear All, I am looking for papers on the largest prime factor of a mersenne number. As far as I know the largest prime factor has to be less than the square root of the mersenne number. Are there any tighter bounds? Thanx in advance
IIRC, the bound applies to the largest penultimate prime factor of a Mersenne number.

2^11-1 = 2047 = 23 x 89 and 89 > sqrt(2^11 - 1)

Otherwise, the upper limit of trial-factoring for a number is sqrt(n).

Mersenne factors have the property of being of the form 2kp+1 (k=1,2,3... and p= the exponent of the number), so the upper limit may as well be lowered to 2kp+1 < sqrt(p) (where we have 2kp+1 < sqrt(p) < 2(k+1)p+1)

There are other heuristics, like the factor should be 1 or 7 mod 8, or [16 different values] mod 120, or [more different values] mod 420 (or 4620). Those values for the factor automatically rule out multiples of 3, 5, 7, 11.

Luigi

Last fiddled with by ET_ on 2011-04-07 at 13:06 Reason: Edited after Science_Man_88 post

2011-04-07, 13:01   #3
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

2·3·23·61 Posts

Quote:
 Originally Posted by kurtulmehtap Dear All, I am looking for papers on the largest prime factor of a mersenne number. As far as I know the largest prime factor has to be less than the square root of the mersenne number. Are there any tighter bounds? Thanx in advance
not completely accurate the largest can be more but to not be prime it must have one below the sqrt. all factors of prime exponents mersennes must be of the form 2kp+1 and also being 8x$\pm$1 and 6y$\pm$1 ( and yes I may be missing something).

 2011-04-07, 13:37 #4 science_man_88     "Forget I exist" Jul 2009 Dartmouth NS 20E216 Posts http://www.google.ca/search?sourceid...rsenne+numbers is what I did and the last one on my first page of results seems good.
2011-04-07, 16:41   #5
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101010101002 Posts

Quote:
 Originally Posted by ET_ IIRC, the bound applies to the largest penultimate prime factor of a Mersenne number.
There is nothing special about Mersenne numbers in this regard.
Why do people seem to think that they are special? NO
number (trivially) can have two prime factors greater than its square root.

Quote:
 There are other heuristics, like the factor should be 1 or 7 mod 8, or [16 different values] mod 120, or [more different values] mod 420 (or 4620). Those values for the factor automatically rule out multiples of 3, 5, 7, 11. Luigi
These restrictions are NOT 'heuristics'. They are THEOREMS.

2011-04-07, 20:57   #6
ET_
Banned

"Luigi"
Aug 2002
Team Italia

485710 Posts

Quote:
 Originally Posted by R.D. Silverman There is nothing special about Mersenne numbers in this regard. Why do people seem to think that they are special? NO number (trivially) can have two prime factors greater than its square root. These restrictions are NOT 'heuristics'. They are THEOREMS.
Sorry for the confusion...

In the first answer I specified Mersenne numbers because that was the question. You are right when you say that the same apply to all numbers.

And about my use of the term heuristics... I used that term when I first approached the problem, many years ago. Now I should have learnt that "Theorem" is the right word: thank you for your making it even clearer to everybody.

Finally, I am glad that your answer dealt about terms use, and not about trivial math errors in my answer.

Luigi

Last fiddled with by ET_ on 2011-04-07 at 20:59 Reason: My keyboard often hides vowels...

2011-04-18, 17:24   #7
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts

Quote:
 Originally Posted by ET_ IIRC, the bound applies to the largest penultimate prime factor of a Mersenne number. 2^11-1 = 2047 = 23 x 89 and 89 > sqrt(2^11 - 1) Otherwise, the upper limit of trial-factoring for a number is sqrt(n). Mersenne factors have the property of being of the form 2kp+1 (k=1,2,3... and p= the exponent of the number), so the upper limit may as well be lowered to 2kp+1 < sqrt(p) (where we have 2kp+1 < sqrt(p) < 2(k+1)p+1)
The inequality posted just above is total nonsense. May I suggest that
you proofread your posts before submitting them?

2011-04-18, 17:27   #8
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

750810 Posts

Quote:
 Originally Posted by kurtulmehtap Dear All, I am looking for papers on the largest prime factor of a mersenne number. As far as I know the largest prime factor has to be less than the square root of the mersenne number. Are there any tighter bounds? Thanx in advance
May I suggest that in the future you should CHECK your
claims before posting? 15 seconds of checking factorizations of
2^n-1 (from published tables) would have revealed that your claim
about the largest prime factor being less than the square root was
nonsense. Finding counter-examples is trivial.

 Similar Threads Thread Thread Starter Forum Replies Last Post dabaichi News 571 2020-10-26 11:02 Batalov GMP-ECM 14 2010-04-19 17:17 amcfarlane Math 6 2004-12-26 23:15 heryu Miscellaneous Math 10 2004-09-08 11:15 wfgarnett3 Lounge 7 2002-11-25 06:34

All times are UTC. The time now is 20:29.

Sun Feb 5 20:29:22 UTC 2023 up 171 days, 17:57, 1 user, load averages: 0.74, 1.04, 1.07

Copyright ©2000 - 2023, 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.

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