Az Eszterházy Károly Tanárképző Főiskola Tudományos Közleményei. 1995-1996. Sectio Mathematicae. (Acta Academiae Paedagogicae Agriensis : Nova series ; Tom. 23)

GRYTCZUK, A. and GRYTCZUK, J., A primality test for Fermat numbers

A primality test for Fermat numbers A. GRYTCZUK and J. GRYTCZUK Abstract. Relying on some properties of Bernoulli numbers we derive a new primality criterion for Fermat numbers F

n—2

2"-fl. 1. Introduction. For a given a sequence of positive integers it is often very hard to decide whether there are infinitely many primes among its terms. Consider for example the sequence 2+1, 2

2 + 1, 2

3 + 1, 2

4 + 1, It is an easy observation that 2

m -f 1, rn > 0 can be a prime only if rn is itself a power of 2. So, we obtain in this way the Fermat numbers F

n = 2

2 +1, n > 0. The first five of them are F

0 = 3, F

x = 5, F

2 = 17, F

3 = 257, F

4 = 65 537 and they are all primes. Fermat thought that this pattern persists but Euler found that F

b is composite: F

5 = 2

3

2 + 1 = (641)(6700417). In fact, for 4 < n < 24 and for many larger values of of n Fermat numbers are known to be composite. It is strange that beyond no further Fermat primes have been found. The prupose of this note is to give a necessry and sufficient condition for the Fermat number F

n to be a prime. Our test is similar to the Lucas

— Lehmer test for Mersenne numbers M

n = 2

7

1 — 1 (see [2]). Indeed, primality of F

n depends on whether F

n divides an appropriate term of the recurrent sequence T(m) defined by (la) T(l) = 1, (lb) T(m) = (-1)""

1 + (-l)

i+

1 f

2

m ~ l

S)r(m - j), m> 1. i-1 V ' / This is stated in the following theorem. Theorem. Let k and n be fixed positive integers such that 0 < k < [log n log 2], n > 1 and let T(m) be as above. Then the Fermat number F

k is a prime if and only if F

k does not divide T(2

n_

1). 2. Proof of the Theorem. We derive our assertion from the following lemma. Lemma. Let B2

m denote the 2m-th Bernoulli number. Then for every