§ 6.3. Теорема Ферма

Теорему, которую мы хотим доказать, иногда ласково называют «малой теоремой Ферма». Она говорит, что если простое число и — любое целое, то делит . Частный случай этой теоремы известен многие сотни лет, но Ферма,

кажется, был первым, кто доказал теорему в полной общности. Начнем с перевода формулировки теоремы на язык сравнение.

Теорема Ферма. Пусть положительное простое число и а — целое; тогда

Чтобы доказать теорему с помощью математической индукции, нам нужно найти утверждение к которому можно применить метод. Вот оно:

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

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

Лемма. Пусть положительное простое число, целые; тогда

Доказательство леммы. Как следует из формулы бинома Ньютона,

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

А это, в свою очередь, будет немедленно следовать из делимости биномиальных коэффициентов на при По определению,

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

Теперь можно вернуться к доказательству теоремы Ферма. Предположение индукции:

В качестве индуктивного перехода нам нужно показать, что По лемме

По предположению индукции, пр можно заменить на Проделав это, мы получаем: что мы и хотели показать.

Наиболее интересных приложений теоремы Ферма придется подождать до следующей главы. А сейчас будем довольствоваться использованием теоремы для упрощения вычислений степеней по модулю проблемы, с которой мы уже сталкивались. Сначала переформулируем теорему в более удобной форме.

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

Но и окончательно Именно этот вариант уравнения из теоремы Ферма мы будем использовать в дальнейшем чаще всего. Для будущих ссылок сформулируем его в виде утверждения.

Теорема Ферма. Пусть положительное простое число и а — целое, не делящееся на тогда

Задача, к которой мы хотели бы применить теорему Ферма, звучит следующим образом. Для трех данных натуральных чисел , к таких, что найти вычет по модулю

Если делит а, то вычет равен 0. Поэтому без ограничения общности можно предполагать, что не делит а. Разделим к на с остатком: где неотрицательные целые числа, причем Следовательно,

По теореме Ферма Значит, и достаточно делать вычисления только для экспонент, показатель которых меньше

Приведем наглядный пример, демонстрирующий силу этой простой редукции. Допустим, нам нужно найти вычет числа 25432675 по модулю 13. Рецепт предыдущей главы предписывал вычислить несколько степеней двойки по модулю 13, прежде чем что-нибудь получить. Посмотрим, что будет, если применить теорему Ферма. Сначала найдем остаток от деления 5432 675 на Он равен 11. Затем, рассуждая, как в предыдущих абзацах, мы имеем

Непосредственный счет дает окончательный ответ: