Wilson theorem

The set of Wilson (named after John Wilson ) is a mathematical theorem from the theory of numbers . It makes statements about divisibility about natural or whole numbers and is therefore also assigned to elementary number theory , with whose methods it can also be proven.

sentence

Wilson's theorem is: be a natural number. Then is a prime number if and only if is divisible by . Here referred to the faculty , so the product . ${\displaystyle p\geq 2}$ ${\displaystyle p}$ ${\displaystyle (p-1)!+1}$ ${\displaystyle p}$ ${\displaystyle (p-1)!}$ ${\displaystyle 1\cdot 2\cdot 3\cdots (p-1)}$

With the help of the concept of congruence one can also formulate the sentence like this: If it is a natural number, then it holds ${\displaystyle p\geq 2}$

${\displaystyle (p-1)!\equiv -1{\pmod {p}}\Longleftrightarrow p\ \mathrm {ist} \ \mathrm {prim.} }$

Conversely, one can also conclude with the proposition: If it is a natural number, then it holds ${\displaystyle n\geq 2}$

${\displaystyle (n-1)!\equiv {\begin{cases}n-1{\pmod {n}},&\mathrm {falls} \ n\ \mathrm {Primzahl} ,\\2{\pmod {n}},&\mathrm {falls} \ n=4,\\0{\pmod {n}},&\mathrm {sonst} .\end{cases}}}$

So if and is not divisible by, then is a prime number. Is but by divisible, we obtain from the set of Wilson the information that is composed, without a concrete factorization with getting to . However, the computational effort for the faculty is no less than trial divisions. ${\displaystyle n>4}$ ${\displaystyle (n-1)!}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle (n-1)!}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n=ab}$ ${\displaystyle a,b\neq 1}$

Direct evidence

The very simple proof can be given in a few words: If a prime number, the residue class ring is a field in which and are the only elements that are inverse to themselves . Therefore, every factor appears in the product together with its inverse element, which is why the product is the same . But that means precisely what follows. Conversely , if there is no prime number, there are factors with . Therefore, and , in any case, there are two factors in the product whose product is, which is why the entire product must disappear in. But that means and especially . ${\displaystyle p}$ ${\displaystyle \mathbb {Z} /(p)=\{{\overline {0}},\ldots ,{\overline {p-1}}\}}$ ${\displaystyle {\overline {1}}}$ ${\displaystyle {\overline {p-1}}}$ ${\displaystyle {\overline {2}}\cdot {\overline {3}}\cdot \ldots \cdot {\overline {p-2}}}$ ${\displaystyle {\overline {1}}}$ ${\displaystyle (p-2)!\equiv 1{\pmod {p}}}$ ${\displaystyle (p-1)!\equiv -1{\pmod {p}}}$ ${\displaystyle n>4}$ ${\displaystyle 1<a,b\leq n-2}$ ${\displaystyle n=a\cdot b}$ ${\displaystyle {\overline {a}}\cdot {\overline {b}}={\overline {0}}}$ ${\displaystyle {\overline {a}}\cdot {\overline {2b}}={\overline {0}}}$ ${\displaystyle {\overline {2}}\cdot {\overline {3}}\cdot \ldots \cdot {\overline {n-2}}}$ ${\displaystyle {\overline {0}}}$ ${\displaystyle \mathbb {Z} /(n)}$ ${\displaystyle (n-2)!\equiv 0{\pmod {n}}}$ ${\displaystyle (n-1)!\equiv 0{\pmod {n}}}$

Remarks

• For every natural number , each of the two congruences and exactly satisfied if the other is satisfied. One wins one from the other (and vice versa) through right multiplication , taking into account that the congruences and always apply for and . Wilson's theorem is therefore equivalent to what Sierpiński calls "Leibniz's theorem" ${\displaystyle n\geq 2}$ ${\displaystyle (n-2)!\equiv 1{\pmod {n}}}$ ${\displaystyle (n-1)!\equiv -1{\pmod {n}}}$ ${\displaystyle -1}$ ${\displaystyle n\in N}$ ${\displaystyle n\geq 2}$ ${\displaystyle n-1\equiv -1{\pmod {n}}}$ ${\displaystyle (n-1)\cdot (-1)\equiv (-1)^{2}\equiv 1{\pmod {n}}}$

