OFFSET
0,6
COMMENTS
For n>=1 the Fermat Number F(n) is prime if and only if 3^((F(n) - 1)/2) is congruent to -1 (mod F(n)).
Any positive integer k for which the Jacobi symbol (k|F(n)) is -1 can be used as the base instead.
REFERENCES
M. Krizek, F. Luca & L. Somer, 17 Lectures on Fermat Numbers, Springer-Verlag NY 2001, pp. 42-43.
LINKS
Dennis Martin, Table of n, a(n) for n = 0..11
Chris Caldwell, The Prime Pages: Pepin's Test.
FORMULA
a(n) = 3^((F(n) - 1)/2) (mod F(n)), where F(n) is the n-th Fermat Number, using the symmetry mod (so (-F(n)-1)/2 < a(n) < (F(n)-1)/2).
EXAMPLE
a(4) = 3^(32768) (mod 65537) = 65536 = -1 (mod F(4)), therefore F(4) is prime.
a(5) = 3^(2147483648) (mod 4294967297) = 10324303 (mod F(5)), therefore F(5) is composite.
MAPLE
f:= proc(n) local F;
F:= 2^(2^n) + 1;
`mods`(3 &^ ((F-1)/2), F)
end proc:
seq(f(n), n=0..10); # Robert Israel, Dec 19 2016
PROG
(PARI) a(n)=centerlift(Mod(3, 2^(2^n)+1)^(2^(2^n-1))) \\ Jeppe Stig Nielsen, Dec 19 2016
CROSSREFS
KEYWORD
sign
AUTHOR
Dennis Martin (dennis.martin(AT)dptechnology.com), Nov 27 2008
STATUS
approved