Точные квадраты и делимость

[nnosipov]

Натуральные числа $m$ и $n$ таковы, что оба числа $mn+1$ и $mn+n+1$ являются точными квадратами. Докажите, что $n$ делится на $8(2m+1)$.

PS. Еще одна несложная задача, для которой есть стандартный путь решения. Здесь было бы интересно найти более короткое решение, не апеллирующее к лишним сущностям.

[Andrey A]

Обозначим $mn+n+1=x^2,mn+1=y^2.$ Тогда $m+1-m=\dfrac{x^2-1}{n}-\dfrac{y^2-1}{n}=1,$ откуда $n=x^2-y^2, \dfrac{m+1}{m}=\dfrac{x^2-1}{y^2-1}.$ Решения выражаются дробями $\dfrac{x_0=1}{y_0=1},\dfrac{x_1=4m+3}{y_1=4m+1},\dfrac{x_{k+1}=(4m+2)x_k-x_{k-1}}{y_{k+1}=(4m+2)y_k-y_{k-1}}.$
$n_1=x_1^2-y_1^2=(4m+3)^2-(4m+1)^2=8(2m+1).$
$n_{k+1}=x_{k+1}^2-y_{k+1}^2$, и нужное требование выполняется из соображений сравнимости. Если что, можно подробней. А по первому впечатлению годится только $(m=0,n=l^2-1).$ Да, симпатично. Насчет лишних сущностей не уверен что удалось.

[nnosipov]

Andrey A в сообщении #1450541 писал(а):

Если что, можно подробней.

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

Собственно, это и есть стандартный путь. Можно использовать технику цепных дробей или свести дело к (параметрическому) уравнению Пелля. Но вдруг есть какое-нибудь хитрое тождество, откуда требуемая делимость следует более-менее сразу? Или еще что-нибудь в этом роде. В общем, хочется какого-то чуда.

[Andrey A]

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

Или еще что-нибудь в этом роде. В общем, хочется какого-то чуда.

Не знаю. Первое-то решение надо иметь как минимум. В данном случае $8(2m+1)=(4m+3)^2-(4m+1)^2$ можно просто подобрать и увидеть, что квадраты отвечают нужным требованиям, но теорему об интуиции еще никто не сформулировал ) И почему, собственно, цепными дробями – не сразу? Может быть, это и есть нужное чудо, причем мало изученное.

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

... обоснование того, что указанные дроби дают все решения.

Сначала о делимости. $x_{k+1}^2-y_{k+1}^2=\left ( (4m+2)x_k-x_{k-1} \right )^2-\left ( (4m+2)y_k-y_{k-1} \right )^2=$ $\left ( (4m+2)(x_k+y_k)-(x_{k-1}+y_{k-1}) \right )\left ( (4m+2)(x_k-y_k)-(x_{k-1}-y_{k-1}) \right )=$
$=8(2m+1)^2 \dfrac{x_k^2-y_k^2}{2}-8(2m+1)$ $\dfrac{(x_{k-1}+y_{k-1})(x_k-y_k)+(x_k+y_k)(x_{k-1}-y_{k-1})}{4}+(x_{k-1}^2-y_{k-1}^2).$
Все элементы дробей последовательности есть нечетные числа, поэтому дроби в последнем выражении сократимы на цело. Из делимости $n_{k-1}$ следует делимость $n_{k+1}$, ну а для $k=0,1$ выполняется. Можно это как-то быстрее, конечно. А вот полноту решения могу обосновать только наблюдениями, связанными с темой https://dxdy.ru/topic33345.html. Количество серий, выражающих решение уравнения $\dfrac{a}{b}=\dfrac{x^2-1}{y^2-1}$ не превышает количества $X^2 \equiv 1 \mod (a-b), 0<X \leqslant a-b.$ В данном случае такой квадрат всего один.

[nnosipov]

Andrey A в сообщении #1450624 писал(а):

А вот полноту решения могу обосновать только наблюдениями, связанными с темой topic33345.html.

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

[Andrey A]

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

... а строгое доказательство это все же нечто другое.

Конечно. Нет, не могу.

[Andrey A]

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

Тот текст очень трудно переварить.

Я в начале темы действительно смутно догадывался о некоторых вещах, но к последнему посту всё упростилось. Всё ведь сводится к уравнению $X^2-MY^2=C$. Процесс совершенно аналогичный стандартному, только дроби используются с шагом не $p_nq_{n-1}-p_{n-1}q_n=\pm 1$, а $p_nq_{n-1}-p_{n-1}q_n=\pm C$ и остатки вида $p^2-Mq^2$ тоже задаются кратные $C$. Раскладывается при этом не $\sqrt{M}$, а некоторая квадратичная иррациональность, которая определена однозначно, как и начальные условия процесса. А вот условия разрешимости уравнения — да, вопрос сложный, но в любом случае получаем наименьшие вычеты кратные $C$. И доказательства. Это тоже не моей части.

[Shadow]

В одном пукте я не особо уверен, хотя кажется должно быть так.

$\begin{cases} mn+1=x^2\\mn+n+1=y^2\end{cases}\Rightarrow \begin{cases} mn+1=x^2\\n=y^2-x^2\end{cases}$

Класическая замена $y=\dfrac{a+b}{2},\;x=\dfrac{a-b}{2}$, получаем

$n=ab$

$mab+1=\dfrac{(a-b)^2}{4}$, откуда

$a^2-2(2m+1)ab+b^2-4=0$

Скачки Виета туда-сюда, $b=2,a=4(2m+1)$ - минимальное решение в натуральных числах и т.д.

Тут, конечно главный вопрос: Какая гарантия, что при некотором $m$ не найдется решение между $2$ и $4(2m+1)$ со всеми вытекающими...

В целых неотрицательных, серию можно начать с нуля, благо ноль в этой же серии, т.е. для любого $m$ решениями являются соседние члены последовательности

$0,2,4(2m+1),\cdots$

и если между вторым и третьим членом существует решение, то должно существовать и между 0 и 2, а 1 не является решением для любого $m$
Вот тут...полной уверености нет.

[nnosipov]

Shadow в сообщении #1450819 писал(а):

Вот тут...полной уверености нет.

Полагаю, все там можно довести до кондиции, т.е. до абсолютно строгого рассуждения.

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

[Andrey A]

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

Вот для этой конкретной задачи у Вас есть ощущение, что Вы все можете строго доказать?

Andrey A в сообщении #1450631 писал(а):

Нет, не могу.

Могу свести уравнение $\dfrac{m+1}{m}=\dfrac{x^2-1}{y^2-1}$ к уравнению $\left ( (m+1)y^2+mx^2\right )^2-\left ( (2m+1)^2-1 \right )(xy)^2=1$, а это уже кто-то доказал до меня.

Исправлено.

Вернее так: $\dfrac{m+1}{m}=\dfrac{x^2-1}{y^2-1}$ сводится к $(m+1)y^2-mx^2=1$, а оно к нечетным решениям Пелля. В любом случае других решений не видно.

[Shadow]

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

Полагаю, все там можно довести до кондиции, т.е. до абсолютно строгого рассуждения.

Думаю, совершенно стандартное рассуждение для минимального елемента (для любой серии решений) используя Vieta jumping.

Пусть минимальное решение (для гипотетически другой серии) $(a_1,b)$, причем $a_1 \ge b$

Из $a_1a_2=b^2-4$, следует $a_2<b$, и пара $(a_2,b)$ не будет решением в неотрицательных числах только если $a_2<0$, т.е. $b^2-4<0$

[Andrey A]

Andrey A в сообщении #1450826 писал(а):

$\dfrac{m+1}{m}=\dfrac{x^2-1}{y^2-1}$ сводится к $(m+1)y^2-mx^2=1$, а оно к нечетным решениям... уравнения $\left ( (m+1)y^2+mx^2\right )^2-\left ( (2m+1)^2-1 \right )(xy)^2=1$.

