mersenneforum.org  

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

Reply
 
Thread Tools
Old 2020-10-09, 07:02   #1
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

7×89 Posts
Default Why does a prime p divide a Fermat Number?

Hi all,
There is an interesting article in Mathematics Magazine (Vol 92, No 4, October 2020).
The title of the article is "Why does a prime p divide a Fermat Number?" They reference fermatsearch.org. They state that a Fermat prime divisor divides one and only one Fermat number.

Regards,
Matt
MattcAnderson is offline   Reply With Quote
Old 2020-10-09, 08:27   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·7·11·29 Posts
Default

Quote:
Originally Posted by MattcAnderson View Post
Why does a prime p divide a Fermat Number?
Because he can, and he wants to do so.
The "unicity" of factors is known, and trivial to prove.

Last fiddled with by LaurV on 2020-10-09 at 08:28
LaurV is offline   Reply With Quote
Old 2020-10-09, 08:52   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

58916 Posts
Default

Quote:
Originally Posted by MattcAnderson View Post
They state that a Fermat prime divisor divides one and only one Fermat number.
I've learnt in this nice way: F(n)=2+F(0)*F(1)*F(2)*...*F(n-1), so if we have a common divisor d of F(n) and F(m), where m<n then d|2, hence d=1 because all F(k) is odd.
R. Gerbicz is offline   Reply With Quote
Old 2020-10-09, 16:11   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·7·11·29 Posts
Default

Yep, that's what wikipedia used to say for a while
LaurV is offline   Reply With Quote
Old 2020-10-09, 20:12   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

13×109 Posts
Default

Quote:
Originally Posted by LaurV View Post
Yep, that's what wikipedia used to say for a while
Really not read, in general I know the shortest proofs. Another way:
If 2^(2^m)==-1 mod d then for n>m taking this to the 2^(n-m)-th power:
2^(2^n)==1 mod d from this F(n)==2 mod d and the rest is the same. This could be even shorter proof when you write down, but needs more knowledge.
R. Gerbicz is offline   Reply With Quote
Old 2020-10-09, 22:01   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23×5×229 Posts
Quote:
Originally Posted by LaurV View Post
Because he can, and he wants to do so.
Are you sure that this is not the answer for the 'Why did the chicken cross the road?"

Then again, this answer is quite universal, just like "42". I like it.
Batalov is offline   Reply With Quote
Old 2020-10-13, 15:31   #7
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·7·11·29 Posts
Default

That's not a "show off" for the fact I know the math. I may know it, I may not know it. I was barking more in that direction that people come and ask questions whose answers (and more details about subject) could be found by a simple search.

Last fiddled with by LaurV on 2020-10-13 at 15:31
LaurV is offline   Reply With Quote
Old 2020-10-13, 22:50   #8
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

7×89 Posts
Default

We know that the Fermat numbers are defined as
F(n) = 2^(2^n) + 1.

Also,
F(0) to F(4) are prime numbers.
F(5) to F(32) are composite numbers.
F(33) to F(35) are of unknown character.
F(36) is composite.

This data is available at -
http://www.prothsearch.com/fermat.html

I spent several years using trial division programs
trying to find the smallest prime factor of F(34).

So far we know that the smallest prime divisor of
F(34) is greater than 7*10^17.

Maybe someone else wants to work on this.
The program (mmff) can be downloaded from
fermatsearch.org

Regards,
Matt
MattcAnderson is offline   Reply With Quote
Old 2020-10-14, 01:05   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

916010 Posts
Default

Quote:
Originally Posted by MattcAnderson View Post
I spent several years using trial division programs
trying to find the smallest prime factor of F(34).
If you used the programs that most people use (didn't write your own?) - then you don't know which F(n) you will find a factor for.

The stats show that you mostly reserved ranges for N=36.
This means that you can just as well find a factor of F(33) or F(32), if you keep at it.
You are not guaranteed to find the factor of F(34)!
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Prime numbers 2kMp+1 that (don't) divide MMp ET_ Operazione Doppi Mersennes 26 2019-02-03 18:25
Number 59649589127497217 is a factor of Fermat number F7 literka Miscellaneous Math 73 2013-11-17 10:33
On Fermat's Last Number c10ck3r Miscellaneous Math 14 2012-11-29 20:36
Fermat number F6=18446744073709551617 is a composite number. Proof. literka Factoring 5 2012-01-30 12:28
Fermat number factors Citrix Math 35 2007-01-23 23:17

All times are UTC. The time now is 05:43.

Sat Nov 28 05:43:33 UTC 2020 up 79 days, 2:54, 3 users, load averages: 1.65, 1.32, 1.29

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