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

[avva]

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


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

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

• p = [q₁...q_n], s = [q₂...q_n]

Естественно для разных s мы вообще говоря получим разные n и разные последовательности q! Но для каждой такой последовательности эти два равенства будут выполняться. Более того, обратим внимание, что

• q₁>=2, q_n>=2

Первое из этих равенств следует из того, что значение дроби больше 2, а q₁ - первое целое частное; а второе равенство верно всегда, как мы заметили при обсуждении алгоритма.

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

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

Значит, наша новая дробь равна p/s', где s' - какое-то число из того же промежутка. Но это значит, что разложение p/s' = [q_n...q₁]/[q_n-1...q₁] совпадает с "собственным" разложением p/s', которое мы бы получили, если бы начали с s', а не с s. У p/s' есть какое-то "своё" разложение вида [t₁...t_m]/[t₂...t_m], но из равенства дробей мы видим, что эти разложения обязаны совпадать, т.е. m=n, а последовательность t₁...t_n - это то же, что q₁...q_n, только перевёрнутое наоборот.

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

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

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

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

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

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

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

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

q₁, q₂, ..., q_i, q_i+1, q_i, ...,q₁

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

q₁, q₂, ..., q_i, q_i, ...,q₁

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

p = [q₁, ..., q_i, q_i+1, q_i, ...,q₁] = [q₁, ..., q_i, q_i+1]*[q_i, ...,q₁] + [q₁, ..., q_i]*[q_i-1, ...,q₁]

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

p = [q₁, ..., q_i] ( [q₁, ..., q_i, q_i+1] + [q_i-1, ...,q₁] )

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

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

p = [q₁, q₂, ..., q_i, q_i, ...,q₁]

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

p = [q₁, ..., q_i]*[q_i, ..., q₁] + [q₁, ...,q_i-1]*[q_i-1, ...,q₁]

В обоих слагаемых множители равны друг другу, т.к. получаются друг из друга переворачиванием цепочки индексов (свойство номер два). Поэтому, если мы обозначим a = [q₁, ..., q_i]², b = [q₁, ..., q_i-1]², то получим

• p = a² + b²

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

---

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

Вопросы, дополнения, замечания и прочие комментарии принимаются.

Comments

[malaya-zemlya.livejournal.com]

Интересное доказательство. Удивительно, что все известные мне доказательства в какой-то момент используют ту же самую идею: попытаться разбить множество с нечетным числом элементов на пары. Один элемент останется, Он то и даст нам искомое решение.

Приведу одно короткое и красивое док-во из книжки Proofs from The Book (Martin Aigner, Gunter Siegler. Springer-Verlag 2002)

Буду писать по английски потому, что переключаться с одного шрифта на другой нет никаких таких сил.

Say we have a prime number p=4n+1, we need to represent it as a sum of 2 squares
1. Consider set of integer triples
S={(x,y,z),x>0,y>0,4xy+z^2=0}
S is finite because 0

[Error: Irreparable invalid markup ('<x<p/4,0<y<p/4>') in entry. Owner must fix manually. Raw contents below.]

Интересное доказательство. Удивительно, что все известные мне доказательства в какой-то момент используют ту же самую идею: попытаться разбить множество с нечетным числом элементов на пары. Один элемент останется, Он то и даст нам искомое решение.

Приведу одно короткое и красивое док-во из книжки Proofs from The Book (Martin Aigner, Gunter Siegler. Springer-Verlag 2002)

Буду писать по английски потому, что переключаться с одного шрифта на другой нет никаких таких сил.

Say we have a prime number p=4n+1, we need to represent it as a sum of 2 squares
1. Consider set of integer triples
S={(x,y,z),x>0,y>0,4xy+z^2=0}
S is finite because 0<x<p/4,0<y<p/4 and for each x,y we have only 2 possible values of z with opposite signs.
We cannot have z=0 because p is prime. From this we can also see that S contains an even number of elements.

2. Consider mapping f:(x,y,z)->(y,z,-z)
It is an involution (is its own inverse) and it has no fixed points (because it flips the sign of z)
Using it we can split S in 2 halves such that f exchanges the elements between them. We can do it in many ways, for example:

