Разделы 
Дополнительно
Задача по математике - 3059
2019-05-06 
Теорема Вильсона. Доказать, что если целое число $p$ - простое, то число $(p-1)! + 1$ делится на $p$; если же $p$ - составное, то $(p-1)! + 1$ не делится на $p$.
Решение:
Пусть $a$ - какое-нибудь из чисел ряда $2, 3, \cdots, p - 2$. Рассмотрим числа
$a, 2a, \cdots, (p - 1)a$.
Никакие два из этих чисел не могут давать одинаковых остатков при делении на $p$; следовательно, эти числа дают при делении на $p$ остатки $1, 2, \cdots, p - 1$ и притом каждый из этих остатков получается только один раз (ср. с решением задачи 3052). В частности,
найдется такое целое число $b$ из ряда $1, 2, \cdots, p - 1$, что $ba$ при делении на $p$ дает остаток 1. При этом $b \neq 1$ и $b \neq p - 1$, ибо $2 \leq a \leq p - 2$; следовательно, при $b = 1$ число $ba = a$ при делении на $p$ дает остаток $a \neq 1$, а при $b = p - 1$ число $ba = - (p - 1)a = pa - a$ при делении на $p$ дает остаток $p - a \neq 1$. Кроме того, $b \neq а$, так как если бы $а^2$ при делении на $p$ давало остаток 1, то $a^2 - 1 = (a+1)(a-1)$ делилось бы на $p$, что возможно только при $a = 1$ и $a = p - 1$. Следовательно, $2 \leq b \leq p - 2$ и $b \neq a$, т. е. все числа $2, 3, \cdots, p - 2$ распадаются на пары чисел, произведение которых при делении на $p$ дает остаток 1.
Произведение $2 \cdot 3 \cdot \cdots \cdot (p - 2)$, содержащее $\frac{p-3}{2}$ таких пар чисел, тоже дает при делении на $p$ остаток 1, Число $p - 1$ при делении на $p$ дает остаток -1. Следовательно, $(p-1)! = 1 \cdot 2 \cdot 3 \cdot \cdots \cdot (p-2) \cdot (p - 1) = [2 \cdot 3 \cdot \cdots \cdot (p -2)] \cdot (p-1)$ при делении на $p$ дает остаток -1, т. е. $(p-1)! = kp - 1$; $(p - 1)! + 1 = kp$. Таким образом, $(p - 1)! + 1$ делится на $p$.
Если $p$ - непростое, то оно имеет простой делитель $q < p$. Тогда $(p-1)!$ делится на $q$; поэтому $(p -1)! + 1$ не делится на $q$ и, значит, не может делиться также и на $p$.
Теорема Вильсона. Доказать, что если целое число $p$ - простое, то число $(p-1)! + 1$ делится на $p$; если же $p$ - составное, то $(p-1)! + 1$ не делится на $p$.
Решение:
Пусть $a$ - какое-нибудь из чисел ряда $2, 3, \cdots, p - 2$. Рассмотрим числа
$a, 2a, \cdots, (p - 1)a$.
Никакие два из этих чисел не могут давать одинаковых остатков при делении на $p$; следовательно, эти числа дают при делении на $p$ остатки $1, 2, \cdots, p - 1$ и притом каждый из этих остатков получается только один раз (ср. с решением задачи 3052). В частности,
найдется такое целое число $b$ из ряда $1, 2, \cdots, p - 1$, что $ba$ при делении на $p$ дает остаток 1. При этом $b \neq 1$ и $b \neq p - 1$, ибо $2 \leq a \leq p - 2$; следовательно, при $b = 1$ число $ba = a$ при делении на $p$ дает остаток $a \neq 1$, а при $b = p - 1$ число $ba = - (p - 1)a = pa - a$ при делении на $p$ дает остаток $p - a \neq 1$. Кроме того, $b \neq а$, так как если бы $а^2$ при делении на $p$ давало остаток 1, то $a^2 - 1 = (a+1)(a-1)$ делилось бы на $p$, что возможно только при $a = 1$ и $a = p - 1$. Следовательно, $2 \leq b \leq p - 2$ и $b \neq a$, т. е. все числа $2, 3, \cdots, p - 2$ распадаются на пары чисел, произведение которых при делении на $p$ дает остаток 1.
Произведение $2 \cdot 3 \cdot \cdots \cdot (p - 2)$, содержащее $\frac{p-3}{2}$ таких пар чисел, тоже дает при делении на $p$ остаток 1, Число $p - 1$ при делении на $p$ дает остаток -1. Следовательно, $(p-1)! = 1 \cdot 2 \cdot 3 \cdot \cdots \cdot (p-2) \cdot (p - 1) = [2 \cdot 3 \cdot \cdots \cdot (p -2)] \cdot (p-1)$ при делении на $p$ дает остаток -1, т. е. $(p-1)! = kp - 1$; $(p - 1)! + 1 = kp$. Таким образом, $(p - 1)! + 1$ делится на $p$.
Если $p$ - непростое, то оно имеет простой делитель $q < p$. Тогда $(p-1)!$ делится на $q$; поэтому $(p -1)! + 1$ не делится на $q$ и, значит, не может делиться также и на $p$.
