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 22×32 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

113538 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

2×5×839 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 100000110001102 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

23×3×311 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

12EB16 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

"Bob Silverman"
Nov 2003
North of Boston

23·3·311 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

"Bob Silverman"
Nov 2003
North of Boston

23·3·311 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 15:12.

Sat Aug 13 15:12:45 UTC 2022 up 37 days, 10 hrs, 2 users, load averages: 0.58, 0.96, 1.01