Задача 79 из Серпинского (о простых вида 4k+1)

[Ktina]

Доказать, что каждое простое число вида $4k+1$ является длиной гипотенузы прямоугольного треугольника, стороны которого выражаются натуральными числами.

В книге дано такое решение:
Согласно известной теореме Ферма каждое простое число вида $4k+1$ есть сумма двух квадратов натуральных чисел...

Я знаю три теоремы Ферма: Великую, Малую и Среднюю (это в МАТАНе, когда функции на экстремум исследуют). Но ни в одной из этих трёх не говорится о том, о чём упоминает Серпинский.

[Whitaker]

Ktina
Вообще-то это теорема Ферма-Эйлера:
Каждое простое число вида $4k+1$ можно представить в виде суммы двух квадратов.
Можете посмотреть тут

[fancier]

Whitaker в сообщении #649398 писал(а):

Ktina
Вообще-то это теорема Ферма-Эйлера:
Каждое простое число вида $4k+1$ можно представить в виде суммы двух квадратов.
Можете посмотреть тут

Айерленд и Роузен пишут, что Ферма (стр. 122 русскоязычного издания). См. также стр. 81 и далее в "Живых числах".

[Whitaker]

fancier
В книге К. Чандрасекхарана "Введение в АТЧ" эта теорема Эйлера.
В русской Википедии теорема Эйлера-Ферма, а в английской теорема Ферма

[Ktina]

Whitaker в сообщении #649398 писал(а):

Ktina
Вообще-то это теорема Ферма-Эйлера:
Каждое простое число вида $4k+1$ можно представить в виде суммы двух квадратов.
Можете посмотреть тут

И доказательство длинновато...

[Whitaker]

Ktina
Через квадратичный вычеты довольно коротко доказывается. Можете посмотреть в К. Чандрасекхаране "Введение в АТЧ"

[nnosipov]

Ktina в сообщении #649406 писал(а):

И доказательство длинновато...

А как же Zagier's "one-sentence proof"? Впрочем, на мой взгляд, оно хоть и самое короткое, но точно не самое простое.

[fancier]

Ktina в сообщении #649406 писал(а):

И доказательство длинновато...

Одно короткое доказательство основано на том, что простое нечетное $p$ раскладывается в произведение различных простых в кольце целых гауссовых чисел т. и т.т., когда -1 является квадратичным вычетом по модулю $p$, т.е. $p$ сравнимо с 1 по модулю 4. Но, пожалуй, оно не совсем элементарно...

[Keter]

Можно через представление пифагоровых троек попробовать.

Простое число $p=4k+1$ представимо в виде суммы двух квадратов натуральных чисел (это следует из теоремы Ферма-Эйлера). То есть $p=4k+1=m^2+n^2$, где $m, n \in \mathbb{N}$.

Рассмотрим числа $a=m^2-n^2$ и $b=2mn$ (будем считать, что $m>n$). Докажем тождество $p^2=a^2+b^2$:

$(m^2+n^2 )^2=(m^2-n^2 )^2+(2mn)^2,$

$m^4+2m^2 n^2+n^4=m^4-2m^2 n^2+n^4+4m^2 n^2,$

$2m^2 n^2=2m^2 n^2.$

А доказательство самой теоремы могу в оффтоп кинуть. В иностранных источниках Zagier's "one-sentence proof", почему-то именно это док-во мне нравится больше всего. Хотя есть более короткое, через детерминанты, но не вникал.

(Оффтоп)

