Доказательства маленькой теоремы Фермаца - Википедия - Proofs of Fermats little theorem

В этой статье собраны различные доказательства из Маленькая теорема Ферма, в котором говорится, что

для каждого простое число п и каждый целое число а (видеть модульная арифметика ).

Упрощения

Несколько из доказательства малой теоремы Ферма приведенные ниже зависят от двух упрощений.

Во-первых, мы можем предположить, что а находится в диапазоне 0 ≤ ап − 1. Это простое следствие законов модульная арифметика; мы просто говорим, что мы можем сначала уменьшить а по модулюп. Это соответствует сокращению по модулюп, как можно проверить.

Во-вторых, достаточно доказать, что

за а В диапазоне 1 ≤ ап − 1. В самом деле, если предыдущее утверждение верно для таких а, умножая обе части на а дает исходную форму теоремы,

С другой стороны, если а = 0, теорема выполняется тривиально.

Комбинаторные доказательства

Доказательство подсчетом ожерелий

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

Приведенное здесь доказательство является адаптацией Голомб доказательство.[1]

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

Например, если п = 5 и а = 2, то мы можем использовать алфавит с двумя символами (скажем, А и B), и здесь 25 = 32 струны длиной 5:

AAAAA, AAAAB, AAABA, AAABB, AABAA, AABAB, AABBA, AABBB,
ABAAA, ABAAB, АБАБА, ABABB, ABBAA, ABBAB, ABBBA, ABBBB,
BAAAA, BAAAB, БААБА, BAABB, БАБАА, БАБАБ, БАББА, BABBB,
BBAAA, BBAAB, BBABA, BBABB, BBBAA, BBBAB, BBBBA, BBBBB.

Ниже мы будем утверждать, что если мы удалим из списка строки, состоящие из одного символа (в нашем примере, AAAAA и BBBBB), остальные апа строки могут быть организованы в группы, каждая группа содержит ровно п струны. Следует, что апа делится нап.

Украшения на шею

Ожерелье, представляющее семь разных струн (ABCBAAC, BCBAACA, CBAACAB, BAACABC, AACABCB, ACABCBA, CABCBAA)
Ожерелье, представляющее только одну струну (AAAAAAA)

Давайте думать о каждой такой строке как о представлении ожерелье. То есть мы соединяем два конца нити вместе и рассматриваем две нити как одно и то же ожерелье, если можем. вращать одна строка для получения второй строки; в этом случае мы скажем, что две строки друзья. В нашем примере все следующие строки являются друзьями:

AAAAB, AAABA, AABAA, ABAAA, BAAAA.

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

AAABB, AABBA, ABBAA, BBAAA, BAAAB,
AABAB, АБАБА, БАБАА, ABAAB, БААБА,
AABBB, ABBBA, BBBAA, BBAAB, BAABB,
ABABB, БАББА, ABBAB, BBABA, БАБАБ,
ABBBB, BBBBA, BBBAB, BBABB, BABBB,
BAAAA, AAAAB, AAABA, AABAA, ABAAA,
AAAAA,
BBBBB.

Обратите внимание, что в приведенном выше списке каждое ожерелье с более чем одним символом представлено 5 разными строками, а количество ожерелий, представленных только одной строкой, равно 2, то есть является количеством различных символов. Таким образом, список очень ясно показывает, почему 32 − 2 делится на 5.

Можно использовать следующее правило, чтобы определить, сколько друзей в данной строке S имеет:

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

Например, предположим, что мы начинаем со строки S = ABBABBABBABB, который состоит из нескольких копий более короткой строки Т = ABB. Если мы будем вращать его по одному символу за раз, мы получим следующие 3 строки:

ABBABBABBABB,
BBABBABBABBA,
BABBABBABBAB.

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

Завершение доказательства

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

  • Некоторые строки содержат п идентичные символы. Есть ровно а из них по одному на каждый символ в алфавите. (В нашем текущем примере это строки AAAAA и BBBBB.)
  • В остальных строках используются как минимум два различных символа алфавита. Если мы сможем расстаться S в повторяющиеся копии некоторой строки Т, длина Т должен разделить длину S. Но, поскольку длина S это премьер п, единственная возможная длина для Т это также п. Следовательно, приведенное выше правило говорит нам, что S точно п друзья (в том числе S сам).

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

Доказательство с использованием динамических систем

В этом доказательстве используются некоторые основные концепции из динамические системы.[2]

Начнем с рассмотрения семьи функции Тп(Икс), куда п ≥ 2 - это целое число, отображая интервал [0, 1] себе по формуле

