Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Category:

теорема Ферма

Вчера совершенно случайно наткнулся на очень красивое доказательство теоремы Ферма (но не той, знаменитой, а совсем другой, намного легче - их несколько вообще-то). Как я люблю такие случайные счастливые находки! (ключевое слово: serendipity) Вообще-то, заглядывая научный журнал двухлетней давности, совершенно не ожидаешь найти в нём статью на латыни, но это именно то, что со мной сегодня произошло. Я очень удивился. Оказалось, что это не статья, а часть статьи; вообще-то статья по-английски, но в конце её приведена копия старой и незаслуженно забытой статьи 1854-го года на латыни на эту же тему. Всего две страницы, латинская статья короткая; кстати, и в 1854-м году писать научную статью на латыни было уже делом очень экстравагантным.

Английская статья пересказывала в современных терминах доказательство, появившееся впервые в этой самой коротенькой латинской статье. Доказательство почти совсем элементарное и настолько красивое, что я не могу удержаться от соблазна попробовать его пересказать так просто, как только смогу. Если какие-то шаги будут непонятны, можно спрашивать и я объясню.

Сама же теорема гласит вот что. Разделим все нечётные простые числа на два класса: те, корорые при делении на 4 дают остаток 1, и те, которые при делении на 4 дают остаток 3. Любое число из первого класса можно представить в виде суммы двух квадратов (т.е. в виде a2+b2, где a и b - натуральные числа). Ни одно число из второго класса невозможно представить в виде суммы двух квадратов.




Прежде всего отделим зёрна от плевел. Второе утверждение теоремы тривиально; оно там просто для красоты и полноты. Оно тривиально потому, что сумма двух квадратов никогда не может дать остаток 3 при делении на 4. И вот почему.

Рассмотрим, какие остатки даёт квадрат числа при делении на 4, в зависимости от того, какой остаток даёт само число:
  • Если число a даёт остаток 0 или 2, то оно чётное, значит a=2x для какого-то натурального x. Тогда a2=4x2 делится на 4, т.е. даёт остаток 0.
  • Если число a даёт остаток 1, т.е.
    a=4x+1, тогда a2=(4x+1)2= 16x2+8x+1, т.е. даёт остаток 1.
  • Если число a даёт остаток 3, т.е. a=4x+3, тогда a2=(4x+3)3=16x2+24x+9 = (16x2+24x+8)+1, т.е. опять-таки даёт остаток 1.

Значит, какими бы ни были числа a и b, их квадраты при делении на 4 дают остаток 0 или 1. Но тогда сумма этих квадратов может давать только остатки 0, 1 или 2, но не 3. Поэтому никакое простое число с остатком 3 не может быть представлено в виде суммы двух квадратов.


Нетривиальной частью теоремы является утверждение о том, что любое простое число с остатком 1 можно представить в виде суммы двух квадратов. Впервые это утверждение сформулировали в 17-м веке ещё до Ферма. Названо оно по имени Ферма потому, что в середине 17-го века он утверждал, что у него есть твёрдое доказательство; но самого доказательства не опубликовал (ох, вредные у него были привычки). Первое доказательство опубликовал Эйлер ещё через 100 лет после этого; и пишут, что он искал его в течение семи лет (работая не только над этим, конечно).

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



Начнём немного издалека. Вспомним, как работает очень простой и известный алгоритм Евклида для нахождения наибольшего общего знаменателя чисел x и y.

Пусть у нас есть два числа x и y, причём первое больше второго. Тогда поделим первое на второе с остатком:
  • x = q1*y + r1
При этом остаток r1 будет обязательно меньше делимого y. Если этот остаток равен 0, то мы на этом закончили; если нет, сделаем теперь то же самое, только с y и r1 вместо x и y: поделим большее число на меньшее с остатком, и будем продолжать так же, пока наконец не получим деление без остатка:
  • y = q2*r1 + r2
  • r1 = q3*r2 + r3
    ...
  • rn-3 = qn-1*rn-2 + rn-1
  • rn-2 = qn*rn-1


Когда всё это закончится, последний ненулевой остаток - rn-1 - как раз и будет наибольшим общим делителем x и y. Это легко доказать и проверить, но нас это вообще-то сейчас не интересует. Нам важен алгоритм Евклида не ради этого делителя, а ради последовательности частных q1....qn. Заметим прямо сейчас, что последнее частное qn не может быть 1, оно как минимум 2 (или больше). Это потому, что предпоследний остаток rn-1 не может быть равен предыдущему остатку rn-2, он обязан быть меньше его, т.к. был получен в результате деления с остатком на rn-2.