A natural number is prime if and only if it is congruent ${\displaystyle n\geq 2}$

${\displaystyle (n-2)!\equiv 1{\pmod {n}}}$

Fulfills.

• Fischer / Sacher - as well as other authors - only cite the congruence statement for prime numbers as Wilson's theorem . ${\displaystyle p\in \mathbb {N} }$

Examples

The following table shows the values ​​of n from 2 to 30, ( n -1)! and the remainder of ( n -1)! modulo n . If n is a prime number, then the background color is pink . And if n is a composite number, then the background color is light green .

Table of the remainder modulo n

${\displaystyle n}$	${\displaystyle (n-1)!}$	${\displaystyle (n-1)!\ {\bmod {\ }}n}$
2	1	1
3	2	2
4th	6th	2
5	24	4th
6th	120	0
7th	720	6th
8th	5040	0
9	40320	0
10	362880	0
11	3628800	10
12	39916800	0
13	479001600	12
14th	6227020800	0
15th	87178291200	0
16	1307674368000	0
17th	20922789888000	16
18th	355687428096000	0
19th	6402373705728000	18th
20th	121645100408832000	0
21st	2432902008176640000	0
22nd	51090942171709440000	0
23	1124000727777607680000	22nd
24	25852016738884976640000	0
25th	620448401733239439360000	0
26th	15511210043330985984000000	0
27	403291461126605635584000000	0
28	10888869450418352160768000000	0
29	304888344611713860501504000000	28
30th	8841761993739701954543616000000	0

history

The result, now known as Wilson's Theorem, was first discovered by Ibn al-Haytham , but was eventually named after John Wilson (a student of the English mathematician Edward Waring ) who rediscovered it more than 700 years later. Waring published this theorem in 1770, although neither he nor Wilson could provide evidence. Lagrange gave the first proof in 1773.

According to Dietrich Mahnke, there is reason to assume that Leibniz knew about this result a century before, but never published it. In a manuscript from 1683, Leibniz proved Fermat's Little Theorem and also mentioned the fact that is equivalent to the Wilson theorem for prime numbers (and referred to by Sierpiński as “Leibniz's theorem”) , where he falsely claimed that the Remainder could be 1 or −1. Mahnke explains in "Leibniz in search of a general prime number equation" on page 42: ${\displaystyle p}$ ${\displaystyle (p-2)!\equiv 1{\pmod {p}}}$

“ Leibniz does, like Vacca im Boll. di bibl. e storia mat. 1899 established that Wilson's theorem was recognized about a century earlier than Waring published it in his Meditationes algebraicae (Cantabrigiae 1770) and Lagrange first proved it at the point indicated. Leibniz has the remainder of 1 !, 2 !, 3 !, ..., 16! In handwriting 25. mod 17, furthermore the series mod 3, mod 4, ..., mod 17 compiled and concluded from this [...] Dh (p-2)! = 1 mod p, if p is a prime number, on the other hand (n-2 )! = m mod n, where m has a common factor with n. If one were to multiply the first congruence by p-1, the well-known Wilson [...] theorem would follow. Leibniz has now checked his inductively found theorem for the next prime number, p = 17, but has made a calculation. Namely, it indicates 11! = 16, ..., 15! = 16.16! = 1 mod 17, while in reality 11! = 1, ... 15! = 1.16! = 16 mod 17. This calculation error caused him to change his correct sentence and to add the wrong addition: "... relinquish [1 vel complementum ad 1]", ie. H. p-1. In fact, in his calculation, 15! = 17-1, while in reality 15! = 1 is mod 17. This explains this false addition, which Vacca did not understand. "

Generalizations

The general rule is:

