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 ?


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.

| cite | improve this answer | |
  • $\begingroup$ I didn't know that such test exists . As you can see my test uses lesser number of iterations . $\endgroup$ – pedja Mar 23 '12 at 11:58
  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Mar 23 '12 at 17:21
  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Mar 23 '12 at 17:24
  • 6
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Mar 23 '12 at 18:18
  • $\begingroup$ @EmilJerabek On my computer Java implementation of this test is approximately $1.5$ time faster than Java implementation of Inkeri's test... $\endgroup$ – pedja Apr 6 '12 at 4:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.