Можно добавить, что из четных решений Пелля (а больше неоткуда) следует серия иррациональных в общем случае пар $x,y:\ \dfrac{x}{y}=\dfrac{x_1=0}{y_1=\frac{1}{\sqrt{m+1}}},\dfrac{x_2=2\sqrt{m+1}}{y_2=\frac{2m+1}{\sqrt{m+1}}},...,$ $\dfrac{x_{k+1}=(4m+2)x_k-x_{k-1}}{y_{k+1}=(4m+2)y_k-y_{k-1}}.$ Подстановка $m \rightarrow l^2-1$ ведет к серии рациональных $x,y:\ \dfrac{x}{y}=\dfrac{x_1=0}{y_1=1/l},\dfrac{x_2=2l}{y_2=(2l^2-1)/l},...,\dfrac{x_{k+1}=(4l^2-2)x_k-x_{k-1}}{y_{k+1}=(4l^2-2)y_k-y_{k-1}}.$ Числители дробей, выражающих значения $y$, взятые по $\mod l$, образуют последовательность с периодом $(1,-1)$. Поэтому целое $y$ возможно только при $l=1$, но тогда $m=l^2-1=0$, что выходит за рамки условия задачи. Значит, других решений нет. Заодно удалось доказать, что уравнение $(m+1)y^2-mx^2=1$ имеет единственную серию решений.

[nnosipov]

Andrey A в сообщении #1451197 писал(а):

Заодно удалось доказать, что уравнение $(m+1)y^2-mx^2=1$ имеет единственную серию решений.

Вот это-то и доказывается абсолютно стандартным способом. Домножив на $m$, получим уравнение

$$u^2-(m^2+m)v^2=-m, \eqno(*)$$

где $u=mx$, $v=y$. Уравнение $(*)$ имеет единственную серию решений (в натуральных числах)

$$u+v\sqrt{m^2+m}=(-m+\sqrt{m^2+m})(2m+1+2\sqrt{m^2+m})^k,\eqno(**)$$

где $k$ --- натуральное число. Это легко следует из теоремы о базисных решениях уравнения Пелля

$$x^2-Ay^2=B,$$

которую я неоднократно здесь приводил (единожды доказав этот общий результат, мы получаем простой --- алгоритмический --- метод исследовать параметрические уравнения типа $(*)$). Поскольку в серии решений $(**)$ имеет место свойство $u \equiv 0 \pmod{m}$ (что легко устанавливается индукцией по $k$), приходим к тому, что и уравнение

$$(m+1)y^2-mx^2=1$$

имеет единственную серию решений, которая получается из $(**)$ и после упрощения может быть записана в виде

$$y\sqrt{m+1}+x\sqrt{m}=(\sqrt{m+1}+\sqrt{m})^{2l-1},$$

где $l$ --- натуральное число.

[rightways]

Shadow в сообщении #1450819 писал(а):

В одном пукте я не особо уверен, хотя кажется должно быть так.

$\begin{cases} mn+1=x^2\\mn+n+1=y^2\end{cases}\Rightarrow \begin{cases} mn+1=x^2\\n=y^2-x^2\end{cases}$

Класическая замена $y=\dfrac{a+b}{2},\;x=\dfrac{a-b}{2}$, получаем

$n=ab$

$mab+1=\dfrac{(a-b)^2}{4}$, откуда

$a^2-2(2m+1)ab+b^2-4=0$

Скачки Виета туда-сюда, $b=2,a=4(2m+1)$ - минимальное решение в натуральных числах и т.д.

Тут, конечно главный вопрос: Какая гарантия, что при некотором $m$ не найдется решение между $2$ и $4(2m+1)$ со всеми вытекающими...

В целых неотрицательных, серию можно начать с нуля, благо ноль в этой же серии, т.е. для любого $m$ решениями являются соседние члены последовательности

$0,2,4(2m+1),\cdots$

и если между вторым и третьим членом существует решение, то должно существовать и между 0 и 2, а 1 не является решением для любого $m$
Вот тут...полной уверености нет.

Тут легче доказать что либо $a$ либо $b$ делится на 2m+1.

По Виета $a_1+a=2(2m+1)b$
Поэтому если $a$ не делится на $2m+1$ . То и $a_1$ не делится. Отсюда и спуск и решение задачи выходит.

Вопрос:
А откуда можно узнать что именно $n$ делится на $2m+1$?. Как находить такой вывод?

[Shadow]

rightways в сообщении #1456266 писал(а):

Тут легче доказать что либо $a$ либо $b$ делится на 2m+1.

rightways в сообщении #1456266 писал(а):

Вопрос:
А откуда можно узнать что именно $n$ делится на $2m+1$?. Как находить такой вывод?

Shadow в сообщении #1450819 писал(а):

$n=ab$