14. Малая теорема Ферма

Теорема 9. Если простое число, то для каждого целого числа а число а делится на

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

натурального числа а. Согласно формуле Ньютона для двучлена, имеем

где для

причем, как известно, числа являются целыми. Отсюда мы заключаем, что число делится на следовательно, согласно следствию теоремы 7, по крайней мере одно чисел должно делиться на Но так как то ни одно из чисел не делится на следовательно, на должно делиться Отсюда, учитывая (1), мы заключаем, что число делится на Прибавив к нему число а, делящееся на (так как мы предполагаем, что теорема справедлива для числа а), мы обнаружим, что число делятся на т. е. что теорема справедлива для числа а

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

Если а — целое отрицательное число, то при имеем , и так как из двух последовательных целых чисел и а одно всегда четное, то всегда Далее, при простом нечетном имеем и поэтому . Следовательно теорема справедлива и для целых отрицательных чисел а. Таким образом, теорема 9 доказана полностью.

В качестве частного случая теоремы 9, для мы получаем теорему, согласно которой для любого простого числа число делится на Возникает

вопрос, будет ли верна обратная теорема, т. е. если натуральное число такое, что то должно ли быть простым числом?

Для многих предполагаемых теорем, относящихся к простым числам, производилась проверка на большом числе частных случаев. Если бы мы проверили, например, все последовательные натуральные числа и

300, то обнаружили бы, что каждое такое натуральное число для которого делится на , является простым числом. Быть может, именно этот путь привел китайцев 25 веков назад к теореме, согласно которой, еслн для натурального числа число делится на , то число простое. Однако эта теорема оказалась ложной, ибо число , как мы сейчас покажем, делится на 341, а число является составным.

В том, что число делится на 341, мы можем убедиться следующим образом. Очевидно, Число делится на 341. Значит, и число также делится на 341 (так как для натуральных и число как известно, делится на Числа делятся на 341, откуда следует, что и число делится на 341. Отсюда, в силу нашего равенства для числа , тотчас же получаем, что это число делится на 341, что и требовалось доказать.

Естественно, возникает вопрос, существует ли бесконечно много натуральных чисел , для которых китайская теорема неверна. Чтобы доказать, что ответ на этот вопрос является утвердительным, достаточно (имея в виду, что составное нечетное число 341 не удовлетворяет теореме) доказать, что для каждого составного нечетного числа , не удовлетворяющего указанной теореме, существует составное нечетное число, большее а также не удовлетворяющее ей.

Итак, предположим, что нечетное составное число где а и натуральные числа не удовлетворяет китайской теореме и, значит, Число есть нечетное составное, так как оно делится на число большее 1 (ибо и меньшее чем причем Таким образом, достаточно еще только

показать, что Мы имеем но есть нечетное число, следовательно, где натуральное число. Отсюда

Число таким образом, делится на число Следовательно, и число делится на значит, составное число не удовлетворяет китайской теореме, что и требовалось доказать.

Возникает также вопрос, существуют ли составные четные числа, не удовлетворяющие китайской теореме. Только в 1960 г. Д. X. Лемер нашел такое число: Нахождение этого числа было очень сложным делом, проверить же, что оно является делителем числа нетрудно. Легко проверить, что откуда следует, что число делится на а значит, также на 73 и 1103. Таким образом, число делится на 2, 73 и 1103, а так как эти числа являются разными простыми числами, то делится на их произведение, т. е. на число что и требовалось доказать.

В 1951 г. Н. Г. В. X. Биджер доказал, что существует бесконечно много четных чисел , для которых число делится на .

Доказано также, что существует бесконечно много пар разных простых чисел таких, что число делится на . В 1958 г. А. Шинцель доказал, что для любого целого числа а и любого натурального существуют разные простые числа такие, что .

В связи с ложностью китайской теоремы напрашивается вопрос, существуют ли составные числа такие, что для каждого целого а число делится на Такие составные числа мы называем абсолютно псевдопростыми. Высказано предположение (до сих пор не доказанное), что таких чисел имеется бесконечно много. Наименьшее из них есть число

Чтобы доказать, что число 561 есть абсолютно псевдопростое, достаточно доказать, что для всех целых а

число а делится на каждое из простых чисел 3, 11, 17.

Число а, очевидно, делится на 3, если а делится на 3. Если же а не делится на 3, то а есть число вида откуда следовательно, отсюда а значит, и а.

Число а, очевидно, делится на 11, если число а делится на 11. Согласно теореме Ферма, для всех целых а имеем так что если число а не делится на И, то отсюда вытекает, что и, следовательно, откуда уже заключаем, что

Число делится на 17, если число а делится на 17. Согласно теореме Ферма, для всех целых а имеем . Поэтому если число а не делится на 17, то отсюда вытекает, что откуда и, значит, (ибо Итак, мы доказали, что число 561 является абсолютно псевдопростым.

Числами абсолютно псевдопростыми являются также

известно и много других таких чисел.

Из малой теоремы Ферма вытекает, что если простое число то число делится на Возникает вопрос, существуют ли простыв числа для которых делится на Мы знаем только два таких простых числа именно 1093 и 3511, и знаем, что нет других таких простых чисел ; но мы не знаем, существуют ли такие числа, превосходящие 100 000, и конечно ли их количество. Мы не знаем также, существует ли бесконечно много простых чисел таких, для которых число не делится на

Из теоремы Ферма легко вытекает, что если простое число, то число делится на p. Г. Джуга высказал в 1950 г. предположение, что эта делимость имеет место только для простых чисел, и проверил его для всех чисел