In algebra and number theory, Wilson's theorem states that a natural number n > 1 is a prime number if and only if the product of all the positive integers less than n is one less than a multiple of n. That is (using the notations of modular arithmetic), the factorial
In other words, any integer n > 1 is a prime number if, and only if, (n − 1)!
+ 1 is divisible by n.[1] The theorem was first stated by Ibn al-Haytham c. 1000 AD.
[2] Edward Waring announced the theorem in 1770 without proving it, crediting his student John Wilson for the discovery.
[4] There is evidence that Leibniz was also aware of the result a century earlier, but never published it.
is divided by n. (In the notation of modular arithmetic, the remainder when m is divided by n is written m mod n.) The background color is blue for prime values of n, gold for composite values.
As a biconditional (if and only if) statement, the proof has two halves: to show that equality does not hold when
can be factored as the product of two unequal numbers,
The first two proofs below use the fact that the residue classes modulo a prime number form a finite field (specifically, a prime field).
form a field, every non-zero residue
Euclid's lemma implies[a] that the only values of
Again, the result is trivial for p = 2, so suppose p is an odd prime, p ≥ 3.
Now consider h also has degree p − 1 and leading term xp − 1.
Modulo p, Fermat's little theorem says it also has the same p − 1 roots, 1, 2, ..., p − 1.
Finally, consider f has degree at most p − 2 (since the leading terms cancel), and modulo p also has the p − 1 roots 1, 2, ..., p − 1.
The third Sylow theorem implies Multiplying both sides by (p − 1) gives that is, the result.
In practice, Wilson's theorem is useless as a primality test because computing (n − 1)!
modulo n for large n is computationally complex, and much faster primality tests are known (indeed, even trial division is considerably more efficient).
[citation needed] Used in the other direction, to determine the primality of the successors of large factorials, it is indeed a very fast and effective method.
[citation needed] Using Wilson's Theorem, for any odd prime p = 2m + 1, we can rearrange the left hand side of
We can use this fact to prove part of a famous result: for any prime p such that p ≡ 1 (mod 4), the number (−1) is a square (quadratic residue) mod p. For this, suppose p = 4k + 1 for some integer k. Then we can take m = 2k above, and we conclude that (m!
Wilson's theorem has been used to construct formulas for primes, but they are too slow to have practical value.
Wilson's theorem allows one to define the p-adic gamma function.
Gauss proved[7][non-primary source needed] that
That is, the product of the positive integers less than m and relatively prime to m is one less than a multiple of m when m is equal to 4, or a power of an odd prime, or twice a power of an odd prime; otherwise, the product is one more than a multiple of m. The values of m for which the product is −1 are precisely the ones where there is a primitive root modulo m. Original : Inoltre egli intravide anche il teorema di Wilson, come risulta dall'enunciato seguente:"Productus continuorum usque ad numerum qui antepraecedit datum divisus per datum relinquit 1 (vel complementum ad unum?)
si datus sit primitivus.
Si datus sit derivativus relinquet numerum qui cum dato habeat communem mensuram unitate majorem.
"Egli non giunse pero a dimostrarlo.Translation : In addition, he [Leibniz] also glimpsed Wilson's theorem, as shown in the following statement:"The product of all integers preceding the given integer, when divided by the given integer, leaves 1 (or the complement of 1?)
"However, he didn't succeed in proving it.The Disquisitiones Arithmeticae has been translated from Gauss's Ciceronian Latin into English and German.
The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.