A={(x,y,z):z>0) <-> S-A={(x,y,z):z<0)
or
B={(x,y,z):x-y+z>0) <-> S-B={(x,y,z):x-y+z<0)

for the 2nd example we need to prove that there's no x-y+z=0 in S. But that's easy
x-y+z=0->z=y-x->p=4xy+(y-x)^2=(x+y)^2 which contradicts p being prime

From the above we can also conclude that |A|=|B|=|S|/2

2. Consider mapping g:B->B
(x,y,z)->(x-y+z,y,2y-z)
It is very straightforward to prove that it indeed maps B to B and that it is an involution.
However it contains exactly 1 fixed point:
((p-1)/4,1,1)
The uniqueness of this fixed point follows from arithmetic and p being prime.
Conclusion: B contains an odd number of elements

3. Consider mapping h:A->A (x,y,z)->(y,x,z)
It is trivial to see that it indeed maps A to A and that it is an involution.
<b>But A contains the same number of elements as B, and B contains an odd number of elements. Therefore h must have a fixed point</b>
So A contains a point that looks like (x,x,z) . From this we conclude that
p=4x^2+z^2=(2x)^2+z^2

We just have represented p as a sum of 2 squares. QED.

Re:

[avva.livejournal.com]

Я восстановлю Ваш аргумент, он не показывается полностью из-за проблемы со скобками, интерпретирующимися в виде тагов. В определении S у Вас 0 там где, кажется, должно быть p? Определение f у Вас (x,y,z)->(y,z,-z), но должно быть (x,y,z)->(x,y,-z), верно?

А книжка Proofs from the Book очень хорошая, действительно, я её листал несколько раз.

-----------------------------
Say we have a prime number p=4n+1, we need to represent it as a sum
of 2
squares 1. Consider set of integer triples
S={(x,y,z),x>0,y>0,4xy+z^2=p}
S is finite because 0<x<p/4,0<y<p/4 and for each x,y we have only 2
possible values of z with opposite signs. We cannot have z=0 because p
is prime. From this we can also see that S contains an even number of
elements.

2. Consider mapping f:(x,y,z)->(y,z,-z) It is an involution (is its
own
inverse) and it has no fixed points (because it flips the sign of z)
Using it we can split S in 2 halves such that f exchanges the elements
between them. We can do it in many ways, for example:

A={(x,y,z):z>0) <-> S-A={(x,y,z):z<0)

or B={(x,y,z):x-y+z>0) <-> S-B={(x,y,z):x-y+z<0)

for the 2nd example we need to prove that there's no x-y+z=0 in S. But
that's easy x-y+z=0->z=y-x->p=4xy+(y-x)^2=(x+y)^2 which contradicts p
being prime

From the above we can also conclude that |A|=|B|=|S|/2

2. Consider mapping g:B->B (x,y,z)->(x-y+z,y,2y-z) It is very
straightforward to prove that it indeed maps B to B and that it is an
involution. However it contains exactly 1 fixed point: ((p-1)/4,1,1)
The
uniqueness of this fixed point follows from arithmetic and p being
prime. Conclusion: B contains an odd number of elements

3. Consider mapping h:A->A (x,y,z)->(y,x,z) It is trivial to see that
it
indeed maps A to A and that it is an involution. But A contains the
same number of elements as B, and B contains an odd number of
elements.
Therefore h must have a fixed point So A contains a point that
looks
like (x,x,z) . From this we conclude that p=4x^2+z^2=(2x)^2+z^2

We just have represented p as a sum of 2 squares. QED.

Re:

[malaya-zemlya.livejournal.com]

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

:В определении S у Вас 0 там где, кажется, должно быть p?

Да.

:Определение f у Вас (x,y,z)->(y,z,-z), но должно быть (x,y,z)->(x,y,-z), верно?

(x,y,z)->(y,x,-z)

у и х переставлены местами, а z меняет знак. Это важно, иначе работать не будет.

Re:

[avva.livejournal.com]

А! Теперь понятно, почему f делит S пополам на B и S\B, а то у меня это не сходилось. Спасибо ещё раз, красивый аргумент.