куда {у} обозначает дробная часть из у. Например, функция Т3(Икс) показано ниже:

Пример функции Tn

Число Икс0 считается фиксированная точка функции ж(Икс) если ж(Икс0) = Икс0; другими словами, если ж листья Икс0 фиксированный. Неподвижные точки функции можно легко найти графически: это просто Икс координаты точек, где график из ж(Икс) пересекает график прямой у = Икс. Например, неподвижные точки функции Т3(Икс) равны 0, 1/2 и 1; они отмечены черными кружками на следующей схеме:

Неподвижные точки функции Tn

Нам потребуются следующие две леммы.

Лемма 1. Для любого п ≥ 2 функция Тп(Икс) имеет ровно п фиксированные точки.

Доказательство. На иллюстрации выше есть 3 фиксированные точки, и те же геометрические аргументы применимы для любого п ≥ 2.

Лемма 2. Для любых положительных целых чисел п и м, и любой 0 ≤ x ≤ 1,

Другими словами, Тмин(Икс) это сочинение из Тп(Икс) и Тм(Икс).

Доказательство. Доказательство этой леммы несложно, но нужно быть осторожнее с концом Икс = 1. В этом случае лемма, очевидно, верна, поскольку

Итак, допустим, что 0 ≤ Икс <1. В этом случае

так Тм(Тп(Икс)) дан кем-то

Поэтому нам действительно нужно показать, что

Для этого заметим, что {nx} = nxk, куда k это целая часть из nx; тогда

поскольку мк целое число.

Теперь приступим к доказательству малой теоремы Ферма с изучения функции Тап(Икс). Будем считать, что а ≥ 2. Из леммы 1 мы знаем, что он имеет ап фиксированные точки. По лемме 2 мы знаем, что

так что любая неподвижная точка Та(Икс) автоматически является фиксированной точкой Тап(Икс).

Нас интересуют неподвижные точки Тап(Икс) которые нет фиксированные точки Та(Икс). Назовем множество таких точек S. Есть апа указывает в S, поскольку снова по лемме 1 Та(Икс) имеет ровно а фиксированные точки. Следующая диаграмма иллюстрирует ситуацию для а = 3 и п = 2. Черные кружки - точки S, из них 32 − 3 = 6.

Неподвижные точки в множестве S

Основная идея доказательства теперь состоит в том, чтобы разбить множество S в его орбиты под Та. Это означает, что мы выбираем точку Икс0 в S, и повторно применять Та(x) к нему, чтобы получить последовательность точек

Эта последовательность называется орбитой Икс0 под Та. По лемме 2 эту последовательность можно переписать в виде

Поскольку мы предполагаем, что Икс0 неподвижная точка Та п(Икс), после п шаги, которые мы ударили Тап(Икс0) = Икс0, и с этого момента последовательность повторяется.

Однако последовательность не можешь начать повторяться раньше этого. Если бы это было так, длина повторяющегося раздела должна была бы быть делителем п, поэтому он должен быть 1 (поскольку п простое). Но это противоречит нашему предположению, что Икс0 не является фиксированной точкой Та.

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

(Это доказательство по сути такое же, как и доказательство подсчета ожерелий приведенный выше, просто просмотренный через другую линзу: можно представить интервал [0, 1] как заданный последовательностями цифр в базе а (наше различие между 0 и 1 соответствует знакомому различию между представлением целых чисел как оканчивающихся на «.0000 ...» и «.9999 ...»). Тап сводится к сдвигу такой последовательности на п много цифр. Неподвижными точками этого будут последовательности, которые являются циклическими с периодом деления п. В частности, неподвижные точки Тап можно рассматривать как ожерелья длины п, с Тап соответствующее вращению таких ожерелий на п пятна.

Это доказательство также может быть представлено без различия между 0 и 1, просто используя полуинтервал [0, 1); тогда Тп будет только п - 1 фиксированная точка, но ТапТа все равно будет работать апа, по мере необходимости.)

Полиномиальные доказательства

Доказательство с помощью биномиальной теоремы

Это доказательство, благодаря Эйлер,[3] использует индукция чтобы доказать теорему для всех целых чисел а ≥ 0.

Базовый шаг, который 0п ≡ 0 (модп), тривиально. Далее мы должны показать, что если теорема верна для а = k, то это верно и для а = k + 1. Для этого индуктивного шага нам понадобится следующая лемма.

