In mathematics, Wilson's theorem (also known as Al-Haytham's theorem) states that p > 1 is a prime number if and only if Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ... This article does not cite any references or sources. ...

(see factorial and modular arithmetic for the notation). For factorial rings in mathematics, see unique factorisation domain. ... Modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic because of its use in the 24-hour clock system) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ...

History

The theorem was first discovered by the Iraqi mathematician Ibn al-Haytham (known as Alhazen in Medieval Europe) circa 1000 AD, but it is named after John Wilson (a student of the English mathematician Edward Waring) who stated it in the 18th century.^[1] Waring announced the theorem in 1770, although neither he nor Wilson could prove it. Lagrange gave the first proof in 1773. There is evidence that Leibniz was also aware of the result a century earlier, but he never published it. Islamic mathematics is the profession of Muslim Mathematicians. ... Alhazen Abu Ali al-Hasan Ibn Al-Haitham, (965-1040) was a Arab Muslim mathematician; he is sometimes called al-Basri, after his birthplace. ... The Middle Ages formed the middle period in a traditional schematic division of European history into three ages: the classical civilization of Antiquity, the Middle Ages, and modern times, beginning with the Renaissance. ... Europe in 1000 The year 1000 of the Gregorian Calendar was the last year of the 10th century as well as the last year of the first millennium. ... John Wilson (1741 – 1793) was an English mathematician who had a theorem, Wilsons Theorem, named after him for its discovery, not its proof. ... Leonhard Euler, one of the greatest mathematicians of all time A mathematician is a person whose primary area of study and research is the field of mathematics. ... Edward Waring (1736 - August 15, 1798) was British mathematician who was born in Old Heath (near Shrewsbury) Shropshire England and died in Pontesbury Shropshire England He was Lucasian professor of mathematics at Cambridge University from 1760 until his death. ... Joseph-Louis Lagrange, comte de lEmpire (January 25, 1736 – April 10, 1813; b. ... It has been suggested that this article be split into multiple articles. ...

Proofs

First proof

This proof uses the fact that if p is a prime, then the set of numbers G = (Z/pZ)^× = {1, 2, ... p − 1} forms a group under multiplication modulo p. This means that for each element a in G, there is a unique inverse element b in G such that ab ≡ 1 (mod p). If a ≡ b (mod p), then a² ≡ 1 (mod p), which forces a² − 1 = (a + 1)(a − 1) ≡ 0 (mod p), and since p is prime, this forces a ≡ 1 or −1 (mod p), i.e. a = 1 or a = p − 1. This picture illustrates how the hours in a clock form a group. ... In mathematics, the multiplicative group of integers modulo n is the group defined by multiplication of the units (that is, the numbers relatively prime to ) in the ring for a given integer . ... In mathematics, the inverse of an element x, with respect to an operation *, is an element x such that their compose gives a neutral element. ...

In other words, 1 and p − 1 are each their own inverse, but every other element of G has a distinct inverse, and so if we collect the elements of G pairwise in this fashion and multiply them all together, we get the product −1. For example, if p = 11, we have

The property of commutative, associative are used in above procedure. All of elements in above product will be in the form g g ^-1 ≡ 1 (mod p) except 1 (p-1) which is left.

If p = 2, the result is trivial to check.

For a converse (but see below for a more exact converse result), suppose the congruence holds for a composite n, and note that then n has a proper divisor d with 1 < d < n. Clearly, d divides (n − 1)! But by the congruence, d also divides (n − 1)! + 1, so that d divides 1, a contradiction. In mathematics and especially in abstract algebra, a congruence relation or simply congruence is an equivalence relation that is compatible with some algebraic operation(s). ... A composite number is a positive integer which has a positive divisor other than one or itself. ... In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ... In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ...

Second proof

Here is another proof of the first direction: Suppose p is prime. Consider the polynomial

Recall that if f(x) is a nonzero polynomial of degree d over a field F, then f(x) has at most d roots over F. Now, with g(x) as above, consider the polynomial In abstract algebra, a field is an algebraic structure in which the operations of addition, subtraction, multiplication and division (except division by zero) may be performed, and the same rules hold which are familiar from the arithmetic of ordinary numbers. ...

Since the leading coefficients cancel, we see that f(x) is a polynomial of degree at most p − 2. Reducing mod p, we see that f(x) has at most p − 2 roots mod p. But by Fermat's little theorem, each of the elements 1, 2, ..., p − 1 is a root of f(x). This is impossible, unless f(x) is identically zero mod p, i.e. unless each coefficient of f(x) is divisible by p. Fermats little theorem (not to be confused with Fermats last theorem) states that if p is a prime number, then for any integer a, This means that if you start with a number, initialized to 1, and repeatedly multiply, for a total of p multiplications, that number by...

But since p is odd, the constant term of f(x) is just (p − 1)! + 1, and the result follows.

Applications

Wilson's theorem is useless as a primality test, since computing (n − 1)! is difficult for large n. A primality test is an algorithm for determining whether an input number is prime. ...

Using Wilson's Theorem, we have for any prime p:

where p = 2m + 1. This becomes

And so primality is determined by the quadratic residues of p. We can use this fact to prove part of a famous result: −1 is a square (quadratic residue) mod p if p ≡ 1 (mod 4). For suppose p = 4k + 1 for some integer k. Then we can take m = 2k above, and we conclude that In mathematics, a number q is called a quadratic residue modulo p if there exists an integer x such that: Otherwise, q is called a quadratic non-residue. ...

Generalization

There is also a generalization of Wilson's theorem, due to Carl Friedrich Gauss: Johann Carl Friedrich Gauß (in English literature sometimes written Gauss) ( ; Latin: ) (30 April 1777 – 23 February 1855) was a German mathematician and scientist of profound genius who contributed significantly to many fields, including number theory, analysis, differential geometry, geodesy, magnetism, astronomy, and optics. ...

where p is an odd prime.

A further generalization of Wilson's theorem was proven in 2003 by Thomas Krakow:

A number is prime iff for all

holds. This theorem can be proven easily by induction to n. For n = 1 and n = p we obtain Wilson's theorem. If we set we obtain:

is prime if and only if

Converse

The converse to Wilson's theorem states that for a composite number n > 5, A composite number is a positive integer which has a positive divisor other than one or itself. ...

n divides (n − 1)!.

This leaves the case n = 4, for which 3! is congruent to 2 modulo 4.

In fact if q is a prime factor of n, so that n = qa, the numbers

1, 2, ..., n − 1

include a − 1 multiples of q. Therefore the power of q dividing the factorial is at least n/q − 1; and the power dividing n at most

log n/log q.

The required inequality

log n/log q ≤ n/q − 1

does hold in general, except for the case q = 2 and n = 4.

See also

• Primitive root modulo n

A primitive root modulo n is a concept from modular arithmetic in number theory. ...

Notes

The MacTutor history of mathematics archive is a website hosted by University of St Andrews in Scotland. ...

References

• Ore, Oystein (1988). Number Theory and its History. Dover, 259-271. ISBN 0-486-65620-9.