задача на уравнение Пелля.

[N1508]

(Тут размещено решение)

$A=n^{2}+c$ выделяем ближайший полный квадрат - $n$ - наибольшее число, квадрат которого меньше заданного (A).
Пусть $x=2n/c$
$y^{2} = Ax^{2}+1$. Тогда:
$y^{2}=(n^{2}+c)(2n/c)^{2} +1$
Раскрываем скобки:
$y^{2}=(2n^{2}/c)^{2}+2(2n^{2}/c) +1= (2n^{2}/c+1)^{2} $
если $x=2n/c$ - целое, то и $x=2n^{2}/c$ тоже целое. Значит $x$ и $y$ целые - это нетривиальное решение.
Остается для нашего случая доказать, что в нашем случае $A=n^{2}+c$ имеет место: $c$ - делитель $n$

[nnosipov]

N1508
Ваше утверждение можно сформулировать так. Пусть $n$ и $c$ --- такие натуральные числа, что число $2n/c$ является целым. Положим $A=n^2+c$. Тогда пара чисел $(2n^2/c+1,2n/c)$ является минимальным решением уравнения Пелля $x^2-Ay^2=1$. (Иными словами, я бы подчеркнул факт минимальности.)

[N1508]

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

N1508
Ваше утверждение можно сформулировать так. Пусть $n$ и $c$ --- такие натуральные числа, что число $2n/c$ является целым. Положим $A=n^2+c$. Тогда пара чисел $(2n^2/c+1,2n/c)$ является минимальным решением уравнения Пелля $x^2-Ay^2=1$. (Иными словами, я бы подчеркнул факт минимальности.)

И опять согласен и опять почти. Есть там маленькая "запятая".
Для завершения темы я бы мог дать здесь "мой вариант" более полного и более строгого описания всех частных случаев решения уравнения Пелля.
Я не знаю, насколько здесь это было бы уместно, поэтому, чтобы не утомлять участников форума, обозначу только несколько моментов:
1. Любое $A$ можно разложить на $A=n^2 \pm c$. B формуле следует брать модуль $|2n/c|$
2. Для некоторых $A$ значение $2n/c$ является нетривиальным решением.
3. Факт того, что решения по п.2 являются наименьшими не очевиден и требует доказательства. Хотя, мне кажется, это было бы нетрудно сделать.
4. По поводу "наименьшее" есть исключение. Конкретно при $c = -1$. В этом случае наименьшее решение - единица, а $2n$ тоже решение, но строго следующее после единицы по возрастанию (из бесконечного количества решений).
5. Есть еще "частные решения", не укладывающиеся в "предложенную" формулу (назвать "мою формулу" было бы нескромно).

И еще, пользуясь случаем..

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

Окей, давайте пообсуждаем. Первое, о чем я подумал: не поискать ли для Вашего $A$ представление в виде $t^2d^2+t$ или $t^2d^2+2t$. Для таких $A$ минимальное решение уравнения Пелля $x^2-Ay^2=1$ выписывается в явном виде. Вы этот трюк имели в виду?

Ваши примеры полностью описываются предложенной формулой: $n=td; c=t; n=td; c=2t$.
Я, когда Вам отвечал "почти", - имел ввиду, что формула охватывает и Ваши примеры и еще многие другие.
В принципе, если позаботиться, чтобы $2n/c$ было целым, можно предложить и другие варианты для получения решений "в явном виде". Но суть их все те же
$2n/c$ в том или ином виде.

[nnosipov]

N1508 в сообщении #1427432 писал(а):

3. Факт того, что решения по п.2 являются наименьшими не очевиден и требует доказательства. Хотя, мне кажется, это было бы нетрудно сделать.

Да.

N1508 в сообщении #1427432 писал(а):

4. По поводу "наименьшее" есть исключение. Конкретно при $c = -1$.

Да, но это единственное исключение.

N1508 в сообщении #1427432 писал(а):

5. Есть еще "частные решения", не укладывающиеся в "предложенную" формулу

