Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Categories:

теорема Ферма, продолжение

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


Итак, пусть у нас есть простое число p, которое при делении на 4 даёт остаток 1, т.е. мы можем записать его в виде p = 4*x + 1.

Пусть s - какое-то число в промежутке от 2 до 2*x. Посмотрим на дробь p/s. Значение этой дроби больше 2, т.к. p > 2*2x. Мы можем использовать алгоритм Евклида для того, чтобы найти последовательность частных q1...qn для этой дроби. Как мы показали раньше, мы тогда получим p/s = [q1...qn]/[q2...qn]. Более того, т.к. число p простое, дробь p/s обязательно будет несократимой, и тогда первое свойство функции [q1...qn] говорит нам, что
  • p = [q1...qn], s = [q2...qn]

Естественно для разных s мы вообще говоря получим разные n и разные последовательности q! Но для каждой такой последовательности эти два равенства будут выполняться. Более того, обратим внимание, что
  • q1>=2, qn>=2
Первое из этих равенств следует из того, что значение дроби больше 2, а q1 - первое целое частное; а второе равенство верно всегда, как мы заметили при обсуждении алгоритма.

Итак, мы взяли какое-то s в промежутке от 2 до 2x, и получили q1...qn. Теперь перевернём эту последовательность: qn...q1 и проделаем обратную операцию: составим большую вложенную дробь, начиная с qn, потом qn-1... и так далее до q1. Мы уже знаем, что когда мы эту большую дробь приведём к общему знаменателю, то получим [qn...q1]/[qn-1...q1] (знаменатель есть числитель без первого члена).

Но числитель этой дроби - [qn...q1] - равен [q1...qn] согласно нашему второму свойству функции [q1...qn]. А это в свою очередь равно исходному числу p, как мы видели выше. Значит, эта дробь равна p/[qn-1...q1] . Более того, первое частное этой новой дроби равно qn, а мы знаем, что qn>=2. Значит, в этой дроби p делится на какое-то число более чем в два раза меньше, чем p. Но такое число обязано тоже принадлежать промежутку от 2 до 2x, ведь p/2 - это 2x+1/2!

Значит, наша новая дробь равна p/s', где s' - какое-то число из того же промежутка. Но это значит, что разложение p/s' = [qn...q1]/[qn-1...q1] совпадает с "собственным" разложением p/s', которое мы бы получили, если бы начали с s', а не с s. У p/s' есть какое-то "своё" разложение вида [t1...tm]/[t2...tm], но из равенства дробей мы видим, что эти разложения обязаны совпадать, т.е. m=n, а последовательность t1...tn - это то же, что q1...qn, только перевёрнутое наоборот.

Если мы теперь возьмём это разложение для p/s' и опять его перевернём, то очевидно, что получим обратно разложение для p/s - потому что всё, что мы при этом сделаем, это просто перевернём qn...q1 обратно в q1...qn.

Что мы из этого видим? Мы видим, что любому числу s из промежутка от 2 до 2x соответствует число s' из того же промежутка, так что p/s и p/s' разлагаются в последовательности вида q1...qn, перевёрнутые по отношению друг к другу.

Но чисел в этом промежутке от 2 до 2x нечётное количество!

Их нечётное количество - ровно 2x-1 чисел - и поэтому хотя бы одно из них обязано
"спариться" с самим собой в этом распределении
. Т.е. для какого-то s его s' - это оно само.

Но что это значит? Это значит, что для такого s у нас есть разложение p/s=[q1...qn]/[q2...qn], и оно же равно [qn...q1]/[qn-1...q1]. Дроби равны между собой, т.к. s=s'.

Если мы возьмём дробь [q1...qn]/[q2...qn], и будем её раскладывать по алгоритму Евклида в вложенную дробь, то мы знаем, что будем получать одно за другим частные q1, потом q2, потом q3... и так далее до qn. Если мы начнём с дроби вида [qn...q1]/[qn-1...q1] и начнём её раскладывать по алгоритму Евклида, то мы тоже знаем, что будем получать частные qn, потом qn-1... и так далее до q1.
Но мы только что увидели, что это одна и та же дробь, значит, и частные должны быть одинаковые в обоих случаях! Т.е. мы обязательно получаем, что q1=qn, q2=qn-1, q3=qn-2... и так далее.

Иными словами, наша последовательность q1...qn для p/s (такого s, которое "спаривается" само с собой) - палиндром: она читается одинаково с начала и с конца.

Раз она палиндром, то есть две возможности: либо у неё длина нечётная, и тогда она выглядит так:

q1, q2, ..., qi, qi+1, qi, ...,q1

или у неё чётная длина, и тогда она выглядит так:

q1, q2, ..., qi, qi, ...,q1

Предположим сначала, что у неё нечётная длина, и выведем из этого противоречие. Применяя свойство номер три (сложную формулу, позволяющую "расщепить" выражение типа [q1...qn] в середине), получаем:

p = [q1, ..., qi, qi+1, qi, ...,q1] = [q1, ..., qi, qi+1]*[qi, ...,q1] + [q1, ..., qi]*[qi-1, ...,q1]

Но в обоих слагаемых есть общий множитель: [q1, ..., qi], он же [qi, ...,q1] (равны по второму свойству). Вынося его за скобки, получаем

p = [q1, ..., qi] ( [q1, ..., qi, qi+1] + [qi-1, ...,q1] )

Т.к. легко видеть, что оба множителя больше единицы, а p - простое число, получаем противоречие.

Из этого следует, что в нашем палиндроме q1, ..., qi обязательно должно быть чётное количество чисел, т.е. он выглядит так:

p = [q1, q2, ..., qi, qi, ...,q1]

Применим к этому выражению опять свойство номер 3, "расщепив" его на индексе i, и получим

p = [q1, ..., qi]*[qi, ..., q1] + [q1, ...,qi-1]*[qi-1, ...,q1]

В обоих слагаемых множители равны друг другу, т.к. получаются друг из друга переворачиванием цепочки индексов (свойство номер два). Поэтому, если мы обозначим a = [q1, ..., qi]2, b = [q1, ..., qi-1]2, то получим
  • p = a2 + b2


Что и требовалось доказать.



Уф... это получилось раза в два длиннее, чем я рассчитывал. Надеюсь, что хоть кто-то дочитал до конца и что хоть кому-то понравилось ;)

Вопросы, дополнения, замечания и прочие комментарии принимаются.
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 8 comments