Нужна помощь. Задача на делимость и антье.

[age]

nnosipov в сообщении #462596 писал(а):

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

Тогда неизвестно в п.3, если найдётся сумма квадратов, которая делится на $p=4k+1$, то будет ли $p$ суммой квадратов?

[nnosipov]

Давайте я напишу доказательство, считая, что п.п. 1) и 3) доказаны. Итак, пусть $p \equiv 1 \pmod{4}$ --- простое число, для которого теорема неверна. В соответствии с п. 3) имеем $x^2+1=pm$ для некоторых целых $x$ и $m$, при этом $1<m<p$. Число $m$ обязательно имеет простой делитель $p_1$, не представимый в виде суммы двух квадратов (действительно, если все простые делители $m$ суть суммы квадратов, то, применяя несколько раз п. 1), придём к тому, что и $p$ есть сумма квадратов, вопреки предположению). Поскольку $p_1 \equiv 1 \pmod{4}$ и, кроме того, $p_1<p$, получается, что $p_1$ --- меньшее простое число, для которого теорема также неверна. Но в таком случае возможен бесконечный спуск $p>p_1>p_2>\dots$, что и является искомым противоречием.

Как видно, в этом рассуждении используется ещё и такой "медицинский" факт: сравнение $x^2+1 \equiv 0 \pmod{p}$ неразрешимо для любого простого $p=4k+3$. Но он доказывается совсем просто --- при помощи малой теоремы Ферма. В самом деле, из разрешимости сравнения следовало бы противоречие: $1 \equiv x^{p-1}=(x^2)^{(p-1)/2}=(x^2)^{2k+1} \equiv (-1)^{2k+1}=-1 \pmod{p}$.

[Батороев]

(Оффтоп)

Скорее всего, задача 2 предполагала лишь знание теоремы Ферма-Эйлера, а именно того, что любое простое число $p=4k+1$ представимо в виде суммы двух квадратов.
И далее:

$p=4k+1=a^2+b^2$

$p=\dfrac{2a^2+2b^2}{2}$

$4a^2b^2=\left(\dfrac{2a^2+2b^2}{2}\right)^2-\left(\dfrac{2a^2-2b^2}{2}\right)^2$

$4a^2b^2=p^2-\left(\dfrac{2a^2-2b^2}{2}\right)^2$.

Ну, или что еще хлеще, что у квадрата простого $(4k+1)^2$ не может быть простых делителей вида $4k+3$ в нечетных степенях ( ).

[nnosipov]

Батороев в сообщении #462689 писал(а):

(Оффтоп)

Скорее всего, задача 2 предполагала лишь знание о существовании теоремы Ферма-Эйлера, а именно то, что любое простое число $p=4k+1$ представимо в виде суммы двух квадратов.
И далее:

$p=4k+1=a^2+b^2$

$p=\dfrac{2a^2+2b^2}{2}$

$4a^2b^2=\left(\dfrac{2a^2+2b^2}{2}\right)^2-\left(\dfrac{2a^2-2b^2}{2}\right)^2$

$4a^2b^2=p^2-\left(\dfrac{2a^2-2b^2}{2}\right)^2$.

(Оффтоп)

Да, такой вариант вполне правдоподобен. В целом, это плохая задача для олимпиады.

[Батороев]

nnosipov в сообщении #462692 писал(а):

(Оффтоп)

В целом, это плохая задача для олимпиады.

(Оффтоп)

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

[nnosipov]

Батороев в сообщении #462696 писал(а):

(Оффтоп)

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

(Оффтоп)

Эта задача плоха тем, что она даёт явные преимущества тем, кто знает о теореме Ферма-Эйлера. А для таких, кстати, задача вообще выглядит глупой, ибо её решение слишком очевидно.

[Батороев]

(Оффтоп)

Знает, значит, увлекается. А если увлекается, то почему не должен иметь преимущество?!
Остальные же пусть доказывают, что их способности сродни со способностями Рамануджана.