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

 2011-04-07, 12:53 #1 kurtulmehtap   Sep 2009 448 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

10010110011012 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
Dumbassville

26·131 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 Dumbassville 26·131 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

Nov 2003

22·5·373 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

4,813 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.

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

Nov 2003

11101001001002 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

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

Nov 2003

22·5·373 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 23:05.

Sun May 9 23:05:00 UTC 2021 up 31 days, 17:45, 0 users, load averages: 3.00, 2.82, 2.67