# Primality criteria for Fermat numbers using quartic recurrence equation

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$

I have found that :

$F_2 \mid S_1 , ~F_3 \mid S_3 ,~F_4 \mid S_7$

where $F_2 , F_3 , F_4$ are Fermat numbers .

Conjecture :

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

In this document you can find my proof of this conjecture .

Question :

Is my proof acceptable ? Are there similar criteria in the literature ?

-
Skimming through it, I didn't see anything obviously wrong. –  zeb Mar 23 '12 at 10:28
I like the conjecture, but your question is not appropriate for Math Overflow. May I suggest that you change it to "I think I've proved that ..., are there similar criteria in the literature?" Otherwise, I suspect that this question will be closed. –  Kevin O'Bryant Mar 23 '12 at 17:38
–  Emil Jeřábek Mar 23 '12 at 18:23

There are already similar results in the literature giving necessary and sufficient conditions for primality of Fermat numbers. For example, using the sequence $(R_n)_{n \geq 0}$ defined by $R_0=8$ and $R_{n+1}=R_n^2-2$, Inkeri has proved that $F_n$ ($n \geq 2$) is prime if and only if $F_n$ divides $R_{2^n-2}$.

The reference is Inkeri, Tests for primality, Ann. Acad. Sci. Fenn. Ser. A I 279 (1960), 1-19.

See also Krizek, Luca, Somer, 17 Lectures on Fermat Numbers, CMS Books, Springer, 2001.

-
I didn't know that such test exists . As you can see my test uses lesser number of iterations . –  pedja Mar 23 '12 at 11:58
I don't know how you count iterations. Looking at the indices suggests to me that you use more iterations than the test of Inkeri does. Gerhard "Ask Me About System Design" Paseman, 2012.03.23 –  Gerhard Paseman Mar 23 '12 at 17:21
I apologize. I switched indices in my head as I was writing the remark. I support your assertion (based only on the post, however) that your test uses fewer indices. Gerhard "Needs To Drink More Coffee" Paseman, 2012.03.23 –  Gerhard Paseman Mar 23 '12 at 17:24
The tests are the same, one step of pedja’s recurrence amounts to doing two steps of Inkeri’s recurrence. Obviously, you can cut down the number of iterations $k$ times by doing $k$ original steps in one iteration, but that’s not going to reduce the number of arithmetic operations used. –  Emil Jeřábek Mar 23 '12 at 18:18
@EmilJerabek On my computer Java implementation of this test is approximately $1.5$ time faster than Java implementation of Inkeri's test... –  pedja Apr 6 '12 at 4:14