Теорема Вильсона

Теорема Вильсона

Теорема (Вильсон, О простых числах):

p — простое [math] \Leftrightarrow (p-1)! \equiv -1(mod \text{ }p)[/math].

Доказательство:

[math]\triangleright[/math]

[math] \Leftarrow [/math] Если p — не простое, тогда [math] (p-1)! \vdots p [/math] (кроме [math] p = 4 [/math]),но -1, в любом случае, мы не получим. [math] \Rightarrow [/math] Пусть [math]x : 1 \le x \le p-1[/math], для любого такого существует парный ему [math] y[/math] такой, что [math] xy \equiv 1(mod \text{ }p) [/math]. Может случиться, что для некоторых [math]x[/math] будет выполнено равенство [math]x=y[/math]. Тогда [math] x^2 \equiv 1(mod \text{ }p) [/math], значит [math] (x-1)(x+1) \vdots p [/math], значит [math] x=1 [/math] или [math]x=p-1[/math]. Таким образом последовательность [math] 2,3, \ldots,p-2 [/math] разбивается на пары, что произведение чисел каждой из них сравнимо с 1 по модулю p. Таким образом [math] (p-1)! \equiv 1(p-1)(mod \text{ }p)[/math], откуда следует, что [math] (p-1)! \equiv -1(mod \text{ }p)[/math]

[math]\triangleleft[/math]