Есть, например $A=n^2 \pm 4$, где $n$ нечётно.

N1508 в сообщении #1427432 писал(а):

Я, когда Вам отвечал "почти", - имел ввиду, что формула охватывает и Ваши примеры и еще многие другие.

Что за "многие другие"? Мои примеры и Ваша формула эквивалентны (в том смысле, что описывают одно и то же множество значений $A$).

N1508 в сообщении #1427432 писал(а):

В принципе, если позаботиться, чтобы $2n/c$ было целым, можно предложить и другие варианты для получения решений "в явном виде".

Можно, но зачем? Мы знаем минимальное решение, а все остальные решения получаются из минимального понятно как.

[N1508]

Согласен с Вами во всем, но отмечу, на всякий случай.

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

Есть, например $A=n^2 \pm 4$, где $n$ нечётно.

У меня есть "явная форма" при $c=4$ и для нечетного $n$.
А также "явная форма" и для $c=2n-3$ при четном и нечетном $n$. Хотя, согласен, это уже "вид сбоку", конечно.

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

Что за "многие другие"? Мои примеры и Ваша формула эквивалентны (в том смысле, что описывают одно и то же множество значений $A$).

Не сочтите за буквоедство, просто в порядке уточнения...
Ваше множество - это $с =1, 2$.
Мое множество - это $с =1, 2, 4, n, 2n$. Согласен, в принципе, что это почти одно и то же, если учесть еще знак $\pm$.

Спасибо всем за обсуждение!
Отдельное спасибо nnosipov!
Подскажите, если это не трудно, где все-таки это можно посмотреть в теории, я этого всего не нашел, хотя искал долго и, вроде бы, везде.
Пришлось смотреть и классические учебники, вроде Бухштаба и труды Бугаенко и к иностранцам пытался "заглянуть". Не нашел явных упоминаний о "частных решениях". Или я все же "просмотрел"? Так получилось, что мы с сыном писали программу (вернее я немного помогал ему работать над алгоритмом, а он писал программу) и я пытался ее оптимизировать с точки зрения аналитики. И эти "частные случаи" серьезно помогли в написании программы.
Программа получилась на мой взгляд, в итоге неплохая. Но надо было при описании алгоритма дать ссылки в теоретической части. "Присваивать" формулу не хотелось. И поиски затянулись настолько, что в итоге сыну уже не до того. Олимпиады на носу...
А меня "заело". Хочется завершить труд.
Поэтому буду признателен за ссылку (ссылки).

[nnosipov]

N1508, пожалуйста.

Кроме Бухштаба, можно посмотреть еще: Венков Б.А. Элементарная теория чисел. М.-Л.: Гл. ред. общетехн. и техно-теорет. лит., 1937. (Несмотря на название, книга не очень элементарна, но все же.)

На английском гораздо больше литературы. Например:
1. Barbeau E.J. Pell’s equation. New York: Springer-Verlag, 2003.
2. Andreescu T., Andrica D. Quadratic diophantine equations. New York: Springer, 2015.
3. Jacobson J., Williams H.C. Solving the Pell equation. New-York: Springer, 2009.
4. W. Sierpinski. Elementary Theory of Numbers. 1988.

Кроме [3], эти книги более-менее элементарны. В первую очередь загляните в книгу Серпинского, там есть раздел, посвященный уравнению Пелля (гл. II, параграф 17), а также раздел, посвященный непрерывным дробям (гл. VIII).

[yk2ru]

Если домножить уравнение на $2\cdot19$ , то получим уравнение

$$38y^2 = 38B^2x^2 + C^2x^2 + 38$$

Не ошибся ли?

[N1508]

Не понятно о чем речь. Можно пояснить, что такое $B$ и $C$?

[yk2ru]

$$A = {(2\cdot3\cdot19)^{115}}^{116} + 2\cdot3^2\cdot19^3$$

$$38A = 38\cdot{(2\cdot3\cdot19)^{115}}^{116} + 2^2\cdot3^2\cdot19^4$$

$$38A = 38B^2 +C^2$$

