Икс и игрек (задача с XXV всесоюзки)

[Xenia1996]

а) Найти 2 натуральных числа х и у таких, что $xy+x$ и $xy+y$ являются квадратами различных натуральных чисел.
б) Можно ли найти такие х и у в пределах от 988 до 1991?

(Попытка решения)

Пункт а) решила влёгкую: $x=1, y=8$. Пункт б) попытаюсь здесь:
Если х и у лежат в пределах от 988 до 1991, то наименьшее из чисел $xy+x$ и $xy+y$ (без ограничения общности, пусть это будет первое из них) не меньше, чем $988^2$, а значит расстояние до ближайшего квадрата превышает 1800. Но расстояние до ближайшего квадрата не должно быть больше $y-x$, а значит, не больше $1991-988=1003$.
Если я ничего не упустила, то приходим к противоречию. Если же упустила, пожалуйста, поправьте. Заранее благодарна!

[maxal]

Гораздо более интересная задача на ту же тему:

Доказать, что если оба числа $xy+x$ и $xy+y$ являются квадратами, где $x$ и $y$ - натуральные числа, то одно из чисел $x, y$ также является квадратом.

[ИСН]

... а другое - квадратом без единицы?

[maxal]

ИСН в сообщении #368972 писал(а):

... а другое - квадратом без единицы?

Ну а как иначе?

[neo66]

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

Гораздо более интересная задача на ту же тему:
Доказать, что если оба числа $xy+x$ и $xy+y$ являются квадратами, где $x$ и $y$ - натуральные числа, то одно из чисел $x, y$ также является квадратом.

Пусть:
$xy+x=m^2$
$xy+y=n^2$

Отсюда:
$\frac {m^2}{x} - \frac {n^2}{x+1}=1$

Это означает, что квадратичная форма $f$ над полем рациональных чисел $\mathbb{Q}$:
$f(a,b,c)=a^2 - xb^2+(x+1)c^2$ представляет ноль (т.е. существуют такие нетривиальные $a,b,c \in \mathbb{Q}$, что $f(a,b,c)=0$).

Значит она представляет ноль над любым полем р-адических чисел $\mathbb{Q}_p$.
Пусть $x$ и $x+1$ не квадраты и $p$ - простое число, входящее в разложение $x$ в нечетной степени. (Можно считать, что $p$ - не $2$. Иначе, вместо $x$ ,будем рассматривать $x+1$.)
Обозначим $-(x+1)$ через $q$. То есть, мы имеем квадратичную форму $a^2 - xb^2-qc^2$,
представляющую ноль над $\mathbb{Q}_p$. Но, символ Гильберта $(x,q)_p=(p,q)_p=-1$, так как $q$ взаимно просто с $p$ и не квадрат. Получаем противоречие с предположением. Другими словами: или $x$ или $x+1$ - квадрат.

Чуть более элементарно: мы хотим доказать, что, если $x$ и $q$ - не квадраты, то уравнение $f(a,b,c)=a^2 - xb^2-qc^2=0$ не имеет нетривиального решения в р-адических числах. Пусть оно имеет решение. Тогда, уравнение $a^2 - prb^2-qc^2=0$, где $r$ взаимно просто с $p$ тоже имеет решение. Несложный анализ показывает, что это не так.

[maxal]

neo66 в сообщении #377181 писал(а):

мы хотим доказать, что, если $x$ и $q$ - не квадраты, то уравнение $f(a,b,c)=a^2 - xb^2-qc^2=0$ не имеет нетривиального решения в р-адических числах.

Это неверное утверждение.
Контрпример: $x=2$, $q=7$. Соответствующее уравнение имеет решение даже в целых числах: $f(5,3,1)=5^2 - 2\cdot 3^2 - 7\cdot 1^2 = 0$.
Ищите у себя ошибку.

[neo66]

Ошибка в том, что символ Гильберта $(p,q)_p=-1$, если $q$ не является квадратичным вычетом по $mod(p)$, а не просто не квадратом. Так, что высокая наука пока не катит.

[juna]

Пусть $x=\alpha \cdot d^2$, где $\alpha$ свободно от квадратов, тогда из уравнения $x(y+1)=m^2$ следует $y+1=\alpha \cdot k^2$. Тогда из уравнения $y(x+1)=n^2$ следует $(\alpha \cdot k^2-1) \cdot (\alpha \cdot d^2 +1) = n^2$. (отсюда, кстати, совместным решением двух уравнений Пелля $\alpha \cdot k^2-1=t^2$, $\alpha \cdot d^2 +1=l^2$ находим все решения). Предположим, что $\alpha \cdot k^2-1=\beta \cdot \omega^2$, $\alpha \cdot d^2+1=\beta \cdot \pi^2$, где $\beta \not =1$ и свободно от квадратов. Тогда по теореме Лежандра из первого уравнения $\alpha$ - квадратичный вычет по модулю $\beta$, а из второго $- \alpha$ - квадратичный вычет по модулю $\beta$, что одновременно невозможно.

[neo66]

juna в сообщении #378871 писал(а):

Тогда по теореме Лежандра из первого уравнения $\alpha$ - квадратичный вычет по модулю $\beta$, а из второго $- \alpha$ - квадратичный вычет по модулю $\beta$, что одновременно невозможно.

$\alpha=1$, $\beta=5$.

[Sonic86]

Попытался решить систему $x(y+1)=(m+1)^2, y(x+1)=m^2$ обычными методами. Получилась пара решений:
1) $x=\frac{m^2}{y}-1, y=z^2, m=zl, l=a, z=2b-a, a^2-2b^2=1$
2) $x=\frac{m^2}{y}-1, y=2z^2, m=2zl, l=d, z=c-d, c^2-2d^2=1$
Причем мне совсем неочевидно, почему во втором решении$x$ или $y$ - квадрат (хотя это верно)

(Оффтоп)

наверное это какой-то неправильный метод

Могу также доказать, что $x,y$ являются суммой двух квадратов.
Доказал, что если система имеет решение при $x,y$ не квадратах, то существует решение у обеих обобщенных уравнениях Пелля $pa^2-qb^2=1$ и $qc^2-pd^2=1$, где $p,q$ оба являются суммой двух квадратов.

(Оффтоп)

Так что вопрос о существовании решений обобщенных уравнений Пелля $pa^2-qb^2=1$ стоит очень остро!

juna писал(а):

Тогда по теореме Лежандра из первого уравнения $\alpha$ - квадратичный вычет по модулю $\beta$, а из второго $- \alpha$ - квадратичный вычет по модулю $\beta$, что одновременно невозможно.

возможно, если, например, $\beta$ простое и $\beta \equiv 1 (4)$.

[juna]

neo66 в сообщении #378897 писал(а):

$\alpha=1$, $\beta=5$.

Неудачный контрпример, при $\alpha=1$ $x$ - как раз точный квадрат. Но Вы и Sonic86, конечно, правы.
Также теорема Лежандра дает критерий для рациональных решений, поэтому пара $(\alpha,\beta)=(13,17)$ не противоречит теореме Лежандра, но $13k^2-17\omega^2=1$ целых решений не имеет.
В общем, все что я написал, можно представить как переформулировку исходной задачи:
Если $\alpha\not = 1,\beta\not=1$ - свободны от квадратов, то одновременно уравнения $\alpha \cdot k^2-\beta\cdot\omega^2=1$, $\alpha \cdot d^2-\beta\cdot\pi^2=-1$ не могут иметь решения в целых числах.

[Sonic86]

сообщение отредактировано 03.05.2011, исправлены опечатки, но решение неверно!
Предположим, что существует решение, где $x,y$ оба не квадраты.
Делая подстановку $x=px_1^2, y=qy_1^2$, где $p,q$ свободны от квадратов и $p,q>1$, получаем, что оба уравнения $ps^2-qt^2=1$ и $qu^2-pv^2=1$ имеют решения, причем $\gcd (p,q)=1$
Рассмотрим уравнение $px^2-qy^2=1$ при $p,q>1$ ($x,y$ новые, не из системы сверху). Оно имеет решение тогда и только тогда, когда $1$ представимо квадратичной формой $px^2-qy^2$. Число $N$ представимо формой $ax^2+bxy+cy^2$ тогда и только тогда, когда существует унимодулярное преобразование координат $M = \left( \begin{array}{cc} \alpha & \beta \\ \gamma & \delta \end{array} \right)$, переводящее форму $ax^2+bxy+cy^2$ в форму $Nx^2+Bxy+Cy^2$, где $B^2 \equiv \Delta \pmod {4N}, 0 \leq B < 2N$, $C: B^2-4NC = \Delta$ (Бухштаб). Дискриминант формы $\Delta = 4pq>0$, $N=1$, тогда $B^2 \equiv 0 \pmod 4, 0 \leq B < 2$, т.е. $B=0$, откуда $C=-pq$.
Несложно доказать, что $px^2-qy^2$ переводится в форму $x^2-pqy^2$ преобразованием с матрицей $M$ тогда и только тогда, когда $(\exists \alpha, \gamma) p \alpha^2 - q \gamma^2=1$.
Предположим, что оба уравнения $ps^2-qt^2=1$ и $qu^2-pv^2=1$ имеют решения. Значит форма $px^2-qy^2$ переводится в $x^2-pqy^2$ преобразованием с унимодулярной матрицей $M_1$ и форма $qx^2-py^2$ переводится в $x^2-pqy^2$ преобразованием с унимодулярной матрицей $M_2$ (если $p=1 \vee q=1$ какие-либо 2 формы совпадают). Тогда существует унимодулярное преобразование с матрицей $M=M_2^{-1}M_1$ формы $px^2-qy^2$ в $qx^2-py^2$. Найдем его напрямую:

