Какие натуральные числа представимы в виде

[nnosipov]

$$ \frac{y^2+1}{x^2-y^2}, $$

где $x$, $y$ --- некоторые целые числа?

Q. Не встречалась ли кому-нибудь эта задачка? Если да, то где?

[maxal]

Обозначая $u=x+y$ и $v=x-y$, получаем:

$$\frac{y^2+1}{x^2-y^2}=\frac{u^2-2uv+v^2+4}{4uv}.$$

Если $u=v$, то решение единственно - $u=v=1$.
Рассмотрим случай $u\ne v$.

Заметим, что $u^2+v^2+4$ должно делиться на $uv$ и применим к этому Vieta jumping. Получим, что $u$, $v$ представляют собой соседние члены одной из следующих рекуррентных последовательностей: A001653 или A052995. Остается только взять явные формулы для их членов и проверить проигнорированную делимость на дополнительную 4-ку.

[nnosipov]

maxal в сообщении #537523 писал(а):

Обозначая $u=x+y$ и $v=x-y$, переходим к форме ...

Да, действительно, этот переход приводит к довольно известному сюжету. Вот ответ: только единица. А формой

$$ \frac{x^2+1}{x^2-y^2} $$

представляется тоже только одно натуральное число --- двойка, но это та же задача

[Shadow]

Получается уравнение $Ax^2-(A+1)y^2=1$. Вот здесь http://dxdy.ru/post529952.html#p529952 Вами объяснено, что кроме $A=1, B=2$ одно из уравнений $Ax^2-By^2=1 \text{ и }Ax^2-By^2=-1$ не имеет решений. Уравнение $Ax^2-(A+1)y^2=-1$ имеет тривиальное решение $x=1, y=1$ - значит наше не имеет, кроме при $A=1$. Т.е только 1 представимо.

[nnosipov]

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

[nnosipov]

Возможно, вот такая задача будет поинтересней.
Пусть $a$ --- фиксированное целое число, не являющееся точным квадратом. Доказать, что множество натуральных чисел, представимых в виде

$$ \frac{x^2-a}{x^2-y^2} $$

($x$, $y$ --- целые числа), является конечным.
P.S. Если $a$ --- точный квадрат, то в указанном виде представляется любое натуральное число.

[nnosipov]

В последней задаче было бы интересно также оценить через $a$ количество тех натуральных чисел, которые представимы в указанном виде.

[Sonic86]

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

Пусть $a$ --- фиксированное целое число, не являющееся точным квадратом. Доказать, что множество натуральных чисел, представимых в виде

$$\frac{x^2-a}{x^2-y^2}$$

($x$, $y$ --- целые числа), является конечным.

проверьте:
Пусть имеется последовательность решений $(x_n,y_n):\frac{x_n^2-a}{x_n^2-y_n^2}=a$. Тогда отсюда следует, что обе последовательности неограниченны, значит, переупорядочив решения $x_n$, считаем, что $x_n\to +\infty$ (можно брать $x_n\geqslant 0$). $y_n$ - функция от $x_n$, значит и $y_n\to +\infty$.
Выразим $y_n$ асимптотически: $y_n=x_n\sqrt{\frac{k-1}{k}-\frac{a}{x_n^2}}=\sqrt{\frac{k-1}{k}}x_n+O(x_n^{-1})$. Поскольку решения - целые числа, то $t=\sqrt{\frac{k-1}{k}}\in\mathbb{Q}$: $k-1=kt^2$, $k$ свободно от квадратов, значит $1-\frac{1}{k}=t^2$, только если $k|1$. Перебираем $k=\pm 1$, получаем лишь $k=1$. Подставляем, видим, что решений нет.

[nnosipov]

Sonic86 в сообщении #540937 писал(а):

Выразим $y_n$ асимптотически: $y_n=x_n\sqrt{\frac{k-1}{k}-\frac{a}{x_n^2}}=\sqrt{\frac{k-1}{k}}x_n+O(x_n^{-1})$. Поскольку решения - целые числа, то $t=\sqrt{k-1}{k}\in\mathbb{Q}$

Последний переход не обоснован, да и неверен. Мы имеем, например, $F_{n+1}=(1+\sqrt{5})/2 \cdot F_n+O(F_n^{-1})$, где $F_n$ --- $n$-е число Фибоначчи. Но мы же отсюда не выводим, что $(1+\sqrt{5})/2$ --- рациональное число.

Нет, совсем просто доказать не получится. Здесь такой выбор: либо Пелль, либо прыгающий Виет. Хотя, по правде говоря, принципиальных отличий нет. Разница только в технических деталях.

[nnosipov]

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

В последней задаче было бы интересно также оценить через $a$ количество тех натуральных чисел, которые представимы в указанном виде.

Справедливо следующее утверждение: любое натуральное число, представимое в виде

$$ \frac{x^2-a}{x^2-y^2} $$

(переменные $x$, $y$ предполагаются целочисленными, $a$ --- фиксированное натуральное число, не являющееся точным квадратом), не превосходит $a$.
Хотелось бы увидеть какое-нибудь нестандартное доказательство этого утверждения.