Лемма. Для любых целых чисел Икс и у и для любого прайма п, (Икс + у)п ≡ Иксп + уп (модп).

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

Доказательство. Предполагать kпk (мод п), и рассмотрим (k+1)п. По лемме имеем

Используя предположение индукции, имеем kпk (мод п); и, очевидно, 1п = 1. Таким образом

что является формулировкой теоремы для а = k+1. ∎

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

где коэффициенты - это биномиальные коэффициенты,

описан с точки зрения факториал функция п! = 1×2×3×⋯×п.

Доказательство леммы. Мы рассматриваем биномиальный коэффициент, когда показатель является простым п:

Все биномиальные коэффициенты - целые числа. В числителе стоит множитель п по определению факториала. Когда 0 < я < п, ни одно из членов в знаменателе не включает множитель п (полагаясь на примитивность п), оставляя сам коэффициент иметь простой множитель п из числителя, подразумевая, что

По модулю п, это исключает все, кроме первого и последнего членов суммы в правой части биномиальной теоремы для простых чисел. п. ∎

Первобытность п является существенным для леммы; в противном случае у нас есть такие примеры, как

который не делится на 4.

Доказательство с использованием полиномиального разложения

Доказательство, впервые обнаруженное Лейбниц (кто не публиковал)[4] а позже заново открыл Эйлер,[3] это очень простое приложение полиномиальная теорема который приведен здесь для простоты.

Суммирование ведется по всем последовательностям целочисленных неотрицательных индексов. k1 через kм такая сумма всех kя является п.

Таким образом, если мы выразим а как сумму единиц (единиц), получаем

Очевидно, что если п простое, и если kj не равно п для любого j, у нас есть

и

если kj равно п для некоторых j.

Поскольку есть ровно а такие элементы, что kj = п, следует теорема.