Запишем все эти равенства немного по-другому, в виде дробей:

 x          r1
--- =  q1+ ---
 y          y

 y          r2
--- =  q2+ ---
 r1         r1

 r1         r3
--- =  q3+ ---
 r2         r2

 ...

 rn-2    
--- =  qn
 rn-1    


Обратим внимание, что каждый раз мы берём целую часть, а дробный остаток "переворачиваем" и прокручиваем заново через тот же алгоритм. "Переворачиваем" - значит, делим 1 на него! Значит, всё это мы можем записать в виде одного длинного равенства такого вида:

 x                               1
---  =   q1+ ----------------------------------------
 y                                 1 
                 q2 + -------------------------------
                                  1
                         q3 + -----------------------
                               .......
                                             1
                                  + qn-1 + ------
                                             qn



(вроде бы IE правильно показывает эту огромную дробь, но Опера не справляется. Если кто-то видит белиберду, то вот что там написано: x/y = q1+1/(q2+1/(q3+....... + 1/qn ))..)))). Т.е. много вложенных дробей, и на каждом уровне есть какой-то qi плюс один делить на следующий уровень).

Перед тем, как читать дальше, советую убедиться, что эта большая формула ясна и понятна.


Итак, что мы видим? Любую дробь вида x/y можно разложить на такую длинную "вложенную" дробь, в которой будут участвовать какие-то натуральные числа q1,q2...qn (причём qn>=2, как мы заметили выше). С другой стороны, ясно, что если мы выберем какие-то числа q1,q2...qn, подставим их в такую дробь, и приведём все к общему знаменателю много раз (начиная с самого низа и продолжая вверх), то в конце концов получим какую-то дробь типа x/y. Числитель и знаменатель этой дроби будут какими-то многочленами от переменных q1,q2...qn, т.к. всё, что мы делаем в процессе приведения к общему знаменателю гигантской дроби, это умножаем разные q друг на друга и складываем, и переворачиваем дроби -- в числителях и знаменателях дробей всегда остаются многочлены с целыми коэффициэнтами.

Обозначим через F(q1...qn) числитель выражения, которое получается после приведения к общему знаменателю такой большой дроби. F(q1...qn) - это какой-то многочлен от переменных q. Например, в простом случае n=2 мы видим, что q1 + 1/q2 будет (q1*q2+1)/q2, т.е. в этом случае F(q1,q2) = q1*q2+1.

Но что находится в знаменателе такой дроби? Представим себе, что мы начали упрощать нашу длинную дробь снизу вверх, и дошли до предпоследнего уровня, и получили что-нибудь такое:

      1
q1+ --------
       s
      ---
       t


Здесь s/t - результат "упрощения" всех уровней, кроме последнего. Что теперь происходит? t переходит вверх в числитель, s остаётся в знаменателе и мы в последний раз всё приводим к общему знаменателю. В результате в числителе у нас будет наша F(q1...qn), по определению, а в знаменателе будет s. Но что такое это s? Это не что иное, как F(q2...qn) - числитель выражения, получающегося, если мы возьмём последовательность q2...qn, т.е. отбросим первый член! Действительно, ведь именно это мы и сделали, когда подсчитали все уровни, кроме первого.

Значит, наше определение функции F в качестве только числителя конечного выражения помогает нам найти и знаменатель тоже - потому что знаменатель обязан быть числителем предыдущего уровня. Значит, общее значение нашей большой дроби равно F(q1...qn)/F(q2...qn). Мы не знаем, как в точности выглядит F, кроме самых простых случаев (т.е. мы можем узнать, но для этого придётся кропотливо подсчитывать и приводить эти дроби), но мы знаем, что это какой-то многочлен от его переменных и что после приведения к общему знаменателю наша большая дробь будет выглядеть именно так.

Пока ещё, пожалуй, неясно, зачем нам всё это нужно для доказательства теоремы Ферма, но скоро, надеюсь, это станет понятным.


Теперь изменим немного нотацию и вместо F(q1...qn) будем писать [q1...qn], используя квадратные скобки. Смысл этого остаётся то же самый, т.е. [q1...qn] - это некий многочлен от переменных q1...qn, который получается в числителе после упрощения большой вложенной дроби, рассмотренной выше.

