Вильсон теоремасы және жай сандар

Theorem on prime numbers
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 integer n > 1 is a prime number if, and only if, (n − 1)! + 1 is divisible by n.

The theorem was first stated by Ibn al Haytham c. 1000 AD. Edward Waring announced the theorem in 1770 without proving it, crediting his student John Wilson for the discovery. Lagrange gave the first proof in 1771. There is evidence that Leibniz was also aware of the result a century earlier, but never published it.

The proofs (for prime moduli) below use the fact that the residue classes modulo a prime number are a finite 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 1=2 ≤ q ≤ n − 2. Because divides , let for some integer Suppose for the sake of contradiction that were congruent to 1=−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). The proof is divided into two cases: First, if n can be factored as the product of two unequal numbers, 1=n = ab, where 2 ≤ a < b ≤ n − 2, then both a and b will appear in the product 1=1 × 2 × × (n − 1) = (n − 1)! and (n − 1)! will be divisible by n. If n has no such factorization, then it must be the square of some prime q, q > 2. But then 2q < q2 = n, both q and 2q will be factors of (n − 1)!, and again n divides (n − 1)!.

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). Used in the other direction, to determine the primality of the successors of large factorials, it is indeed a very fast and effective method. This is of limited utility, however.

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.