Proof of Primality Test for Fermat Numbers

princeps · 2012-04-02, 05:20

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 .

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 MO (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:

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 .

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:

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=F₁=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$

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:

Originally Posted by princeps

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.

princeps · 2012-04-02, 12:31

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

2012-04-02, 08:02	#6
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3·29·83 Posts	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

2012-04-02, 08:59	#7
literka Mar 2010 192₁₀ Posts	Sorry i did not notice the assumption n>=2 Last fiddled with by literka on 2012-04-02 at 09:05

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

2012-04-02, 06:01	#2
Batalov "Serge" Mar 2008 San Diego, Calif. 2³·1,301 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 3²×5×7 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<A<43 -89<O<-88 3×29×83 Posts	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.)

2012-04-02, 09:13	#9
rajula "Tapio Rajala" Feb 2010 Finland 3²·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.