Главная Перейти к главной странице
Введение I. Теория чисел Теорема Вильсона Две теоремы Ферма Распределение простых чисел Неравенства Чебышева II. Анализ III. Модели IV. Задачи
Обозначения Литература

ТЕОРЕМА ВИЛЬСОНА

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


J.L.Lagrange
Рис. 1. Ж. Л. Лагранж (1736–1813)

Теорема 1.1. (Вильсон) Если p — простое, то выполняется сравнение (p − 1)! + 1 ≡ 0   (mod p),

а если p — составное, то соотношение (1) не выполняется.

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

Лемма 1.1. Если НОД(a, b) = 1, то существуют целые u, v, такие, что au + bv = 1.

Доказательство. Очевидно, достаточно доказать утверждение для случая, когда a, b — натуральные числа. Нетривиальной частью доказательства является идея индукции по сумме a + b. При a + b = 2 имеем a = b = 1 и (2) выполняется с u = 1, v = 0. Пусть теорема верна для всех a, b, таких что НОД(a,b) = 1, a + b < k, где k > 2. Тогда, так как a + b > 2, НОД(a,b) = 1, то a ≠ b. Не теряя общности можно считать, что a > b. Поскольку НОД(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, получим (2).

Следствие 1.1. Если a > 1, b > 1, НОД(a, b) = 1, то для каждого k = 0, 1, ... существуют единственные целые числа u, v, такие, что выполняется au − bv = 1,   kb + 1 < u < (k + 1)b,   k = 0, 1, ...

Доказательство. Существование u, v следует из леммы 1.1. Докажем единственность. Предположим, от противного, что имеются такие числа u', v', для которых u'≠ u, v' ≠ v с условием kb + 1 < u' < (k + 1)b и au' − bv' = 1.

Вычитая из (3) почленно (4) получим a(u − u') = b(v − v'). Так как НОД(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 утверждение теоремы не трудно проверить непосредственным вычислением). Докажем, что все числа 2, 3, ... , p − 2

распадаются на пары** чисел, произведение которых даёт при делении на p остаток 1. Пусть q пробегает ряд (5), тогда по следствию из леммы 1.1 найдутся единственные целые u, v, такие что qu − pv = 1,     1 < u < p Следовательно, множество чисел (5) можно разбить на такие пары (qi; qi), i = 1, 2, ... , (p − 3)/2, для которых qiqi = pvi + 1,     i = 1, 2, ... , (p − 3)/2. Перемножая (6) по всевозможным значениям i получим (p − 2)! = pV + 1, где V — некоторое натуральное число. После умножения обеих частей последнего равенства на p − 1 имеем (p − 1)! = p(p − 1)V + p − 1, или (p − 1)! + 1 = p((p − 1)V + 1), то есть, фактически, соотношение (1).

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



* Например, уже для проверки простоты 101 придётся иметь дело вот с таким числом 100! = 9332621544394415268169923885626670049071596826438162
146859296389521759999322991560894146397615651828625369792
0827223758251185210916864000000000000000000000000.

** Здесь существенно, что p — простое число. При составном p такое разбиение на пары невозможно. Например, возьмём простое p = 11. Тогда ряд чисел (5) 2, 3, 4, 5, 6, 7, 8, 9 распадается на пары (2, 6), (3, 4), (5, 9), (7, 8). А при составном p = 9 среди чисел 2, 3, 4, 5, 6, 7 обнаруживается, что уже для 3 нет пары.