Перед тем, как перейти к доказательству самой теоремы, нам нужно установить три важных свойства функции [q1...qn].
  • [q1...qn] и [q2...qn] - взяимно простые числа (у них нет общих делителей, больших 1). Иными словами, [q1...qn]/[q2...qn] - несократимая дробь.

    Это легко увидеть индукцией по n. Действительно, ведь по мере упрощения нашей большой дроби мы в конце концов приходим к выражению вида q1 + 1 / ([q2...qn]/[q3...qn]) (под единицей находится как раз предыдущий уровень, про который мы знаем, что он тоже равен частному соответствующих многочленов). По предположению индукции мы знаем, что [q2...qn] и [q3...qn] - взаимно простые. Когда мы переворачиваем эту дробь и прибавляем q1, мы получаем q1 + [q3...qn]/[q2...qn]. Но если эта дробь несократима, то прибавление к ней целого числа оставит её несократимой (общие делители у числителя и знаменателя не могут появиться). Что и требовалось доказать.

    Важное следствие из этого свойства: если мы начнём с несократимой дроби x/y, разложим её по алгоритму Евклида в большую дробь, состоящую из частных q1...qn, а потом эту большую дробь обратно "сложим", и получим по нашему определнию [q1...qn]/[q2...qn], то неизбежно будет x=[q1...qn] и y=[q2...qn], потому что обе дроби несократимы, и из их равенства следует равенство числителей и знаменателей. Это следствие нам понадобится.
  • Следующее свойство, которое нам нужно, выглядит так:
    [q1...qn] = [qn...q1]

    Т.е. если мы перевернём порядок чисел q, то получим то же самое. Важно: это не значит, что если мы построим дробь начиная с qn, продолжая с qn-1, и так далее до q1 в конце, мы получим то же самое! Но это значит, что в числителе мы получим то же самое. Наша функция [q1...qn] - это только числитель упрощённой дроби.

    Это свойство выглядит совсем нетривиальным. Доказать его напрямую из определения [q1...qn] было бы очень сложно и трудоёмко. Я его доказывать здесь не буду, равно как и следующее, третье, свойство; но для тех, кто знает, что такое матрица и детерминант, я укажу ниже, как это можно очень легко показать. Тех, кто это не знает, прошу поверить мне на слово в том, что касается этого и следующего свойства (ещё можно "руками" проверить на нескольких простых случаях их справедливость).
  • Последнее свойство показывает, как можно "расщепить" последовательность чисел q в середине:

    [q1...qi-1,qi,qi+1,...qn] = [q1...qi-1,qi]*[qi+1,...qn] + [q1...qi-1]*[qi+2,...qn]

    Словами: если мы хотим "расщепить" [q1...qn] сразу после члена qi, то это будет равно сумме двух произведений: во-первых, двух половинок, "расщепленных" прямо после qi: одна от 1 до qi, другая от qi+1 до конца; и второе произведение состоит из тех же половинок, но укороченных на один элемент: одна от 1 до qi-1, другая от qi+2 до конца.

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


Техническое примечание. Вот как доказываются последние два свойства. Дело в том, что [q1...,qi] в точности равно детерминанту матрицы размером nxn, которая устроена так: на главной диагонали выписаны числа q1...,qi, на диагонали справа от главной выписана строка из единиц, и на диагонали снизу от главной выписана строка из минус единиц -- так что, например, строка номер i выглядит так: 0....0, -1, qi, 1, 0.....0. Если попробовать вычислить детерминант такой матрицы, начиная с верхней строки, методом разбития на миноры, то мгновенно видим, что получаем рекурсивную формулу спуска точно такого же вида, как в нашей вложенной дроби -- и в конце процесса детерминант будет равен как раз числителю этой дроби после её "упрощения". Теперь если мы вычислим тот же детерминант, начиная с правого нижнего угла, тем же рекурсивным разбитием на миноры, всё время выбирая нижний правый угол вложенных квадратов, то получим [qn...q1] - и отсюда следует второе свойство. А если мы вычислим детерминант, разбивая на миноры согласно строке номер i, то после некоторых сокращений как раз получим формулу свойства номер 3. Вот и всё.

Теперь мы готовы к тому, чтобы доказать теорему Ферма. Т.к. эта запись уже получилась очень длинной, я переношу само доказательство в следующую, и там же прошу оставлять комменты и по поводу содержания этой записи тоже, если есть вопросы или замечания.
Subscribe
Comments for this post were disabled by the author