(Это доказательство является, по сути, более грубым вариантом доказательство подсчета ожерелий данные ранее; полиномиальные коэффициенты подсчитывают количество способов, которыми строка может быть переставлена ​​в произвольные анаграммы, в то время как аргумент ожерелья подсчитывает количество способов, которыми строка может быть повернута в циклические анаграммы. То есть здесь нетривиальные полиномиальные коэффициенты делятся на п можно рассматривать как следствие того, что каждое нетривиальное колье длины п можно развернуть в строку в п много способов.

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

Доказательство с использованием расширений Power Product

Аддитивно-комбинаторное доказательство, основанное на разложении формального степенного произведения, было дано Гедрюсом Алкаускасом.[5] Это доказательство не использует ни Евклидов алгоритм ни биномиальная теорема, а скорее использует формальный степенной ряд с рациональными коэффициентами.

Доказательство как частный случай теоремы Эйлера

Это доказательство,[3][6] обнаружен Джеймс Айвори[7] и заново открыт Дирихле[8] требует некоторого фона в модульная арифметика.

Предположим, что а положительно и не делится на пИдея состоит в том, что если мы запишем последовательность чисел

 

 

 

 

(А)

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

 

 

 

 

(B)

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

Собирая вместе а сроки доходности

Наконец, мы можем «отменить» числа 1, 2, ..., п − 1 с обеих сторон этого уравнения, получая

В приведенном выше доказательстве есть два шага, которые нам нужно обосновать:

  • Почему элементы последовательности (А), приведенная по модулю п, являются перестановкой (B), и
  • Почему допустимо «отменить» в постановке модульной арифметики.

Мы докажем это ниже; сначала давайте посмотрим на пример этого доказательства в действии.

Пример

Если а = 3 и п = 7, то рассматриваемая последовательность

уменьшение по модулю 7 дает

это просто перестановка

Их умножение дает

то есть,

Отмена 1 × 2 × 3 × 4 × 5 × 6 дает

что является малой теоремой Ферма для случая а = 3 ип = 7.

Закон об отмене

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

 

 

 

 

(C)

тогда мы можем «отменить» ты чтобы получить

 

 

 

 

(D)

Наше использование этого закон об отмене в приведенном выше доказательстве малой теоремы Ферма было справедливо, потому что числа 1, 2, ..., п − 1 конечно не делятся на п (действительно, они меньше чем п).

Мы можем легко доказать закон отмены, используя Лемма евклида, который обычно утверждает, что если простое число п делит продукт ab (куда а и б целые числа), то п должен разделить а или же б. Действительно, утверждение (C) просто означает, что п разделяет uxуу = ты(Иксу). С п простое число, не делящее ты, Лемма Евклида говорит нам, что она должна делить Икс − у вместо; то есть, (D) имеет место.

Обратите внимание, что условия, при которых выполняется закон сокращения, достаточно строгие, и это объясняет, почему маленькая теорема Ферма требует, чтобы п это простое число. Например, 2 × 2 ≡ 2 × 5 (мод 6), но это неправда, что 2 ≡ 5 (мод. 6). Однако имеет место следующее обобщение закона отмены: если ты, Икс, у, и z целые числа, если ты и z находятся относительно простой, и если

тогда мы можем «отменить» ты чтобы получить

Это следует из обобщение леммы Евклида.

Свойство перестановки

Наконец, мы должны объяснить, почему последовательность

при уменьшении по модулю п, становится перестановкой последовательности

Начнем с того, что ни одно из условий а, 2а, ..., (п − 1)а может быть сравнимо с нулем по модулю п, поскольку если k это одно из чисел 1, 2, ..., п − 1, тогда k относительно прост с п, и так а, так Лемма евклида говорит нам, что ка не имеет ничего общего с п. Поэтому, по крайней мере, мы знаем, что числа а, 2а, ..., (п − 1)а, при приведении по модулю п, должен быть найден среди чисел 1, 2, 3, ..., п − 1.

Кроме того, числа а, 2а, ..., (п − 1)а все должно быть отчетливый после уменьшения их по модулю п, потому что, если

куда k и м являются одним из 1, 2, ..., п − 1, то закон отмены говорит нам, что

Поскольку оба k и м находятся между 1 и п − 1, они должны быть равны. Следовательно, условия а, 2а, ..., (п − 1)а при уменьшении по модулю п должно быть отличным. Подведем итог: когда мы уменьшаем п − 1 числа а, 2а, ..., (п − 1)а по модулю п, мы получаем различные члены последовательности 12, ..., п − 1. Поскольку есть ровно п − 1 из них единственная возможность состоит в том, что первые представляют собой перегруппировку вторых.

Приложения к теореме Эйлера

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

Например, если м = 10, то числа меньшем и совмещать с м находятся 1, 3, 7, и 9. Таким образом, мы имеем:

Следовательно,

Доказательство как следствие критерия Эйлера

Доказательства с использованием теории групп

Стандартное доказательство

Это доказательство[9] требует самых основных элементов теория групп.

Идея состоит в том, чтобы признать, что набор грамм = {1, 2, …, п − 1}, с операцией умножения (взятой по модулю п), образует группа. Единственная групповая аксиома, которую необходимо проверить, - это то, что каждый элемент грамм обратимо. Принимая это на веру, допустим, что а находится в диапазоне 1 ≤ ап − 1, то есть, а является элементом грамм. Позволять k быть порядок из а, то есть, k наименьшее натуральное число такое, что аk ≡ 1 (модп). Тогда числа 1, а, а2, ..., аk −1 приведенный по модулюп сформировать подгруппа изграмм чей порядок являетсяk и, следовательно, по Теорема Лагранжа, k делит порядок грамм, который п − 1. Так п − 1 = км для некоторого положительного целого числа м а потом

Чтобы доказать, что каждый элемент б из грамм обратима, можно поступить следующим образом. Первый, б является совмещать к п. Таким образом Личность Безу уверяет нас, что есть целые числа Икс и у такой, что bx + ру = 1. Читая это равенство по модулю п, Мы видим, что Икс является обратным для б, поскольку bx ≡ 1 (модп). Следовательно, каждый элемент грамм обратимо. Итак, как отмечалось ранее, грамм это группа.

Например, когда п = 11, инверсии каждого элемента задаются следующим образом:

а12345678910
а −116439287510

Доказательство Эйлера

Если мы возьмем предыдущее доказательство и вместо использования теоремы Лагранжа попытаемся доказать его в этой конкретной ситуации, то мы получим третье доказательство Эйлера, которое он нашел более естественным.[10][11] Позволять А - множество, элементами которого являются числа 1, а, а2, ..., аk − 1 приведенный по модулюп. Если А = грамм, тогда k = п − 1 и поэтому k разделяет п −1. В противном случае есть некоторые б1 ∈ грамм\А.

Позволять А1 - множество, элементами которого являются числа б1, ab1, а2б1, …, аk − 1б1 приведенный по модулюп. потом А1 имеет k отдельные элементы, потому что иначе было бы два разных числа м, п ∈ {0, 1, ..., k − 1} такой, что амб1апб1 (мод п), что невозможно, так как из этого следовало бы амап (мод п). С другой стороны, ни один элемент А1 может быть элементом А, потому что иначе были бы числа м, п ∈ {0, 1, …, k − 1} такой, что амб1ап (мод п), а потом б1апаkмап + kм (мод п), что невозможно, так как б1А.

Итак, набор АА1 имеет 2k элементы. Если окажется, чтограмм, тогда 2k = п −1 и поэтому k разделяет п −1. В противном случае есть некоторые б2 ∈ грамм\(АА1) и мы можем начать все сначала, определяя А2 как множество, элементами которого являются числа б2, ab2, а2б2, ..., аk − 1б2 приведенный по модулюп. С грамм конечно, этот процесс должен остановиться в какой-то момент, и это доказывает, что k разделяет п − 1.

Например, если а = 5 и п = 13, то, поскольку

  • 52 = 25 ≡ 12 (мод 13),
  • 53 = 125 ≡ 8 (мод 13),
  • 54 = 625 ≡ 1 (мод. 13),

у нас есть k = 4 и А = {1, 5, 8, 12}. Четко, А ≠ грамм = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}. Позволять б1 быть элементом грамм\А; например, возьмите б1 = 2. Тогда, поскольку

  • 2×1 = 2,
  • 2×5 = 10,
  • 2 × 8 = 16 ≡ 3 (мод 13),
  • 2 × 12 = 24 ≡ 11 (мод 13),

