Pépin's test

The Pépin test is a primality test for Fermat numbers. It checks whether natural numbers of the form

Prim or not. The basis for the Pépin - test work by Théophile Pépin (1826 - 1904), François Proth (1852 - 1879) and Édouard Lucas.

Operation

The test is based on the following sentence:

Fk for k ≥ 1 if a prime number if the congruence

Is satisfied.

Since F0 = 3, the theorem is not valid for k = 0 for k = 1 Fk = 5 and we have 32 = 9 ≡ -1 mod 5 To calculate for large k using the modulo command is already included in the intermediate steps is, as illustrated in the example below.

Proof of the theorem

" ": If for some k ≥ 1, the Fermat number Fk prime, then by Euler's criterion for the Legendre symbol congruence

Due to the quadratic reciprocity law applies

Here, the congruences Fk ≡ 1 mod 4 and Fk ≡ 2 mod 3 ( to show by induction ) can be used. This completes the proof in one direction is provided.

" ' Suppose, conversely, that

Applies, it follows by squaring

According to the improved Lucas- test follows that Fk is prime.

The application of the improved Lucas- testing is particularly simple in this case, since Fk - 1 only one prime factor, namely 2 has.

Example

As an example, we show by means of Pépin tests that F3 = 28 1 = 257 is a prime number. We calculate 3128 mod 257 gradually and get 3128 ≡ -1 mod 257:

38 = 6561 ≡ -121 mod 257, → ≡ 316 ( -121 ) 2 ≡ -8 mod 257, → ≡ 332 (-8 ) 2 = 64 mod 257, → 364 ≡ 642 ≡ -16 mod 257, → ≡ 3128 (-16 ) 2 = 256 ≡ -1 mod 257