$$M:\left\{ \begin{array}{cc} x \to ax+by \\ y \to cx+dy \end{array}, ad-bc=1$$

такое, что

$$p(ax+by)^2-q(cx+dy)^2=qx^2-py^2 \Leftrightarrow \left\{ \begin{array}{ccc} pa^2-qc^2=q \\ pab=qcd \\ pb^2-qd^2=-p \end{array}$$

Поскольку $\gcd (p,q)=1$ и $p,q$ свободны от квадратов, то из 1-го уравнения получаем, что $q|a$, и аналогично из 3-го $p|d$. Подставляя $a=qa_1, d=pd_1$, получаем (с условием унимодулярности):

$$\left\{ \begin{array}{cccc} pqa_1^2-c^2=1 \\ a_1b=cd_1 \\ b^2-pqd_1^2=-1 \\ pqa_1d_1-bc=1 \end{array}$$

Из 1-го уравнения следует $\gcd(a_1,c)=1$. Берем 2-е и 4-е уравнения. Так как $a_1b=cd_1$ и $\gcd(a_1,c)=1$, то $a_1|d_1$ и по симметрии $a_1,d_1$ получаем $a_1=d_1, b=c$. Подставляя это в 1-е и 3-е уравнения, получаем:

$$\left\{ \begin{array}{cc} pqa_1^2-b^2=1 \\ b^2-pqa_1^2=-1 \end{array}$$

откуда $1=-1$, что невозможно.
! Вот тут как раз опечатка и сработала. На самом деле получилось $1=1$, так что пока никакого противоречия нету. Соответственно, дальше все неверно.
Таким образом, мы из предположения, что $x,y$ из данной оба не квадраты пришли к противоречию. Значит хотя бы одно из них квадрат.

[maxal]

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

получаем, что оба уравнения $ps^2-qt^2=1$ и $pu^2-qv^2=1$ имеют решения

Знак, случаем, не потеряли?

[Sonic86]

maxal писал(а):

Sonic86 писал(а):

получаем, что оба уравнения $ps^2-qt^2=1$ и $pu^2-qv^2=1$ имеют решения

Знак, случаем, не потеряли?

ой! прошу прощенья, потерял.

upd: знак исправлен 03.05.2011

[nnosipov]

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

Гораздо более интересная задача на ту же тему:

Доказать, что если оба числа $xy+x$ и $xy+y$ являются квадратами, где $x$ и $y$ - натуральные числа, то одно из чисел $x, y$ также является квадратом.

Вот решение этой задачи. Пусть $(x,y)$ --- наименьшая пара натуральных чисел $x<y$, которая удовлетворяет условию задачи и для которой утверждение задачи неверно. Положим $y=x+z$, где $z$ --- натуральное число. Имеем

$$ xy+x=x^2+xz+x=m^2, \quad xy+y=x^2+xz+x+z=(m+k)^2 $$

для некоторых натуральных чисел $m$, $k$. Отсюда $z=k(2m+k)=kl$, где $l=2m+k$. Значит,

$$ x^2+(kl+1)x=(l-k)^2/4, $$

и мы приходим к следующим формулам:

$$ x=\frac{-kl-1+\sqrt{(k^2+1)(l^2+1)}}{2}, \quad y=\frac{kl-1+\sqrt{(k^2+1)(l^2+1)}}{2}. $$

Положим $l_1=(2k^2+1)l-2k\sqrt{(k^2+1)(l^2+1)}$. Поскольку $l>k$, имеем

$$ -k<l_1<l-2k, $$

при этом $l_1 \neq 0$. Кроме того,

$$ \sqrt{(k^2+1)(l_1^2+1)}=(2k^2+1)\sqrt{(k^2+1)(l^2+1)}-2k(k^2+1)l. $$

Пусть

$$ x_1=\frac{-kl_1-1+\sqrt{(k^2+1)(l_1^2+1)}}{2}, \quad y_1=\frac{kl_1-1+\sqrt{(k^2+1)(l_1^2+1)}}{2}. $$

Можно проверить, что

$$ x_1=\frac{(l_1-k)^2}{(l+k)^2}\,y, \quad y_1=x. $$

Если $l_1>0$, $l_1 \neq k$, то новая пара $(x_1,y_1)$ натуральных чисел обладает теми же свойствами, что и исходная пара $(x,y)$. Но $x_1<y_1=x<y$, и мы приходим к противоречию. При $l_1=k$ имеем $x=y_1=1$, что также невозможно. Наконец, если $l_1<0$, то к противоречию приводит рассмотрение пары $(y_1,x_1)=(x,x_1)$, поскольку

$$ x_1=\frac{k|l_1|-1+\sqrt{(k^2+1)(|l_1|^2+1)}}{2}<y $$

ввиду неравенств $|l_1|<k<l$.

to maxal: откуда задача? Очень похоже на замшелую классику.