mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Proof of Primality Test for Fermat Numbers (https://www.mersenneforum.org/showthread.php?t=16685)

princeps 2012-04-02 05:20

Proof of Primality Test for Fermat Numbers
 
1 Attachment(s)
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 .

Batalov 2012-04-02 06:01

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

rajula 2012-04-02 07:00

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

Dubslow 2012-04-02 07:24

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

princeps 2012-04-02 07:40

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

Dubslow 2012-04-02 08:02

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.

literka 2012-04-02 08:59

Sorry i did not notice the assumption n>=2

princeps 2012-04-02 09:03

[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]

rajula 2012-04-02 09:13

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.

literka 2012-04-02 11:40

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

princeps 2012-04-02 12:31

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


All times are UTC. The time now is 02:26.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.