221
правка
Изменения
Нет описания правки
{{Требует доработки
|item1=Надо привести более конструктивное доказательство теоремы. Так, чтобы получился алгоритм. И привести время работы этого алгоритма. Алгоритм должен эффективно работать для простых чисел порядка <tex>10^{300}</tex>.
}}
{{Лемма
|author= Вильсон
|statement=
Если <tex>p</tex> {{- --}} простое, то <tex>(p-1)!+1</tex> делится на <tex>p</tex>.
|proof=
При <tex>p=2, p=3</tex> доказательство очевидно. Докажем для <tex>p\geqslant 5</tex>. Так как <tex>\mathbb{Z}_p</tex> - поле, то для каждого <tex>x</tex> есть такое <tex>y</tex>, что <tex>xy\equiv 1(mod p)</tex>. Может оказаться, что для некоторых <tex>0\leqslant x\leqslant p-1</tex> выполнено <tex>x=y</tex>. Найдём все такие <tex>x</tex>, что <tex>x^2\equiv 1(mod p)</tex>. <tex>x^2-1\equiv 0(mod p) \Rightarrow (x-1)(x+1)\equiv 0(mod p)</tex>. Значит <tex>x\equiv 1(mod p)</tex> или <tex>x\equiv p-1(mod p)</tex>.
