теорема вильсона

Рассмотрим утверждение, которое является критерием простоты числа, т. е. устанавливает необходимое и достаточное условие для того, чтобы данное натуральное число было простым. Эта теорема носит имя Вильсона, но впервые была доказана Жозефом Луи Лагранжем (Joseph Louis Lagrange). Теорема Вильсона насколько красива, настолько и бесполезна практически — факториалы растут чрезвычайно быстро*.

Теорема 1.1. (Вильсон) Если $p$ — простое число, то выполняется сравнение \begin{equation} \label{VILSON_mod} (p - 1)! + 1 \equiv 0 \quad (\mathrm{mod}~p), \end{equation}

а если $p$ — составное, то соотношение ($\ref{VILSON_mod}$) не выполняется.

Для доказательства нам потребуется вспомогательное утверждение, которое интересно также и само по себе.

Лемма 1.1. Если $\textrm{НОД}(a, b) = 1$, то существуют целые числа $u$, $v$, такие что \begin{equation} \label{VILSON_lemma1} au + bv = 1. \end{equation}

Доказательство. Очевидно, достаточно доказать утверждение для случая, когда $a$, $b$ — натуральные числа. Нетривиальной частью доказательства является идея индукции по сумме $a + b$. При $a + b = 2$ имеем $a = b = 1$ и (\ref{VILSON_lemma1}) выполняется с $u = 1$, $v = 0$. Пусть теорема верна для всех $a$, $b$, таких что $\textrm{НОД}(a,b) = 1$, $a + b < k$, где $k > 2$. Тогда, так как $a + b > 2$, $\textrm{НОД}(a,b) = 1$, то $a \ne b$. Не теряя общности можно считать, что $a > b$. Поскольку, очевидно, $\textrm{НОД}(a - b, b) = 1$ и $(a - b) + b = a < k $, по индуктивному предположению существуют целые $x$, $y$, такие, что $$ (a - b)x + by = 1, $$

или $$ ax + b(y - x) = 1. $$ Положив $x = u$, $y - x = v$, получим (\ref{VILSON_lemma1}). ♦

Следствие 1.1. Если $a > 1$, $b > 1$, $НОД(a, b) = 1$, то для каждого $k = 0, 1, \ldots$ существуют единственные целые числа $u$, $v$, такие, что выполняется \begin{equation} \label{VILSON_lemma_sled} au - bv = 1, \end{equation} где $kb + 1 < u < (k + 1)b, \quad k = 0, 1, \ldots$

Доказательство. Существование $u$, $v$ следует из леммы 1.1. Докажем единственность. Предположим, от противного, что имеются такие числа $u'$, $v'$, для которых $u' \neq u$, $v' \neq v$ с условием $kb + 1 < u' < (k + 1)b$ и \begin{equation} \label{UVsled1} au' - bv' = 1. \end{equation}

Вычитая из ($\ref{VILSON_lemma_sled}$) почленно ($\ref{UVsled1}$) получим $$ a(u - u') = b(v - v'). $$ Так как $\textrm{НОД}(a, b) = 1$, то $b \,| \,(u - u')$, но $$ 1 − b < u − u' < b − 1, $$ следовательно, $u - u' = 0$, и, поэтому, $v - v' = 0$. Таким образом, $u = u'$, $v = v'$ и получено противоречие. ♦

Доказательство теоремы Вильсона. Предположим $p$ — простое, $p > 3$ (для случаев $p = 2$, $p = 3$ утверждение теоремы не трудно проверить непосредственным вычислением). Докажем, что все числа \begin{equation} \label{VILSON_numbers} 2, 3, \ldots , p - 2 \end{equation}

распадаются на пары** чисел, произведение которых даёт при делении на $p$ остаток$~1$. Пусть $q$ пробегает ряд (\ref{VILSON_numbers}), тогда по следствию из леммы 1.1 найдутся единственные целые $u$, $v$, такие что $$ qu - pv = 1, \qquad 1 < u < p $$ Следовательно, множество чисел (\ref{VILSON_numbers}) можно разбить на такие пары $(q_i, \overline{q_i})$, $i = 1, 2, \ldots, (p - 3)/2$, для которых \begin{equation} \label{VILSON_para} q_i\overline{q_i} = pv_i + 1, \end{equation} где $i = 1, 2, \ldots, (p - 3)/2. $ Перемножая (\ref{VILSON_para}) по всевозможным значениям $i$ получим $$ (p - 2)! = pV + 1, $$ где $V$ — некоторое натуральное число. После умножения обеих частей последнего равенства на $p - 1$ имеем $$ (p - 1)! = p(p - 1)V + p - 1, $$ или $$ (p - 1)! + 1 = p\big((p - 1)V + 1\big), $$ то есть, фактически, соотношение (\ref{VILSON_mod}).

Пусть теперь $p$ — составное, тогда оно имеет простой делитель $p_1$, причём $p_1 < p$ и, следовательно, $p_1 \, | \, (p - 1)!$ Тогда получим, что $(p - 1)! + 1$ не делится на число $p_1$ и, тем более, на $p$. ♦