у нас есть А1 = {2, 3, 10, 11}. Четко, АА1грамм. Позволять б2 быть элементом грамм\(АА1); например, возьмите б2 = 4. Тогда, поскольку

  • 4×1 = 4,
  • 4 × 5 = 20 7 (мод 13),
  • 4 × 8 = 32 ≡ 6 (мод 13),
  • 4 × 12 = 48 ≡ 9 (мод 13),

у нас есть А2 = {4, 6, 7, 9}. И сейчас грамм = АА1А2.

Обратите внимание, что наборы А, А1, и так далее. смежные классы из А в грамм.

Примечания

  1. ^ Голомб, Соломон В. (1956), «Комбинаторное доказательство« маленькой »теоремы Ферма» (PDF), Американский математический ежемесячный журнал, 63 (10): 718, Дои:10.2307/2309563, JSTOR  2309563
  2. ^ Ига, Кевин (2003), "Динамическое системное доказательство малой теоремы Ферма", Математический журнал, 76 (1): 48–51, Дои:10.2307/3219132, JSTOR  3219132
  3. ^ а б c Диксон, Леонард Юджин (2005) [1919], "Теоремы Ферма и Вильсона, обобщения и обращения; симметричные функции 1, 2, ..., п − 1 по модулю п", История теории чисел, я, Дувр, ISBN  978-0-486-44232-7, Zbl  1214.11001
  4. ^ Вакка, Джованни (1894), "Intorno alla prima dimostrazione di un teorema di Fermat", Bibliotheca Mathematica, 2-я серия (на итальянском), 8 (2): 46–48
  5. ^ Алькаускас, Гедрюс (2009), "Любопытное доказательство маленькой теоремы Ферма", Американский математический ежемесячный журнал, 116 (4): 362–364, arXiv:0801.0805, Дои:10.4169 / 193009709x470236, JSTOR  40391097
  6. ^ Харди, Г. Х.; Райт, Э.М. (2008), «Теорема Ферма и ее следствия», Введение в теорию чисел (6-е изд.), Oxford University Press, ISBN  978-0-19-921986-5
  7. ^ Айвори, Джеймс (1806), «Демонстрация теоремы о простых числах», Новая серия математического депозитария, 1 (II): 6–8
  8. ^ Лежен Дирихле, Питер Густав (1828), "Новые демонстрации теории теории относительности", Журнал für die reine und angewandte Mathematik (На французском), 3: 390–393
  9. ^ Вайль, Андре; Розенлихт, Максвелл (1979), "§ VIII", Теория чисел для начинающих, Springer-Verlag, Дои:10.1007/978-1-4612-9957-8, ISBN  978-0-387-90381-1, Zbl  0405.10001
  10. ^ Вайль, Андре (2007) [1984], "§ III.VI", Теория чисел: подход через историю; от Хаммурапи до Лежандра, Биркхойзер, ISBN  978-0-8176-4565-6, Zbl  1149.01013
  11. ^ Эйлер, Леонард (1761), "Теорема приблизительно остаток ex Divisione potestatum relicta" (PDF), Новые комментарии Academiae Scientiarum Petropolitanae (на латыни), 7: 49–82