Целые числа.

[hippie]

Числа $n$ и $\sqrt{2012n^2+1}$ целые.
Обязательно ли число $\sqrt{\frac{\sqrt{2012n^2+1}+1}2}$ тоже целое?

[nnosipov]

Да.

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

[hippie]

Кажется, пора открыть решение.

$\sqrt{2012n^2+1}=k$ — целое. $2012n^2+1=k^2,$ т.е. $503n^2=\frac{k-1}2\cdot\frac{k+1}2.$
Числа $\frac{k-1}2$ и $\frac{k+1}2$ взаимно простые, а их произведение равно произведению простого числа 503 на квадрат целого числа.
Следовательно, один из множителей является квадратом целого числа, а другой произведением 503 на квадрат целого числа.
Если $\frac{k+1}2$ кратно 503, то $\frac{k-1}2 \equiv -1 (\mod 503),$ и, следовательно, не может быть квадратом целого числа.
Таким образом $\frac{k+1}2$ — квадрат целого числа, т.е. $\sqrt{\frac{\sqrt{2012n^2+1}+1}2}=\sqrt{\frac{k+1}2}$ — целое число.

[nnosipov]

Да, довольно банально оказалось.

[temp03]

Зато красиво. Обожаю такие решения.

[nnosipov]

Сделаю одно замечание. Конечно, здесь откровенно повезло, так как иногда неразрешимые уравнения оказываются просто неразрешимыми по некоторому модулю. Но в общем случае рассчитывать на такое везение не приходится. Вот заменим, например, в условии данной задачи число $2012$ на число $244$, и ответить на поставленный вопрос станет гораздо труднее.

[hippie]

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

Конечно, здесь откровенно повезло.

Правильнее сказать "Конечно, здесь ИСКУССТВЕННО подобран коэффициент 2012, при котором проходит данное решение". Действительно, коэффициент подбирался таким образом, чтобы задача имела простое и короткое идейное решение. А иначе это уже не была бы олимпиадная задача .

(Оффтоп)

Понятно, что подходит любое число вида $4q$, где $q$ — простое число вида $4n+3$. В разное время я предлагал эту задачу с разными коэффициентами.
Пять лет назад, когда я эту задачу только придумал, я использовал её с коэффициентом 28. Позже использовал с коэффициентами 52, 236, 12 (кажется всё). А в этом году совершенно случайно обнаружил, что коэффициент 2012 тоже подходит.

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

Но в общем случае рассчитывать на такое везение не приходится. Вот заменим, например, в условии данной задачи число $2012$ на число $244$, и ответить на поставленный вопрос станет гораздо труднее.

Безусловно, если коэффициент не имеет данный (специально подобранный) вид, то задача становится во много раз сложнее, и перестаёт быть олимпиадной.

Что касается коэффициента 244, то для него утверждение не выполнено:
$\sqrt{244\cdot 113076990^2+1} = 1766319049,$ но $\sqrt{\frac{1766319049+1}2}=3805\sqrt{61}\not\in\mathbb{Z}.$

[nnosipov]

hippie в сообщении #546440 писал(а):

Что касается коэффициента 244, то для него утверждение не выполнено:
$\sqrt{244\cdot 113076990^2+1} = 1766319049,$ но $\sqrt{\frac{1766319049+1}2}=3805\sqrt{61}\not\in\mathbb{Z}.$

Здесь также можно обойтись без конкретных вычислений. Сформулирую Вашу задачу в более общем виде.

Задача. Пусть $q$ --- нечётное простое число. Предположим, что для некоторого целого $n$ число $\sqrt{4qn^2+1}$ оказалось целым. Обязано ли число $\sqrt{\frac{\sqrt{4qn^2+1}+1}{2}}$ также быть целым?

Ответ. Если $q \equiv 3 \pmod{4}$, то да, а если $q \equiv 1 \pmod{4}$, то нет.

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

[hippie]

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

Задача. Пусть $q$ --- нечётное простое число. Предположим, что для некоторого целого $n$ число $\sqrt{4qn^2+1}$ оказалось целым. Обязано ли число $\sqrt{\frac{\sqrt{4qn^2+1}+1}{2}}$ также быть целым?

Ответ. Если $q \equiv 3 \pmod{4}$, то да, а если $q \equiv 1 \pmod{4}$, то нет.

Большое спасибо за информативное дополнение!

Когда Вы предложили коэффициент 244, предположил, что в общем виде (для $q \equiv 1 (\mod 4)$) ответ будет именно таким.
Понятно, что задача эквивалентна такой:
Имеет ли решения в целых числах уравнение $qn^2-m^2=1.$
Но как доказывать, что при $q \equiv 1 (\mod 4)$ такое решение существует, не выходя за рамки "стандартного олимпиадного набора", пока не представляю.

[nnosipov]

hippie в сообщении #546977 писал(а):

Но как доказывать ... не выходя за рамки "стандартного олимпиадного набора", пока не представляю.

Хм, что такое стандартный набор --- это вопрос интересный. Какие факты считать общеизвестными? Если считать общеизвестным, что уравнение Пелля $x^2-qy^2=1$ нетривиально разрешимо, то тогда относительно несложно доказать и разрешимость уравнения $x^2-qy^2=-1$. Во всяком случае, для студенческой олимпиады это было бы нормальным.

[hippie]

Тут мой прокол . По поводу "олимпиадных задач" мне нужно было сразу пояснить:
Поскольку исходная задача была составлена для школьной олимпиады (9—11 классы), то и все последующие задачи я рассматривал именно с этой точки зрения, т.е. в сравнении с исходной.
Конечно, если говорить о студенческих олимпиадах, то класс олимпиадных задач значительно шире.
И, для студенческих олимпиад, IMHO, использование теории уравнений Пелля — вполне нормально.

[nnosipov]

Я имел в виду такое рассуждение. Пусть $(x_0,y_0)$ --- минимальное решение уравнения $x^2-qy^2=1$ (раз есть какое-то нетривиальное решение, то есть и минимальное). Ясно, что $y_0$ должно быть чётным, $y_0=2y_1$. Имеем $(x_0-1)(x_0+1)=4qy_1^2$, откуда следует, что либо (a) $(x_0-1)/2=qa^2$, $(x_0+1)/2=b^2$, либо (б) $(x_0-1)/2=a^2$, $(x_0+1)/2=qb^2$ ($a$, $b$ --- некоторые натуральные числа). В случае (а) получаем $b^2-qa^2=1$, но это противоречит минимальности решения $(x_0,y_0)$. А в случае (б) получаем то, что надо: $a^2-qb^2=-1$.

Кстати, вот подумалось, что в самой фразе

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

Предположим, что для некоторого целого $n$ число $\sqrt{4qn^2+1}$ оказалось целым.

уже сказано о том, что нетривиальные решения существуют (конечно, надо заменить "целое $n$" на "натуральное $n$"). Или это уже жульничество ?

[nnosipov]

Вот случайно наткнулся на aops: http://www.artofproblemsolving.com/Foru ... 6&t=461653