mersenneforum.org  

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

Reply
 
Thread Tools
Old 2011-04-07, 12:53   #1
kurtulmehtap
 
Sep 2009

448 Posts
Default 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
kurtulmehtap is offline   Reply With Quote
Old 2011-04-07, 12:57   #2
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

10010110011012 Posts
Default

Quote:
Originally Posted by kurtulmehtap View Post
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
ET_ is offline   Reply With Quote
Old 2011-04-07, 13:01   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by kurtulmehtap View Post
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\pm1 and 6y\pm1 ( and yes I may be missing something).
science_man_88 is offline   Reply With Quote
Old 2011-04-07, 13:37   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

http://www.google.ca/search?sourceid...rsenne+numbers is what I did and the last one on my first page of results seems good.
science_man_88 is offline   Reply With Quote
Old 2011-04-07, 16:41   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by ET_ View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2011-04-07, 20:57   #6
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

4,813 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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...
ET_ is offline   Reply With Quote
Old 2011-04-18, 17:24   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by ET_ View Post
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?
R.D. Silverman is offline   Reply With Quote
Old 2011-04-18, 17:27   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by kurtulmehtap View Post
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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
(M48) NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED! dabaichi News 571 2020-10-26 11:02
The largest ever prime ECM factor, man Batalov GMP-ECM 14 2010-04-19 17:17
Largest 64 bit prime? amcfarlane Math 6 2004-12-26 23:15
largest factor ,i think. heryu Miscellaneous Math 10 2004-09-08 11:15
need Pentium 4s for 5th largest prime search (largest proth) 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.