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

[olia=))]

Всеукраинская интернет олимпиада

[nnosipov]

olia=)) в сообщении #462345 писал(а):

ну а теорема Ферма-Эйлера эт хорошо, но я уверена что наша задача решается проще только как(( в этой теореме 4к+1, а у нас 4к+1 в квадрате, можно конечно одно из другого вывести , но это часный случай и поэтому не имеет смысла лёгкий случай через тяжёлую теорему((((

Вот дела, это я не вчитался в условие задачи! Надо подумать. Это действительно интересно --- обойтись здесь без теоремы Ферма-Эйлера.

[mihailm]

Может выяснить в начале действующая олимпиада или нет?

[nnosipov]

Пусть $p=4k+1$ --- данное простое число. Предположим, что мы легко доказали существование таких натуральных чисел $x$ и $y$, что $p^2=x^2+y^2$. Тогда $(x,y,p)$ --- пифагорова тройка, причём примитивная, так как $\gcd{(x,y)}=1$. Но устройство примитивных пифагоровых троек хорошо известно (это --- тоже легкий результат): существуют такие натуральные $m$ и $n$, что $x=m^2-n^2$, $y=2mn$ и $p=m^2+n^2$. В частности, получается, что мы легко доказали теорему Ферма-Эйлера, т.е. доказали существование представления $p=m^2+n^2$. Таким образом, задача ТС столь же сложна (или столь же проста, это смотря с какой стороны посмотреть), как и теорема Ферма-Эйлера.

[olia=))]

да я уже натыкалась на такую идею решения, но врядли на олимпиаде за 10 клас хотели увидеть доказательство теорема Ферма-Эйлер о двух квадратах. если расчитывали на это решение , то без доказательства, но как ведь мы этого не учили... НО ВСЁ РАВНО СПАСИБО, ЧТО СТАРАЕТЕСЬ ПОМОЧЬ)))

[nnosipov]

olia=)) в сообщении #462425 писал(а):

но врядли на олимпиаде за 10 клас хотели увидеть доказательство теорема Ферма-Эйлер о двух квадратах

Видите ли, olia=)), либо кто-то умудрился придумать очередное простое доказательство теоремы Ферма-Эйлера (как в своё время это сделал Цагир), либо организаторы олимпиады просто плохо подобрали задачи (ведь остальные задачи ТС совсем банальные и близко не стоят с этой классической теоремой).

[Sonic86]

Наиболее простое (но вообще не простое) доказательство можно найти в книге Доказательства из Книги (погуглите). Может доказательство оттуда как раз от Цагира

[olia=))]

прочитав это доказательство можно понять значение высказывания (Наиболее простое (но вообще не простое))

[nnosipov]

Я бы рекомендовал разобрать исторически первое доказательство, данное Эйлером. Оно интересно, поучительно и более естественно по сравнению с экзотическим доказательством Цагира (хоть и коротким, one sentence, но отнюдь не простым). Доказательство Эйлера следует идее Ферма и основано на методе бесконечного спуска. Для доказательства основной леммы (о разрешимости сравнения $x^2+1 \equiv 0 \pmod{p}$ для простых $p=4k+1$) Эйлер применяет (по-видимому, впервые в теории чисел) конечные разности, а также малую теорему Ферма; в современных учебниках по элементарной теории чисел эту лемму обычно доказывают при помощи теоремы Вильсона.

Интересная интерпретация доказательства Цагира есть в http://mmmf.math.msu.su/lect/spivak/summa_sq.pdf См. также А.В. Спивак, Арифметика-2 (приложение к журналу "Квант", № 5, 2008).

[olia=))]

в кванте я читала эту статью, а по сылке сейчас читаю... СПАСИБО ВАМ))))

-- 26.06.2011, 21:22 --

квант был за другой год но оч по теме, а тот за 2008 я найти не могу

[nnosipov]

olia=)) в сообщении #462498 писал(а):

а тот за 2008 я найти не могу

Только что скачал книжку Спивака (добрые люди её уже отсканировали и выложили; поскольку я хорошо знаком с автором, знаю, он будет не в обиде) и уже проглядел. Настоятельно рекомендую. Там есть всё, о чём я писал выше.

[olia=))]

а как называется книжка?? заранее спасибо)))

[nnosipov]

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

А.В. Спивак, Арифметика-2 (приложение к журналу "Квант", № 5, 2008).

[age]

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

Таким образом, задача ТС столь же сложна (или столь же проста, это смотря с какой стороны посмотреть), как и теорема Ферма-Эйлера.

Абсолютно одно и то же.

olia=)) в сообщении #462425 писал(а):

да я уже натыкалась на такую идею решения, но врядли на олимпиаде за 10 клас хотели увидеть доказательство теорема Ферма-Эйлер о двух квадратах.

И не увидите, оно занимает несколько страниц. Структура примерно такая:
1) если какая-то сумма квадратов делится на сумму квадратов, то и частное тоже сумма квадратов;
2) если сумма квадратов делится на какое-то число, то это число - сумма квадратов;
3) для всякого простого $p=4k+1$ найдётся сумма квадратов которая делится на $p$.

Первые два доказываются методом бесконечного спуска, а вот доказательства третьего методом бесконечного спуска сколько я ни искал (ни сам, ни в книжках, ни в интернете) так и не нашёл.

А если методом Лагранжа, то десятиклассникам такое и не снилось.

[nnosipov]

age в сообщении #462543 писал(а):

И не увидите, оно занимает несколько страниц. Структура примерно такая:
1) если какая-то сумма квадратов делится на сумму квадратов, то и частное тоже сумма квадратов;
2) если сумма квадратов делится на какое-то число, то это число - сумма квадратов;
3) для всякого простого $p=4k+1$ найдётся сумма квадратов которая делится на $p$.

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