22. Числа Ферма

Числами Ферма называются числа вида где Знаменитый математик XVII века П. Ферма предполагал, что все такие числа являются простыми. Это справедливо для , но Л. Эйлер в 1732 г. обнаружил, что число

имеющее 10 цифр, является составным: оно делится на 641. В настоящее время мы знаем уже 37 составных чисел именно для .

Среди этих 37 составных чисел имеются такие, для которых нам известны их разложения на простые сомножители (Например, ), имеются такие, для которых мы не знаем этих разложений, но знаем разложения в произведения двух целых чисел > 1 (например, ), наконец, имеются и такие, для которых мы не знаем ни одного разложения в произведение двух целых чисел хотя и знаем, что такое разложение существует

Начнем с наибольшего из известных составных чисел Ферма, т. е. с числа Оно имеет более чем 10582 цифр, и поэтому все их невозможно выписать. Однако, как уже было сказано ранее (§ 8), мы знаем наименьший простой делитель этого числа: Напрашиваются здесь два вопроса: 1) как найден этот делитель и 2) как можно убедиться, что число имеющее 587 цифр, является делителем числа все цифры которого невозможно выписать.

Мы здесь, очевидно, не будем ни производить деления числа на число ни находить частное от этого деления. Совершенно иным путем мы убедимся, или, скорее всего, выясним, как можно убедиться в том, что число при делении на дает в остатке нуль.

Обозначим для целого числа через остаток от деления на Из определения числа следует, что для каждого целого числа будет Определим теперь последовательность посредством условий

Докажем при помощи индукции, что

Формула (2), очевидно, справедлива для так как Предположим, что она справедлива для некоторого натурального числа . В таком случае, согласно (2), и подавно . Учитывая же, что для имеем затем находим Следовательно, согласно Итак, формула (2) доказана посредством индукции. Для имеем

откуда следует, что число при делении на дает такой же остаток, как и число Поэтому, чтобы исследовать, делится ли число на достаточно исследовать, делится ли на число Осмыслим теперь, какие действия нужно будет выполнить, чтобы подсчитать число Из формул следует, что числа как остатки от деления на все будут меньше так что каждое из них имеет не более чем 587 цифр. Таким образом, из формул (1) вытекает, что для вычисления числа необходимо осуществить 1944 возвышений в квадрат чисел, имеющих не более чем 58? цифр, и столько же делений этих квадратов (следовательно, чисел, имеющих не более чем 1175 цифр) на число имеющее 587 цифр. Это — действия, которые современные электронные машины в состоянии выполнить. Таким путем было подтверждено, что число делится на а так как что легко можно проверить, то заключаем, что число является составным.

Перейдем теперь к вопросу, как можно найти простой делитель числа Известна теорема, согласно которой каждый натуральный делитель числа должен иметь вид где целое неотрицательное число. Для отсюда следует, что делителями числа могут быть только числа, принадлежащие арифметической прогрессии где Для мы получаем тривиальный делитель 1. Для число не является простым, так как, очевидно, делится на 3. Для число делится на следовательно, не является простым. Для число является составным, делящимся на 5. В самом деле, откуда Умножив правую часть последней формулы на 233, найдем, что откуда также Для число делится на 3, следовательно, является составным.

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

Подобным образом можно исследовать другие числа Ферма. Исследование десятизначного числа относительно которого Ферма был убежден, что оно является простым, выполняется весьма просто. Делители числа как мы знаем, должны быть вида или Для мы получаем число 129, делящееся на 3, и следовательно, составное; для получаем простое число 257, которое не является делителем числа в чем легко можно убедиться непосредственным делением. Для мы получаем число 385, делящееся на 5 и, стало быть, составное. Для получаем число делящееся на 3 и, следовательно, также составное. (Иначе, число при делении и на 3, и на 5 дает в остатке 1, а значит, число дает в остатке 2, т. е. число не делится ни на 3, ни на 5 и поэтому не делится также ни на одно из чисел 129, 385 и 513.) Для получаем простое число 641, относительно которого непосредственным делением легко Можно убедиться, что оно является делителем числа Таким образом, только при помощи двух делений мы убеждаемся, что 641 является наименьшим простым делителем числа

