mersenneforum.org > Math Proof of Primality Test for Fermat Numbers
 Register FAQ Search Today's Posts Mark Forums Read

2012-04-02, 05:20   #1
princeps

Nov 2011

22×3 Posts
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
 FermatProof.pdf (169.1 KB, 244 views)

 2012-04-02, 06:01 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 26AD16 Posts Not too late for the April 1st! (at least in our TZ)
 2012-04-02, 07:00 #3 rajula     "Tapio Rajala" Feb 2010 Finland 4738 Posts The proof was also posted on MO (and not on 1st of April).
 2012-04-02, 07:24 #4 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
2012-04-02, 07:40   #5
princeps

Nov 2011

C16 Posts

Quote:
 Originally Posted by Dubslow 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 .

 2012-04-02, 08:02 #6 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40=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
 2012-04-02, 08:59 #7 literka     Mar 2010 26×3 Posts Sorry i did not notice the assumption n>=2 Last fiddled with by literka on 2012-04-02 at 09:05
2012-04-02, 09:03   #8
princeps

Nov 2011

148 Posts

Quote:
 Originally Posted by literka 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$

 2012-04-02, 09:13 #9 rajula     "Tapio Rajala" Feb 2010 Finland 32×5×7 Posts 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.
2012-04-02, 11:40   #10
literka

Mar 2010

26·3 Posts

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

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.

2012-04-02, 12:31   #11
princeps

Nov 2011

22×3 Posts

Quote:
 Originally Posted by literka 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..

 Similar Threads Thread Thread Starter Forum Replies Last Post Godzilla Miscellaneous Math 40 2018-10-17 00:11 Arkadiusz Math 6 2011-04-05 19:39 AntonVrba Math 96 2009-02-25 10:37 T.Rex Math 0 2004-10-26 21:37 T.Rex Math 2 2004-09-11 07:26

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

Mon Aug 8 13:33:09 UTC 2022 up 32 days, 8:20, 1 user, load averages: 1.42, 1.63, 1.55