mersenneforum.org  

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

Reply
 
Thread Tools
Old 2004-07-23, 08:15   #1
devarajkandadai
 
devarajkandadai's Avatar
 
May 2004

22·79 Posts
Default Fermat Numbers

Non-factors of Fermat Numbers:

1) No prime number generated by 2 exp (2n + 1) + 1 can be a factor of any Fermat Number


2 ) prime numbers not generated by 2exp n + 1 also

cannot be factors

Any other sets?

( to be contd)

Devaraj
devarajkandadai is offline   Reply With Quote
Old 2004-07-23, 16:13   #2
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

80416 Posts
Cool Fermat Numbers

Quote:
Originally Posted by devarajkandadai
Non-factors of Fermat Numbers:

1) No prime number generated by 2 exp (2n + 1) + 1 can be a factor of any Fermat Number


2 ) prime numbers not generated by 2exp n + 1 also

cannot be factors

Any other sets?

( to be contd)

Devaraj
Highly obliged if you can give the proofs also.

Mally
mfgoode is offline   Reply With Quote
Old 2004-07-24, 00:00   #3
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default

2exp n + 1 is that 2^n + 1 ? ( one plus 2 to the nth power)

What is n ? Is it any integer large enough to allow 2^n + 1 to be a factor ?

Is 2 ) equivalent to: only prime numbers 2^n + 1 can be factors of fermat numbers ?

IE Binary numbers of the form 101 1001 10001
dsouza123 is offline   Reply With Quote
Old 2004-07-24, 05:12   #4
devarajkandadai
 
devarajkandadai's Avatar
 
May 2004

22×79 Posts
Default Fermat Numbers

Reply to Moderator: yes to the first query.

Also n is any positive integer

Reply to "Mally": These are corallaries of my theorem:
"A Generalisation of Fermat's Theorem" on my site:

www.crorepatibaniye.com/failurefunctions

Devaraj
devarajkandadai is offline   Reply With Quote
Old 2004-07-25, 01:45   #5
dsouza123
 
dsouza123's Avatar
 
Sep 2002

66210 Posts
Default

concerning point 2)
if I correctly understand what you wrote, then it isn't correct.

Counter example
Fermat5 = 2^(2^5) + 1 = 2^32 + 1 = 4294967297
= 100000000000000000000000000000001 (binary)

the possible factors are of the form k*(2^7) + 1 with k >= 0
with k = 0 factor = 1
with k = 5 factor = 5*(2^7) + 1 = 5*128 + 1 = 641 = 1010000001

641 is prime, is a factor of Fermat5, isn't 2^n + 1
dsouza123 is offline   Reply With Quote
Old 2004-07-26, 04:28   #6
devarajkandadai
 
devarajkandadai's Avatar
 
May 2004

22·79 Posts
Default Fermat Numbers

To the moderator:

641 is a factor of F5 i.e. 2^2^5 + 1; it is not a factor of
2^(2n + 1) + 1. Hope this clarifies the matter.
Devaraj
devarajkandadai is offline   Reply With Quote
Old 2004-07-26, 13:27   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Thumbs down

Quote:
Originally Posted by devarajkandadai
To the moderator:

641 is a factor of F5 i.e. 2^2^5 + 1; it is not a factor of
2^(2n + 1) + 1. Hope this clarifies the matter.
Devaraj

Allow me to clarify this matter. I mean no disrespect, but the original
poster would greatly benefit from actually READING about this subject.

Any primitive prime factor of 2^k+1, must equal 1 mod 2k. Period.
Primitive means that it does not divide 2^m+1 for any m < k.
e.g. 11 is a primitive prime factor of 2^5+1. It is also a prime factor
of (say) 2^15+1, but it is not a primitive prime factor.

For Fermat numbers, when k = 2^n (say) we can say a little bit more
because 2 is a primitive root. In this case, we have that any prime factor
is 1 mod 4k.

Any two different Fermat numbers are also relatively prime.

Now can we put the random speculations to rest????
R.D. Silverman is offline   Reply With Quote
Old 2004-07-27, 04:12   #8
devarajkandadai
 
devarajkandadai's Avatar
 
May 2004

22·79 Posts
Default Fermat Numbers

Thank you for further clarification, Dr. Silverman.,

Devaraj

Last fiddled with by devarajkandadai on 2004-07-27 at 04:13
devarajkandadai is offline   Reply With Quote
Old 2004-07-27, 12:27   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Thumbs up

Quote:
Originally Posted by Bob Silverman
Allow me to clarify this matter. I mean no disrespect, but the original
poster would greatly benefit from actually READING about this subject.

Any primitive prime factor of 2^k+1, must equal 1 mod 2k. Period.
Primitive means that it does not divide 2^m+1 for any m < k.
e.g. 11 is a primitive prime factor of 2^5+1. It is also a prime factor
of (say) 2^15+1, but it is not a primitive prime factor.

For Fermat numbers, when k = 2^n (say) we can say a little bit more
because 2 is a primitive root. In this case, we have that any prime factor
is 1 mod 4k.

Any two different Fermat numbers are also relatively prime.

Now can we put the random speculations to rest????
The above gives correct results, but gives a misstatement.

"because 2 is a primitive root. "

should clearly have been: because 2 is a quadratic residue.

For those who are interested, here is a full proof.

Assume 2^2^n + 1 = 0 mod p
Then 2^2^n = -1 mod p
2^2^(n+1) = 1 mod p
By Lagrange's Thm, the order of any element must divide the order of the
group. The order of the group is p-1, hence

2^(n+1) | p - 1 and therefore p = k* 2^(n+1) + 1 for some k.

But we can say more. Note that for n > 1, we also have p = 1 mod 8.
By quadratic reciprocity 2 is a quadratic residue. From Euler's criteria we
then obtain:

2^ ((p-1)/2) = 1 mod p and hence (2^(n+1)) | (p-1)/2. This last result
yields p = k^2^(n+2) + 1.

Euler's criterion says that a^((p-1)/2) = 1 or -1 mod p depending on
whether a is (resp.) a residue or non-residue.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ecm with Fermat numbers ET_ FermatSearch 1 2016-08-02 19:40
P-1/P+1 on Fermat numbers ATH Operazione Doppi Mersennes 2 2015-01-25 06:27
Generalized Fermat Numbers ET_ Programming 4 2008-06-23 07:59
Are there any Fermat numbers that might be prime? jasong Math 39 2007-10-27 23:11
LLT numbers, linkd with Mersenne and Fermat numbers T.Rex Math 4 2005-05-07 08:25

All times are UTC. The time now is 23:44.

Sat Dec 5 23:44:49 UTC 2020 up 2 days, 19:56, 0 users, load averages: 1.74, 1.75, 1.75

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.