Fermat Numbers

[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

[mfgoode]

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

[dsouza123]

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

[devarajkandadai]

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

[dsouza123]

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

[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

[R.D. Silverman]

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

[devarajkandadai]

Thank you for further clarification, Dr. Silverman.,

Devaraj

[R.D. Silverman]

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.