mersenneforum.org > Math Fermat Numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2004-07-23, 08:15 #1 devarajkandadai     May 2004 22·79 Posts 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
2004-07-23, 16:13   #2
mfgoode
Bronze Medalist

Jan 2004
Mumbai,India

22·33·19 Posts
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

 2004-07-24, 00:00 #3 dsouza123     Sep 2002 2·331 Posts 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
 2004-07-24, 05:12 #4 devarajkandadai     May 2004 1001111002 Posts 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
 2004-07-25, 01:45 #5 dsouza123     Sep 2002 2×331 Posts 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
 2004-07-26, 04:28 #6 devarajkandadai     May 2004 1001111002 Posts 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
2004-07-26, 13:27   #7
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×1,877 Posts

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

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????

 2004-07-27, 04:12 #8 devarajkandadai     May 2004 22·79 Posts Fermat Numbers Thank you for further clarification, Dr. Silverman., Devaraj Last fiddled with by devarajkandadai on 2004-07-27 at 04:13
2004-07-27, 12:27   #9
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

1D5416 Posts

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.

 Similar Threads Thread Thread Starter Forum Replies Last Post ET_ FermatSearch 1 2016-08-02 19:40 ATH Operazione Doppi Mersennes 2 2015-01-25 06:27 ET_ Programming 4 2008-06-23 07:59 jasong Math 39 2007-10-27 23:11 T.Rex Math 4 2005-05-07 08:25

All times are UTC. The time now is 16:52.

Sun Jan 29 16:52:58 UTC 2023 up 164 days, 14:21, 0 users, load averages: 1.42, 1.53, 1.28