Proof of Primality Test for Fermat Numbers
 

Let [TEX]F_n[/TEX] be a Fermat number of the form :

[TEX]F_n=2^{2^n}+1[/TEX]

Next , let's define sequence [TEX]S_i[/TEX] as :

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

Then :

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

Proof is attached . Any constructive comment is appreciated .

Not too late for the April 1st! (at least in our TZ)

The proof was also posted on [URL="http://mathoverflow.net/questions/91990/primality-criteria-for-fermat-numbers-using-quartic-recurrence-equation"]MO[/URL] (and not on 1st of April).

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.)

[QUOTE=Dubslow;295131]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.)[/QUOTE]

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 .

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.

Sorry i did not notice the assumption n>=2

[QUOTE=literka;295136]I started to read this link and I am totally confused. On the page 2 there is equality
2[SUP](Fn-1)/2[/SUP] = 1 (mod Fn)
where Fn denotes Fermat number.
Take n=1. Then
Fn=F[SUB]1[/SUB]=5,
(Fn-1)/2 = 2, 2^2=4 and
4 is not equal 1 modulo 5.
Am I missing something?[/QUOTE]

Yes , you have missed condition : [TEX]n \geq 2[/TEX]

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.

[QUOTE=princeps;295137]Yes , you have missed condition : [TEX]n \geq 2[/TEX][/QUOTE]


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.

[QUOTE=literka;295145]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.[/QUOTE]

As far as I know Inkeri's proof isn't freely available...Thanks for your observations..