Диофантовы уравнения II: спуск и прыжок Виета

Если \(x^2=2y^2\), то \(x^2\) чётно, значит \(x=2u\). Тогда \(4u^2=2y^2\), откуда \(y^2=2u^2\), и \(y\) тоже чётно: \(y=2v\). Получаем \(u^2=2v^2\), то есть меньшее положительное решение. Бесконечный спуск невозможен.

Из \(x^2=5y^2\) следует \(5\mid x^2\), значит \(x=5u\). Тогда \(25u^2=5y^2\), то есть \(y^2=5u^2\), и \(5\mid y\). Положив \(y=5v\), получаем \(u^2=5v^2\), меньшее решение. Это невозможно.

По модулю \(3\): \(x^2+y^2\equiv 0\). Это возможно только при \(x\equiv y\equiv 0\pmod 3\). Тогда \(9\mid x^2+y^2\), значит \(9\mid 3z^2\), и \(3\mid z\). Делим \(x,y,z\) на \(3\) и получаем меньшее ненулевое решение. Противоречие.

Квадраты по модулю \(7\) равны \(0,1,2,4\). Сумма двух таких остатков может быть \(0\) по модулю \(7\) только если оба остатка равны \(0\). Значит \(7\mid x\) и \(7\mid y\). Тогда \(49\mid x^2+y^2\), откуда \(7\mid z\). Деление всех переменных на \(7\) даёт меньшее решение, что невозможно.

Правая часть делится на \(4\). Квадрат по модулю \(4\) равен \(0\) или \(1\). Чтобы \(x^2+y^2\equiv 0\pmod 4\), оба квадрата должны быть \(0\), значит \(x,y\) чётны. Тогда \(4\mid x^2+y^2\) и после деления получаем \(z^2=(x/2)^2+(y/2)^2\), но главное уже достаточно: \(x,y\) имеют общий делитель \(2\), поэтому решение не может быть примитивным.

Пусть \(x\le y\) и решение минимально. Как квадратное относительно \(y\), уравнение имеет вид \(Y^2-4xY+x^2+1=0\). Второй корень \(y'=4x-y=\frac{x^2+1}{y}\) положителен и целый. Так как \(y\ge x\), \(y'\le x+\frac{1}{x}\), значит \(y'\le x\). Равенство \(y'=x\) привело бы к \(y=3x\), а тогда \(x^2+9x^2+1=12x^2\), то есть \(2x^2=1\), невозможно. Получаем меньшее решение. При \(x=1\) дискриминант \(16-8=8\) не квадрат. Противоречие.

