In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, Pépin's test is a primality test

Primality test

A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not...

, which can be used to determine whether a Fermat number is prime

Prime number

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

. It is a variant of Proth's test

Proth's theorem

In number theory, Proth's theorem is a primality test for Proth numbers.It states that if p is a Proth number, of the form k2n + 1 with k odd and k In number theory, Proth's theorem is a primality test for Proth numbers....

. The test is named for a French mathematician, Théophile Pépin

Théophile Pépin

Jean François Théophile Pépin was a French mathematician.Born in Cluses, Haute-Savoie, he became a Jesuit in 1846, and from 1850 to 1856 and from 1862 to 1871 he was Professor of Mathematics at various Jesuit colleges. He was appointed Professor of Canon Law in 1873, moving to Rome in 1880. He...

.

Description of the test

Let be the nth Fermat number. Pépin's test states that for n > 0, is prime if and only if
The expression can be evaluated modulo by repeated squaring

Exponentiation by squaring

Exponentiating by squaring is a general method for fast computation of large integer powers of a number. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. In additive notation the appropriate term is double-and-add...

. This makes the test a fast polynomial-time algorithm. However, Fermat numbers grow so rapidly that only a handful of Fermat numbers can be tested in a reasonable amount of time and space.

Other bases may be used in place of 3, for example 5, 6, 7, or 10 .

Proof of correctness

For one direction, assume that the congruence
holds. Then , thus the multiplicative order

Multiplicative order

In number theory, given an integer a and a positive integer n with gcd = 1, the multiplicative order of a modulo n is the smallest positive integer k withThe order of a modulo n is usually written ordn, or On.- Example :To determine the multiplicative order of 4 modulo 7, we compute 42 = 16 ≡ 2 ...

 of 3 modulo divides , which is a power of two. On the other hand, the order does not divide , and therefore it must be equal to . In particular, there are at least numbers below coprime to , and this can happen only if is prime.

For the other direction, assume that is prime. By Euler's criterion

Euler's criterion

In mathematics, Euler's criterion is used in determining in number theory whether a given integer is a quadratic residue modulo a prime.-Definition:Euler's criterion states:Let p be an odd prime and a an integer coprime to p. Then...

,,
where is the Legendre symbol

Legendre symbol

In number theory, the Legendre symbol is a multiplicative function with values 1, −1, 0 that is a quadratic character modulo a prime number p: its value on a quadratic residue mod p is 1 and on a quadratic non-residue is −1....

. By repeated squaring, we find that , thus , and .
As , we conclude from the law of quadratic reciprocity.

External links

• The Prime Glossary: Pepin's test