Рассмотрим преобразование, которое тройке натуральных чисел $(x; y; z)$ сопоставляет три числа $(x'; y'; z')$ по следующему правилу:

$x'=x+2z, y'=z, z'=y-x-z,$ если $x<y-z, \quad (1)$
$x'=2y-x, y'=y, z'=x-y+z,$ если $y-z \le x \le 2y, \quad (2)$
$x'=x-2y, y'=x-y+z, z'=y,$ в остальных случаях. $\quad (3)$

Обозначим это преобразование буквой $B$:

$B(x; y; z)=(x'; y'; z').$

Очень легко проверить,что преобразование $B$ сохраняет форму $x^2+4yz.$
Для случая $(1)$ имеем:
$x'^2+4y' z'=(x+2z)^2+4z(y-x-z)=x^2+4xz+4z^2+4yz-4xz-4z^2=x^2+4yz.$
Для случая $(2)$ имеем:
$x'^2+4y' z'=(2y-x)^2+4y(x-y+z)=4y^2-4yx+x^2+4yx-4y^2+4yz=x^2+4yz.$
Для случая $(3)$ имеем:
$x'^2+4y' z'=(x-2y)^2+4y(x-y+z)=x^2-4xy+4y^2+4yx-4y^2+4yz=x^2+4yz.$

Значит, если для какого-то числа $p$ имелось равенство $x^2+4yz=p$, то оно сохранится и после преобразования $B$.
Проверим, что преобразование $B$, дважды примененное, возвращает нас назад.

Проделаем это для случая $(1)$.
Пусть $x<y-z$, тогда $x'=x+2z, y'=z, z'=y-x-z$, откуда $x'=x+2z>y'-z'=2z+x-y$ и, значит, $B(x'; y'; z')$ надо вычислять по правилу $(3)$:
$x''=x'-2y'=x+2z-2z=x,$
$y''=z'-y'-z'=x+2z-z+y-x-z=y,$
$z''=y'=z.$
И в остальных случаях все аналогично.

А теперь предположим, что $p$ – простое число вида $4k+1$. Тогда, во-первых, уравнение $x^2+4yz=p$ разрешимо, по крайней мере, двумя способами: $x=1, y=k, z=1$ или $x=y=1, z=k$. И, во-вторых, это уравнение имеет конечное число решений. Если предположить, что среди его решений нет таких, при которых $y=z$ (ведь если таковы имеются, то и доказывать нечего: $p=x^2+(2y)^2$), мы получим, что преобразование $B$ разбивает все решения на пары:
$(x; y; z); B(x; y; z)$, если только $(x; y; z) \ne B(x; y; z)$. Посмотрим, существуют такие пары или имеются ли у преобразования $B$ неподвижные точки.

Очень легко понять, посмотрев на формулы $(1) - (3)$, что неподвижные точки у $B$ – те, для которых $x=y$. Но при $x=y>1$ решений у уравнения $x^2+4yz=p$ нет (ибо $p$ не кратно $y$). Значит, есть только одна неподвижная точка $(1; 1; k)$. Из всего сказанного вытекает, что число решений уравнения $x^2+4yz=p$ нечетно: неподвижная точка $(1; 1; k)$, а остальные решения разбиваются на пары.

Однако есть еще одно преобразование, обозначим его $J$, которое $y$ и $z$ меняет местами: $J(x; y; z)=(x; z; y)$. Посмотрим, какие тройки (из наших решений уравнения $x^2+4yz=p$) оно оставляет на месте, то есть каковы те $(x; y; z)$, что $(x; y; z)=(x; z; y)$.

Мы условились ранее, что $y \ne z$. Но тогда и неподвижных точек нет! Значит, все решения разбиваются на пары. То есть число решений четно! Но только что мы утверждали, что число решений нечетно. Получилось противоречие. Значит, обязано существовать решение уравнения $x^2+4yz=p$, где $y=z$, то есть $p=x^2+(2y)^2$ – сумма двух квадратов. Мы доказали, что простое число $p=4k+1$ представимо в виде суммы двух квадратов натуральных чисел.

-- 25.11.2012, 22:56 --

Ktina, кстати, Вы думали о той задаче (произведение чисел в строках и столбцах таблицы)?

[nnosipov]

Keter в сообщении #649663 писал(а):

Хотя есть более короткое, через детерминанты, но не вникал.

Возможно, имеется в виду доказательство, основанное на лемме Минковского о выпуклом теле. Вполне элементарное и вообще симпатичное. Кстати, эта же идея работает и при доказательстве теоремы Лагранжа о 4-х квадратах.

[Коровьев]

Я уже приводил на этом форуме довольно простое доказательство, доступное даже для не обременённых знаниями школьников. Правда, без доказательства леммы на основе Малой теоремы Ферма. Но и там доказательство очень простое. Ну а если исходить из существования первообразных корней по модулю $P$, то лемма доказывается в пол-строки.

[nnosipov]

Коровьев в сообщении #650002 писал(а):

Я уже приводил на этом форуме довольно простое доказательство

В учебной литературе оно известно как доказательство Лагранжа.