18. Теорема Вильсона
Дадим теперь одно важное применение доказанного в § 17 следствия. Пусть
простое число и пусть
есть многочлен степени
с целыми коэффициентами. Для
согласно теореме Ферма, мы имеем
откуда
для
мы, очевидно, также имеем
так как для таких
один из сомножителей рассматриваемого произведения равеи нулю. Учитывая, что разность двух чисел, делящихся на
делится на
мы заключаем, что
для
Таким образом, согласно следствию теоремы Лагранжа (для
мы можем заключить, что все коэффициенты нашего многочлена, а значит, и его свободный член делятся на
Но для нечетных
(так как
свободным членом многочлена
является число
или
Следовательно, если
есть простое нечетное число, то
что, впрочем, справедливо и для
так как
Таким образом, доказана
Теорема 14 (Вильсона). Для каждого простого числа
число
делится на
Следует заметить, что если для натурального числа
число
делится на
то
должно быть простым числом. Действительно, если бы
было составным, то в силу того, что
где а и
натуральные числа
число а было бы одним из сомножителей произведения
следовательно, число
при делении на а давало бы в остатке 1, между тем как, делясь на
оно и подавно должно делиться на а. Полученное противоречие доказывает, что число
должно быть простым.
Итак, для того чтобы натуральное число
было простым, необходимо и достаточно, чтобы число
делилось на
Таким образом, теоретически мы можем при помощи только одного деления выяснить, является данное число простым или нет. Однако практически пользоваться этим способом неудобно, так как уже для трехзначных
число
имеет более чем сто цифр.
В связи с теоремой Вильсона возникает вопрос, возможны ли такие простые числа
для которых
делится на
Оказывается, для
имеется три таких числа: 5, 13 и 563. Мы не знаем, существует ли бесконечно много таких чисел
Теоремы Ферма и Вильсона можно соединить в одну следующую теорему:
Если
простое число, то для любого целого числа а число
делится на
В самом деле, если
простое и а — произвольное целое число, то, согласно теореме Ферма, число
а делится на
а так как, согласно теореме Вильсона, число а
делится на
то и сумма этих чисел, т. е. число
также делится на
. С другой стороны, если
делится на
при любом целом а, то при
мы получаем отсюда теорему Вильсона, из которой следует, что при любом целом а
а так как
то
т. е.
а, что дает теорему Ферма.
Легко также доказать, что теоремы Ферма и Вильсона можно соединить и в следующую теорему:
Если
простое число, а — целое число, то число
а делится на
(Лео Мозер).
Из теоремы Вильсона вытекает
Теорема 15 (Лейбница). Для того чтобы натуральное число
было простым, необходимо и достаточно, чтобы число
делилось на
Доказательство. Если число
является простым, то, согласно теореме Вильсона, число
делится на
Учитывая, что
мы имеем
, откуда видно, что число
делится на
С другой стороны, если
то
и поэтому
откуда (напомним, что
как было уже доказано выше, следует, что
должно быть простым числом. Таким образом, теорема Лейбница доказана.
Если
есть простое число
то
ибо тогда
Поэтому число
как число, большее
согласно
теореме Вильсона, делящееся на
является числом составным.
Итак, если
есть простое число, то
есть число составное. Отсюда следует, что существует бесконечное множество натуральных чисел
для которых число
является составным. Существует ли бесконечное множество натуральных
для которых число
является простым, мы не знаем.
Простыми являются числа
следующим простым числом того же вида является
Мы не знаем, является ли простым число
На основании теоремы Лейбница можно легко заключить, что существует бесконечное множество натуральных чисел
для которых число
является составным. Но мы не знаем, существует ли бесконечное множество натуральных
для которых число
является простым (простыми являются числа
. Мы не знаем также, существует ли среди чисел каждого из видов
где
простое число, бесконечное множество составных чисел.
Мы не знаем ответа на вопрос, существует ли бесконечное множество натуральных
для которых число
является простым
естб
простое число), а также на вопрос, существует ли бесконечное множество таких натуральных чисел
для которых число
является составным.
Числа
являются простыми, но числа
для
и 8 являются составными, делящимися соответственно на 59, 19 и 347.
Докажем еще (следуя идее А. Шинцеля), что для натуральных
произведение
всех простых чисел, меньших
будет больше чем
Допустим, что при некотором натуральном
Тогда мы имели бы
Число
не делится ни на одно простое число
(так как такие числа являются делителями
поэтому, учитывая, что
мы заключаем, что число
имеет простой делитель
который должен быть
Но тогда
что приводит