И это последнее доказательство — из книги Конвея и Ги, "The Book of Numbers".

Да — если уж я пересказываю эти доказательства, то "доказательство складыванием" тоже симпатичное:

Прикладывание катета к гипотенузе приводит к появлению меньшего треугольника — опять с целыми сторонами.

Да, в трёх доказательствах — folding, переворачивание и квадраты — для корня из двух операция спуска на самом деле одна и та же:
из P и Q делается (2Q-P) и (P-Q).

Ещё — читая эту работу, я поймал себя на желании взять ручку и бумагу и сделать список доказательств с краткими комментариями. Дочитав до конца, обнаружил, что авторы уже об этом позаботились:

Федор Петров напомнил про доказательство Рождественской теоремы Ферма, немного похожее на доказательство через квадраты выше — только вместо бесконечного спуска там инволюция.

Рождественская теорема Ферма говорит о том, какие простые представимы в виде суммы двух квадратов: это 2 и простые вида 4k+1 (и только они).

У неё есть стандартное доказательство через гауссовы целые числа: сначала доказываем, что в кольце Z[i]=Z+iZ тоже есть алгоритм Евклида, и потому там есть однозначность разложения на простые.
Потом — что по модулю p=4k+1 есть корень из (-1), потому что если разбивать все ненулевые остатки (а их p-1=4k) на четвёрки (x,1/x,-x,-1/x), то одна такая "четвёрка" схлопнется в двойку (1,-1), а значит, должна схлопнуться и ещё одна. А это может случиться, только если по модулю p есть корень из (-1).
Кстати, так же проверяется, что по модулю простых вида 4k+3 корня из (-1) не бывает (потому что там p-1=4k+2 ненулевых остатка как раз разбиваются на двойку (1,-1) и четвёрки — а места для ещё одной двойки не остаётся).
Ну а дальше из соотношения r^2+1=(r+i)(r-i)=mp и основной теоремы арифметики в Z[i] выводится, что p не простое — и значит, p=(a+bi)(a-bi), то есть p=a^2+b^2.

Так вот — это стандартное доказательство, и оно требует некоторого количества техники (хоть и "по делу"). А есть гораздо более простое доказательство представимости простых вида 4k+1 в виде суммы двух квадратов — геометрическая обработка А. В. Спиваком доказательства, предложенного Д. Загиром (в свою очередь, упростившего доказательство Heath-Brown-а).

А именно: пусть p=4k+1. Если уж p получится представить в виде суммы квадратов, то один из них будет чётным (а другой нечётным, но это неважно). Поэтому давайте сразу искать представление в виде p=x^2+4y^2.

Для этого рассмотрим все возможные представления p в виде p=x^2+4yz, где x,y,z натуральные. И рассмотрим на этом множестве инволюцию — поменяем местами y и z. Так вот, нас интересует неподвижная точка этой инволюции — та, где y=z. (Точка или точки, конечно, но на самом деле она одна).

Как можно гарантировать, что неподвижная точка у инволюции есть? Да очень просто — если общее число точек нечётно, то на пары они в любом случае не разобьются, и неподвижная точка будет.

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

А теперь, собственно, изюминка этого рассуждения: вторую инволюцию можно задать формулами — но гораздо лучше задать геометрически. А именно — представлению p=x^2+4yz можно сопоставить этакую "мельницу":

(Я взял этот рисунок из записок самого Спивака — http://mmmf.msu.ru/lect/spivak/zagir_!.pdf — см. лекцию 15 тут: http://mmmf.msu.ru/lect/lect8.html )

Так вот, на таких "мельницах" есть инволюция, которую проще показать, чем задавать формулами:

(Рисунок оттуда же)