Разделив число на 641, мы получим в частном 6700417. Делители этого числа, будучи делителями числа должны быть вида Если это число составное, то оно имеет простой делитель, не больший, чем корень квадратный из него, и, значит, . Таким образом, для мы имеем здесь неравенство , откуда , а с другой стороны, мы знаем, что должно быть ибо наименьшим простым делителем числа является 641. Таким путем при помощи немногих делений подтверждено, что число 6 700417 является простым, и, следовательно, получено разложение числа в произведение двух различных простых сомножителей.

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

Разыскать простой делитель числа среди чисел арифметической прогрессии практически возможно только в том случае, если число обладает не слишком большим простым делителем. В противном случае, подставляя вместо даже очень много последовательных натуральных чисел, мы не натолкнемся на

такой делитель. Это имеет место, например, для чисел из которых первое содержит 39, а второе 78 цифр. Мы не знаем ни одного простого делителя этих чисел, а также ни одного разложения их в произведения двух натуральных чисел, больших единицы. Однако Дж. К. Морхед в 1905 г. доказал, что число является составным, а в 1909 г. он же и А. Е. Вестерн доказали, что число также является составным. Доказательство основывалось на следующей теореме.

Теорема 21. Если число является простым, то число делится на

Докажем вначале следующее предложение.

Лемма. Если есть целое неотрицательное число и если число является простым, то число делится на

Доказательство. Лемма, очевидно, справедлива для поэтому далее мы можем считать, что к является числом натуральным. Пусть Возьмем произведение первых натуральных чисел, делящихся на 3, и разобьем сомножители этого произведения на три группы, отнеся к первой группе первые 2 сомножителей, ко второй — следующие сомножителей и к третьей — остальные сомножителей.

Сомножители первой группы дают произведение

Сомножители второй группы, если записать их в порядке убывания, дают произведение

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

Так как число сомножителей здесь нечетное , то последнее произведение после развертывания и объединения слагаемых, делящихся на даст нам число где и есть некоторое целое число.

Сомножители третьей группы дают произведение

где натуральное число.

Таким образом, имеем где целое число.

Но Отсюда мы заключаем, что число делится на следовательно, где есть целое число. Но и Поэтому число не делится на Поскольку же произведение делится на то должно делиться на откуда где есть целое число. Таким образом, имеем откуда следует, что число делится на что и требовалось доказать.

Перейдем теперь к доказательству теоремы 21.

Доказательство. Пусть есть некоторое натуральное число. Тогда имеем где натуральное число, откуда следует, что число делится на 4. С другой стороны, имеем натуральное число. Отсюда , так что число делясь на 4, оказывается делящимся и на 3, следовательно, это число делится на 12, и поэтому где целое число. Таким образом, согласно нашей лемме, если число простое, то число делится на

Итак, теорема 21 доказана. Заметим попутно (хотя далее это нам и не понадобится), что можно доказать и теорему, обратную теореме 21.

Воспользуемся теперь теоремой 21 для доказательства того, что число является составным. Для этой цели достаточно показать, что число не делится на число .

Значит, достаточно вычислить остаток от деления числа на Число столь велико, Что мы не можем выписать все его цифры, однако, чтобы подсчитать остаток, который оно дает при делении на можно поступить следующим образом. Число имеет 61 цифру, следовательно, его мы можем написать и подсчитать остаток который получается при делении этого числа на (теперь это уже нетрудно сделать, если прибегнуть к помощи электронной вычислительной машины, но для Морхеда в 1905 г. это было очень трудно, хотя

и возможно). Остаток от деления числа на число есть, очевидно, остаток от деления числа на число Подобным же образом остаток от деления числа на число есть остаток от деления числа на Продолжая этот процесс далее, дойдем до остатка от деления числа на Таким путем найдем, что откуда следует, что число не делится на значит, согласно теореме 21, число не является простым.

Аналогичным образом убеждаемся, и число не является простым. Для каждого же из чисел , которые являются составными, мы знаем их простые делители, Именно:

На основании теоремы 21, при помощи электронных вычислительных машин доказано, что имеющее 2467 цифр, и имеющее 4933 цифры, являются числами составными. Никаких простых делителей этих чисел мы не знаем.

Доказано, что числа также составные, причем найдены их простые делителя:

Число имеет более 30 тысяч цифр. Существующие же в настоящее время вычислительные машины не в состоянии выполнять десятки тысяч делений чисел, имеющих несколько десятков тысяч цифр, на числа, имеющие более 30 тысяч цифр. Таким образом, мы, пока все еще лишены возможности применить теорему 21 к исследованию чисел

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

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

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