[N1508]

Надо лишь показать, что $c$ является делителем числа $n$
Тогда $2n/c$ - целое число. $n^2=(2\cdot3\cdot19)^{2t}; c = 2\cdot3^2\cdot19^3$ Этого достаточно.

[N1508]

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

N1508Кроме Бухштаба, можно посмотреть еще: ...

Этих авторов, как мне кажется, "мой" вопрос не интересовал.
Читать их тяжело, но там точно нет "той самой" формулы.
Я еще кое-что нашел у Эвина и Камнева, но и там лишь намеки и "крохи" из того, что искал я.
Цепные дроби, как мне кажется, достаточно полно изложены у Арнольда. Глубже я не лез.
У иностранцев тоже нет целенаправленного поиска частных решений. Но много интересного для себя я нашел в работе "EVEN AND ODD PERIODS IN CONTINUED FRACTIONS OF SQUARE ROOTS P."

По поводу маленьких "почти":

N1508 в сообщении #1427450 писал(а):

У меня есть "явная форма" при $c=4$ и для нечетного $n$.
А также "явная форма" и для $c=2n-3$ при четном и нечетном $n$.

Вот они:

$A = n^2 +c; c = 4; n=2k+1; 2n/c$ - не целое, но "есть явная форма":
$x_0=n(An^2+3)/2$

И для $c=2n-3$
$A = n^2 +c; c = 2n - 3; 2n/c$ - не целое, но "есть явная форма":

при четном $n$: $x_0=n/2+n$
при нечетном $n$: $x_0=(n^2+1)/2$

Эти формулы легко проверить. Но выводом или доказательством утомлять не буду .

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

[nnosipov]

N1508 в сообщении #1427571 писал(а):

И для $c=2n-3$
$A = n^2 +c; c = 2n - 3; 2n/c$ - не целое, но "есть явная форма":

при четном $n$: $x_0=n/2+n$
при нечетном $n$: $x_0=(n^2+1)/2$

Заменив $n+1$ на $n$, получим $A=n^2-4$.

N1508 в сообщении #1427571 писал(а):

Читать их тяжело, но там точно нет "той самой" формулы.

Ничего не поделаешь, это типично для занятий математикой. Нужный результат может быть скрыт в более общей (более глубокой) постановке задачи. Иными словами, его нужно выискивать, внимательно вчитываясь в текст. Если "та самая" формула --- это вот это утверждение:

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

Пусть $n$ и $c$ --- такие натуральные числа, что число $2n/c$ является целым. Положим $A=n^2+c$. Тогда пара чисел $(2n^2/c+1,2n/c)$ является минимальным решением уравнения Пелля $x^2-Ay^2=1$.

то его можно найти у Серпинского в следующем виде (см. стр. 322): "Hence we conclude that in order that for a natural number $D$ the number $\sqrt{D}$ should have a representation as a simple continued fraction with a period consisting of two terms it is necessary and sufficient that $D = a^2 +k$, where $k$ is a divisor greater than $1$ of number $2a$." Кстати, в том виде, в котором я сформулировал утверждение, оно есть в одной свежей методичке по уравнениям Пелля, которую мне дали почитать. В общем, это утверждение вполне можно считать фольклором.

N1508 в сообщении #1427571 писал(а):

А в литературе ничего подобного я так и не нашел.

Настоятельно рекомендую прочитать параграф 4 главы VIII книги Серпинского (и заглянуть в параграф 5, чтобы понять, как связаны цепные дроби с уравнением Пелля). Обратите внимание, например, на формулы вверху стр. 327: из них можно получить новые "частные" решения. И вообще, попробуйте взглянуть на задачу в постановке Серпинского, это более продвинутый взгляд.

N1508 в сообщении #1427571 писал(а):

Этих авторов, как мне кажется, "мой" вопрос не интересовал.

Конечно, интересовал, только, возможно, в другой постановке.

[N1508]

Соглашусь по всем пунктам. Без возражений.
Получил ответы на все вопросы.
Тему для себя считаю исчерпанной.