${\displaystyle \prod _{\begin{matrix}1\leq a<m\\(a,m)=1\end{matrix}}a\ \equiv \ \left\{{\begin{matrix}-1\ ({\mbox{mod }}m),&{\mbox{wenn }}m=4,\;p^{\alpha },\;2p^{\alpha },\,\alpha \in \mathbb {N} ,\\\ \ 1\ ({\mbox{mod }}m)&{\mbox{sonst}}\end{matrix}}\right.}$

A slight generalization of Wilson's theorem reads:

A number is prime if and only for all ${\displaystyle p\in \mathbb {N} }$ ${\displaystyle 1\leq n\leq p}$

${\displaystyle (n-1)!(p-n)!\equiv (-1)^{n}\ \mathrm {mod} \ p}$

applies. This theorem can easily be proved with complete induction from and with Wilson's theorem. For or results Wilson's theorem. If you put here , you get: ${\displaystyle n}$ ${\displaystyle n=1}$ ${\displaystyle n=p}$ ${\displaystyle n={\frac {p+1}{2}}}$

${\displaystyle p\in \mathbb {N} }$with and odd is prime if and only if . ${\displaystyle p>2}$ ${\displaystyle \left(\left({\frac {p-1}{2}}\right)!\right)^{2}\equiv (-1)^{\frac {p+1}{2}}\ \mathrm {mod} \ p}$

Body-theoretical formulation

General proposition

Wilson's theorem is a special case of a general theorem from the theory of finite fields, which can be stated as follows:

Is a finite body and its unit group , ${\displaystyle K}$ ${\displaystyle K^{*}}$

so is always the equation

${\displaystyle \prod \limits _{a\in K^{*}}{a}=-1}$

Fulfills.

Proof of the general theorem

Following the presentation by Fischer / Sacher one can argue as follows:

The in preferred subset ${\displaystyle K^{*}}$

${\displaystyle M:=\{a\in K^{*}\mid a=a^{-1}\}=\{a\in K^{*}\mid a^{2}=1\}=\{a\in K^{*}\mid a^{2}-1=0\}}$

is the set of zeros of the polynomial and because true ${\displaystyle X^{2}-1\in K[X]}$ ${\displaystyle (X-1)(X+1)=X^{2}-1}$

${\displaystyle M=\{1,-1\}}$.

The other hand is evident

${\displaystyle \prod \limits _{a\in K^{*}}{a}=\prod \limits _{a\in M}{a}}$,

because every body element in the product together with its inverse always makes the contribution . ${\displaystyle a\in K^{*}\setminus M}$ ${\displaystyle 1}$

So the asserted equation holds.

Related terms

The result of the division, which is only integer for prime numbers ${\displaystyle p}$

${\displaystyle {\frac {(p-1)!+1}{p}}}$

is called the Wilson quotient (sequence A007619 in OEIS ). ${\displaystyle W(p)}$

Prime numbers that are even divisible by are called Wilson prime numbers . ${\displaystyle p}$ ${\displaystyle (p-1)!+1}$ ${\displaystyle p^{2}}$

Example: 13 is Wilson's prime number; because . ${\displaystyle (13-1)!+1=13^{2}\cdot 2\,834\,329}$

Web links

Wikibooks: Proof of Wilson's Theorem  - Study and Teaching Materials

• Eric W. Weisstein : Wilson's Theorem . In: MathWorld (English).

Individual evidence

1. ^ Wacław Sierpiński : Elementary Theory of Numbers (=  North-Holland Mathematical Library . Volume 31 ). 2nd revised and expanded edition. North-Holland ( inter alia), Amsterdam ( inter alia ) 1988, ISBN 0-444-86662-0 ( MR0930670 ).
2. ↑ Dietrich Mahnke: "Leibniz in search of a general prime number equation." Bibl. Math. 13 (1912-13), 29-61.
3. ↑ Gerd Fischer, Reinhard Sacher: Introduction to Algebra. 1978, p. 162
4. ↑ Gerd Fischer , Reinhard Sacher: Introduction to Algebra (=  Teubner Study Books: Mathematics ). 2nd revised edition. BG Teubner , Stuttgart 1978, ISBN 3-519-12053-4 ( MR0492996 ).
5. ↑ Eric W. Weisstein : Wilson Quotient . In: MathWorld (English).