mersenneforum.org  

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

Reply
 
Thread Tools
Old 2012-04-02, 05:20   #1
princeps
 
Nov 2011

22·3 Posts
Default Proof of Primality Test for Fermat Numbers

Let F_n be a Fermat number of the form :

F_n=2^{2^n}+1

Next , let's define sequence S_i as :

S_i=S^4_{i-1}-4\cdot S^2_{i-1}+2 ~ \text { with } ~ S_0=8

Then :

F_n ~; (n \geq 2) ~\text{ is a prime iff }~ F_n ~ \mid ~ S_{2^{n-1}-1

Proof is attached . Any constructive comment is appreciated .
Attached Files
File Type: pdf FermatProof.pdf (169.1 KB, 125 views)
princeps is offline   Reply With Quote
Old 2012-04-02, 06:01   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

217068 Posts
Default

Not too late for the April 1st! (at least in our TZ)
Batalov is offline   Reply With Quote
Old 2012-04-02, 07:00   #3
rajula
 
rajula's Avatar
 
"Tapio Rajala"
Feb 2010
Finland

4738 Posts
Default

The proof was also posted on MO (and not on 1st of April).
rajula is offline   Reply With Quote
Old 2012-04-02, 07:24   #4
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×2,399 Posts
Default

Nice link.

Going by the bottom comment on the only answer, the two tests are exactly the same, and the other test is from 1960, so... I guess you could see if your proof improves the original proof? (I don't have anywhere near the sort of knowledge to examine the proofs.)
Dubslow is offline   Reply With Quote
Old 2012-04-02, 07:40   #5
princeps
 
Nov 2011

22·3 Posts
Default

Quote:
Originally Posted by Dubslow View Post
Nice link.

Going by the bottom comment on the only answer, the two tests are exactly the same, and the other test is from 1960, so... I guess you could see if your proof improves the original proof? (I don't have anywhere near the sort of knowledge to examine the proofs.)
The tests could be the same only in sense of computational complexity , although I think that this test should be faster than Inkeri's . Thank you anyway .
princeps is offline   Reply With Quote
Old 2012-04-02, 08:02   #6
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

11100000111012 Posts
Default

No, I'm pretty sure they're the same. R0=S0=8; Rn=R(n-1)^2-2; Sn=(S(n-1)^2-2)^2-2. Therefore, S1=R2, and trivially R2n=Sn for all n (n>=0). Your test ends with i=2^(n-1)-1, while the other test ends with k=2^n-2=2i, so the sequences are identical. All your sequence does is the same as two iterationsof R, and then do half the iterations, but that's still exactly the same thing.

Last fiddled with by Dubslow on 2012-04-02 at 08:05
Dubslow is offline   Reply With Quote
Old 2012-04-02, 08:59   #7
literka
 
literka's Avatar
 
Mar 2010

2·83 Posts
Default

Sorry i did not notice the assumption n>=2

Last fiddled with by literka on 2012-04-02 at 09:05
literka is offline   Reply With Quote
Old 2012-04-02, 09:03   #8
princeps
 
Nov 2011

148 Posts
Default

Quote:
Originally Posted by literka View Post
I started to read this link and I am totally confused. On the page 2 there is equality
2(Fn-1)/2 = 1 (mod Fn)
where Fn denotes Fermat number.
Take n=1. Then
Fn=F1=5,
(Fn-1)/2 = 2, 2^2=4 and
4 is not equal 1 modulo 5.
Am I missing something?
Yes , you have missed condition : n \geq 2
princeps is offline   Reply With Quote
Old 2012-04-02, 09:13   #9
rajula
 
rajula's Avatar
 
"Tapio Rajala"
Feb 2010
Finland

32·5·7 Posts
Default

As underlined by Dubslow, the most satisfactory answer one can give is already given in Emil Jeřábek's comment (behind the link I posted). The test is the same as Inkeri's. So, nothing new.
rajula is offline   Reply With Quote
Old 2012-04-02, 11:40   #10
literka
 
literka's Avatar
 
Mar 2010

2×83 Posts
Default

Quote:
Originally Posted by princeps View Post
Yes , you have missed condition : n \geq 2

I noticed this shortly after uploading post.
I cannot compare your work with work of Inkeri, which I do not know. I have few editorial remarks, which may be useful for you.
Everywhere you use sign of equivalence but in Lemma 2.1. you use sign of equality.
I would, in your place, specify the range of x, y, in Lemma 2.1., since you use Lemma 2.1. for non-integer elements.
literka is offline   Reply With Quote
Old 2012-04-02, 12:31   #11
princeps
 
Nov 2011

1210 Posts
Default

Quote:
Originally Posted by literka View Post
I noticed this shortly after uploading post.
I cannot compare your work with work of Inkeri, which I do not know. I have few editorial remarks, which may be useful for you.
Everywhere you use sign of equivalence but in Lemma 2.1. you use sign of equality.
I would, in your place, specify the range of x, y, in Lemma 2.1., since you use Lemma 2.1. for non-integer elements.
As far as I know Inkeri's proof isn't freely available...Thanks for your observations..
princeps is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Prime numbers test primality - with proof written in invisible ink Godzilla Miscellaneous Math 40 2018-10-17 00:11
The fastest primality test for Fermat numbers. Arkadiusz Math 6 2011-04-05 19:39
PRIMALITY PROOF for Wagstaff numbers! AntonVrba Math 96 2009-02-25 10:37
A primality test for Fermat numbers faster than Pépin's test ? T.Rex Math 0 2004-10-26 21:37
Two Primality tests for Fermat numbers T.Rex Math 2 2004-09-11 07:26

All times are UTC. The time now is 15:13.

Thu Nov 26 15:13:17 UTC 2020 up 77 days, 12:24, 4 users, load averages: 1.05, 1.24, 1.25

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.