Пусть \(x\le y\) и решение минимально. Для \(x=1\) уравнение \(y^2-3y+3=0\) не имеет целых корней; для \(x=2\) получаем \(y^2-6y+6=0\), тоже нет целых корней. При \(x\ge 3\) второй корень \(y'=3x-y=\frac{x^2+2}{y}\) положителен и целый. Так как \(y\ge x\), \(y'\le x+\frac{2}{x}

Пусть \(x\le y\). При \(x=1\) получаем \(y^2-3y+2=0\), откуда \(y=1\) или \(2\). Для \(x>1\) второй корень равен \(y'=3x-y=\frac{x^2+1}{y}\). Он положителен и целый. Так как \(y\ge x\), \(y'\le x+\frac{1}{x}1\) имеем \(0

Запишем \(Y^2-mxY+x^2+c=0\). Один корень равен \(y\). По формуле Виета сумма корней равна \(mx\), значит второй корень \(y'=mx-y\). Так как коэффициенты целые и \(y'\) задан положительным целым числом, подстановка второго корня снова обращает квадратный трёхчлен в ноль. Поэтому \(x^2+(y')^2+c=mxy'\).

Пусть \(x\le y\) и решение минимально по сумме. При \(x=1\) получаем \(y^2-ky+2=0\). Его дискриминант \(k^2-8\) не является квадратом: если \(k^2-8=t^2\), то \((k-t)(k+t)=8\), что при \(k\ge 4\) невозможно. Пусть \(x\ge 2\). Второй корень \(y'=kx-y=\frac{x^2+1}{y}\) положителен и целый. Так как \(y\ge x\), \(y'\le x+\frac{1}{x}

Рассмотрим \(Z^2-3xyZ+x^2+y^2=0\). Один корень \(z\), второй \(z'=3xy-z\). Произведение корней равно \(x^2+y^2>0\), поэтому \(zz'>0\); так как \(z>0\), имеем \(z'>0\). По формуле Виета второй корень удовлетворяет тому же квадратному уравнению, значит \(x^2+y^2+(z')^2=3xyz'\).

Четвёртые степени по модулю \(7\) равны \(0,1,2,4\). Сумма двух таких остатков может быть \(0\pmod 7\) только в случае \(0+0\). Поэтому из \(7\mid x^4+y^4\) следует \(7\mid x\) и \(7\mid y\). Пусть \(x=7x_1\), \(y=7y_1\). Тогда левая часть делится на \(7^4\), значит \(7z^2\) делится на \(7^4\), то есть \(z^2\) делится на \(7^3\). Так как показатель в квадрате чётный, отсюда \(7^2\mid z\); положим \(z=49z_1\). Подставляя, получаем \(7^4(x_1^4+y_1^4)=7\cdot 7^4 z_1^2\), то есть \(x_1^4+y_1^4=7z_1^2\). Получено меньшее положительное решение. Бесконечный спуск невозможен, значит исходных решений нет.

Если \(p\nmid y\), то \((xy^{-1})^2\equiv -1\pmod p\). Возводим обе части в степень \(\frac{p-1}{2}\). Слева получается \(1\), справа \((-1)^{(p-1)/2}=-1\), так как \(p\equiv 3\pmod 4\). Противоречие. Значит \(p\mid y\), а тогда из \(p\mid x^2+y^2\) следует \(p\mid x\).

Так как \(11\equiv 3\pmod 4\) и \(11\mid x^2+y^2\), получаем \(11\mid x\) и \(11\mid y\). Тогда \(121\mid x^2+y^2=11z^2\), значит \(11\mid z\). Делим все переменные на \(11\) и получаем меньшее ненулевое решение. Бесконечный спуск невозможен.

Из уравнения следует \(p\mid x^2+y^2\). По лемме о простых \(3\pmod 4\) получаем \(p\mid x\) и \(p\mid y\). Тогда \(p^2\mid x^2+y^2=pz^2\), значит \(p\mid z^2\), то есть \(p\mid z\). Делим \(x,y,z\) на \(p\) и получаем меньшее ненулевое решение того же уравнения. Это даёт бесконечный спуск, невозможный в положительных целых числах.

Из \(x^4+y^4\equiv 0\pmod 3\) следует, что \(x\) и \(y\) делятся на \(3\). Тогда левая часть делится на \(81\), значит \(3z^4\) делится на \(81\), и \(z\) делится на \(3\). Деление \(x,y,z\) на \(3\) сохраняет уравнение и даёт меньшее ненулевое решение. Противоречие.

Четвёртая степень по модулю \(5\) равна \(0\) или \(1\). Поэтому из \(x^4+y^4\equiv 0\pmod 5\) следует \(5\mid x\) и \(5\mid y\). Тогда \(5^4\mid x^4+y^4=5z^4\), значит \(5^3\mid z^4\), и потому \(5\mid z\). Делим все переменные на \(5\) и получаем меньшее ненулевое решение того же уравнения. Противоречие.

Квадраты по модулю \(5\): \(0,1,4\). Тогда \(2y^2\) имеет остатки \(0,2,3\). Сумма \(x^2+2y^2\) может быть \(0\pmod 5\) только если оба слагаемых имеют остаток \(0\). Значит \(5\mid x,y\). Тогда \(25\mid x^2+2y^2=5z^2\), следовательно \(5\mid z\). Деление всех переменных на \(5\) даёт меньшее решение того же уравнения. Противоречие.

По задаче 8 все решения — соседние члены последовательности \(1,1,2,5,13,34,89,233,\ldots\), где \(a_{n+1}=3a_n-a_{n-1}\). Ограничение \(x+y\le 150\) оставляет соседние пары \((1,1),(1,2),(2,5),(5,13),(13,34),(34,89)\) и их перестановки. Пара \((89,233)\) уже имеет сумму больше \(150\).

Пусть \(x\le y\). При \(x=1\) получаем \(y^2-4y+4=0\), значит \(y=2\). При \(x=2\) получаем \(y^2-8y+7=0\), то есть \(y=1\) или \(7\); это согласуется с соседними членами будущей последовательности. При \(x=3\) дискриминант \(144-48=96\) не квадрат. Для \(x\ge 4\) второй корень равен \(y'=4x-y=\frac{x^2+3}{y}\), он положителен и целый. Так как \(y\ge x\), \(y'\le x+\frac{3}{x}

Обратный ход: если \((a,b)\) — решение, то \((b,4b-a)\) тоже решение. Начиная с \((1,2)\), получаем последовательность \(a_0=1\), \(a_1=2\), \(a_{n+1}=4a_n-a_{n-1}\). Все решения: \((a_n,a_{n+1})\) и перестановки, \(n\ge 0\).