4.8 ДОПОЛНИТЕЛЬНЫЕ ПРИМЕРЫ

За нами тянется долг из гл. 3: мы обещали доказать, что чисел

состоят в точности из наборов чисел

взятых в некотором порядке, где Например, если то и эти числа суть 0, 8, 4, 0, 8, 4, 0, 8, 4, 0, 8, 4.

Первая часть доказательства — показать, что мы получаем наборов первых величин, — теперь уже тривиальна. Согласно (4.38),

откуда мы получаем наборов чисел, полученных при

Теперь нужно показать, что эти чисел суть взятые в некотором порядке. Положим . Тогда по распределительному закону (3.23), так что величины, которые получаются при -это взятые по раз числа

Но на основании (4.27) известно, что — они уже поделены на их Поэтому нужно рассмотреть лишь случай а именно тот случай, когда тип взаимно просты.

Итак, допустим, что Нетрудно заметить, что в этом случае числа (4.45) — это не что иное, как расположенные в некотором порядке числа если воспользоваться „принципом голубиных гнезд" Сей принцип утверждает, что если голубей рассаживаются по гнездам, то одно из гнезд окажется пустым тогда и только тогда, когда в каком-нибудь другом гнезде будет сидеть более одного голубя. (Это аналогично "принципу ящиков Дирихле", доказанному в упр. 3.8.) Известно, что числа (4.45) различны, поскольку

если (это свойство Следовательно, все гнезда с номерами должны заполниться различными числами и доказательство завершено. Тем самым наш долг из гл. 3 погашен.

Доказательство-то завершено, но если не полагаться на косвенную „птичью" аргументацию, а воспользоваться прямым методом, то можно доказать даже большее. Если и если задано

значение то можно явно вычислить число к такое, что разрешив сравнение

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

откуда

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

для всех целых положительных чисел с и если (Разумеется, уравнения имеют уйму решений.) В конце концов этот вопрос был разрешен Эндрю Уайлсом: его эпохальное доказательство формулы (4.46) опубликовано в Annals of Mathematics 141 (1995), с. 443-551.

Теорему Ферма 1640 г. гораздо легче проверить. Теперь она называется малой теоремой Ферма (или, для краткости, просто теоремой Ферма) и утверждает, что

Доказательство. Как обычно, допустим, что обозначает простое число. Нам известно, что чисел суть числа , взятые в некотором порядке. Поэтому если их перемножить, то получим

где сравнимость понимается по модулю р. Это означает, что

и можно сократить на множитель поскольку он не делится на

Иногда более удобна другая формулировка теоремы Ферма:

Данное сравнение имеет место при любом целом Доказать это легко: если , то просто умножаем (4.47) на если же нет, то так что

В том же году, когда им была открыта теорема (4.47), Ферма в письме к Мерсенну высказывает свое предположение о том, что число

должно быть простым при всех Он знал, что первые пять случаев давали простые числа:

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

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

А это соотношение можно проверить вручную, начиная с 3 и возводя в квадрат 32 раза, сохраняя лишь остатки по . Вначале мы получаем затем потом до тех пор, пока не доберемся до

В результате не получается 1, так что не является простым числом. Подобный метод опровержения не дает никакого ключа к разгадке того, каковы могут быть сомножители, — он только доказывает, что сомножители существуют. (В данном случае они равны 641 и 6700417, что было впервые обнаружено Эйлером в

Если бы число оказалось равным 1 по модулю , то данное вычисление не доказывало бы, что число простое, — оно всего лишь не опровергало бы это. Однако в упр. 47 обсуждается обращение теоремы Ферма, с помощью которого можно доказать, что большие простые числа — действительно простые, не прибегая к изнурительным арифметическим выкладкам.

Мы доказали теорему Ферма, сократив обе части уравнения на Оказывается, что величина всегда сравнима по модулю — это следствие одного классического факта, известного под названием теоремы Вильсона:

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

Другая половина теоремы Вильсона утверждает, что ). Эту половину можно доказать, объединяя попарно числа и обратные к ним по . Если , то известно, что существует такое, что

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

Теперь предположим, что каждое число между 1 и образует пару со своим обратным. Поскольку произведение некоторого числа и обратного к нему сравнима с 1, то произведение всех обратных чисел во всех парах также сравнима с 1; по-видимому, и величина будет сравнима с 1. Проверим это, скажем, при Получаем но это число сравнимо с 4, а не с 1 по модулю 5. О-ля-ля! Где же мы ошиблись? Давайтека посмотрим повнимательнее, что собой представляют обратные числа:

вот в чем дело: 2 и 3 образуют пару, а 1 и 4 нет — они являются обратными к самим себе.

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

что и требовалось.

К сожалению, мы не умеем эффективно вычислять факториалы, так что в качестве практического инструмента проверки на простоту теорема Вильсона бесполезна. Это только теорема.