# 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, 2012 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. Mar 23, 2012 at 17:38
• Mar 23, 2012 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 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. Mar 23, 2012 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... Apr 6, 2012 at 4:14