Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Wilson's theorem
Summary
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 satisfies
exactly when n is a prime number. In other words, any number n is a prime number if, and only if, (n − 1)! + 1 is divisible by n.
This theorem was stated by Ibn al-Haytham (c. 1000 AD), and, in the 18th century, by the English mathematician John Wilson. Edward Waring announced the theorem in 1770, although neither he nor his student Wilson could prove it. Lagrange gave the first proof in 1771. There is evidence that Leibniz was also aware of the result a century earlier, but he never published it.
For each of the values of n from 2 to 30, the following table shows the number (n − 1)! and the remainder when (n − 1)! 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.
The proofs (for prime moduli) below use the fact that the residue classes modulo a prime number are a field—see the article prime field for more details. Lagrange's theorem, which states that in any field a polynomial of degree n has at most n roots, is needed for all the proofs.
If n is composite it is divisible by some prime number q, where 2 ≤ q ≤ n − 2. Because divides , let for some integer . Suppose for the sake of contradiction that were congruent to −1 (mod n) where n is composite. Then (n-1)! would also be congruent to −1 (mod q) as implies that for some integer which shows (n-1)! being congruent to -1 (mod q). But (n − 1)! ≡ 0 (mod q) by the fact that q is a term in (n-1)! making (n-1)! a multiple of q. A contradiction is now reached.
In fact, more is true. With the sole exception of 4, where 3! = 6 ≡ 2 (mod 4), if n is composite then (n − 1)! is congruent to 0 (mod n).
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.