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

Если число чётно, \(n=2k\), то \(n^2=4k^2\), а \(k^2\pmod4\) равно \(0\) или \(1\), поэтому получаем \(0\) или \(4\). Если число нечётно, прямой вид \(n=2k+1\) даёт \(n^2=4k(k+1)+1\), а \(k(k+1)\) чётно, значит \(n^2\equiv1\) или \(9\pmod{16}\). Итак, возможны \(0,1,4,9\).

Квадрат по модулю \(4\) равен \(0\) или \(1\). Значит, сумма двух квадратов по модулю \(4\) может быть только \(0,1,2\). Правая часть имеет остаток \(3\), противоречие.

Для \(n\equiv0,1,2,3,4,5,6\pmod7\) выражение \(n^2+n+1\) даёт остатки \(1,3,0,6,0,3,1\). Поэтому делимость на \(7\) выполнена ровно при \(n\equiv2\) или \(n\equiv4\pmod7\).

Нужно \(n^2\equiv-1\equiv4\pmod5\). Это происходит при \(n\equiv2\) или \(n\equiv3\pmod5\).

Достаточно проверить остатки \(0,1,\ldots,9\). Их квадраты по модулю \(10\) равны \(0,1,4,9,6,5,6,9,4,1\). Остатков \(2,3,7,8\) среди них нет.

Квадраты \(0^2,1^2,\ldots,6^2\) по модулю \(13\) дают \(0,1,4,9,3,12,10\). Значит, \(x\equiv5\) или \(x\equiv-5\equiv8\pmod{13}\).

Сумма двух элементов из \(\{0,1,4\}\) по модулю \(8\) может быть \(0,1,2,4,5\). Остаток \(7\) невозможен. Правая часть равна \(7\pmod8\), значит решений нет.

По модулю \(8\) каждый квадрат равен \(0,1\) или \(4\). Перебор сумм трёх таких остатков показывает, что остаток \(7\) невозможен: варианты дают \(0,1,2,3,4,5,6\), но не \(7\). Правая часть имеет остаток \(7\), противоречие.

Имеем \(4(n^2+3n+5)=(2n+3)^2+11\). Делимость на \(11\) равносильна \((2n+3)^2\equiv0\pmod{11}\), то есть \(2n+3\equiv0\pmod{11}\). Так как \(2^{-1}\equiv6\pmod{11}\), получаем \(n\equiv-18\equiv4\pmod{11}\).

Так как \(p\mid a^2+1\), имеем \(a^2\equiv-1\pmod p\). При этом \(p\nmid a\). Тогда \(a^4\equiv1\), но \(a^2\not\equiv1\). Значит, порядок \(a\) по модулю \(p\) равен \(4\). Порядок элемента делит \(p-1\), поэтому \(4\mid p-1\), то есть \(p\equiv1\pmod4\).

Предположим, что \(p\nmid y\). Тогда существует \(y^{-1}\pmod p\), и из \(x^2+y^2\equiv0\) получаем \((xy^{-1})^2\equiv-1\pmod p\). Но для простого \(p\equiv3\pmod4\) число \(-1\) не является квадратом. Противоречие. Значит, \(p\mid y\), а тогда из \(p\mid x^2+y^2\) следует \(p\mid x^2\), то есть \(p\mid x\).

Условие равносильно \(x^2\equiv1\pmod3\) и \(x^2\equiv4\pmod5\). Первое даёт \(x\not\equiv0\pmod3\), второе даёт \(x\equiv\pm2\pmod5\). Совмещая классы, получаем \(x\equiv2,7,8,13\pmod{15}\).

Условие \(x^2\equiv1\pmod{24}\) равносильно \(x^2\equiv1\pmod8\) и \(x^2\equiv1\pmod3\). По модулю \(8\) это означает, что \(x\) нечётно. По модулю \(3\) это означает \(x\not\equiv0\pmod3\). Значит, среди остатков \(0,\ldots,23\) подходят все нечётные, не делящиеся на \(3\): \(1,5,7,11,13,17,19,23\). Проверка показывает, что каждый из них действительно даёт квадрат \(1\pmod{24}\).

Нужно решить \(x^2\equiv-1\pmod5\) и \(x^2\equiv-1\pmod{13}\). По модулю \(5\): \(x\equiv\pm2\). По модулю \(13\): \(x\equiv\pm5\). Совмещая четыре пары условий по CRT, получаем \(x\equiv8,18,47,57\pmod{65}\).

Из \(x^2\equiv y^2\pmod p\) следует \(p\mid (x-y)(x+y)\). Так как \(p\) простое, оно делит один из множителей. Значит, \(x\equiv y\pmod p\) или \(x\equiv -y\pmod p\).

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

Так как \(p\nmid b\), положим \(t\equiv ab^{-1}\pmod p\). Тогда \(t^2+t+1\equiv0\). Умножим на \(t-1\): \(t^3-1\equiv0\). При этом \(t\not\equiv1\), иначе \(3\equiv0\pmod p\), что невозможно. Значит, порядок \(t\) равен \(3\). Порядок делит \(p-1\), поэтому \(3\mid p-1\), то есть \(p\equiv1\pmod3\).

Предположим, что не оба числа делятся на \(p\). Если \(p\mid b\), то из формы получаем \(p\mid a^2\), значит \(p\mid a\), противоречие предположению. Значит, можно считать \(p\nmid b\). Тогда \(t=ab^{-1}\) удовлетворяет \(t^2+t+1\equiv0\pmod p\), и, как в предыдущей задаче, это даёт элемент порядка \(3\). Тогда \(3\mid p-1\), то есть \(p\equiv1\pmod3\), что противоречит \(p\equiv2\pmod3\). Следовательно, \(p\mid a\) и \(p\mid b\).

Пусть \(p\equiv3\pmod4\) и \(p\mid x^2+y^2\). По лемме \(p\mid x\) и \(p\mid y\), значит \(x=px_1\), \(y=py_1\). Тогда \(N=p^2(x_1^2+y_1^2)\). Если \(p\) снова делит \(x_1^2+y_1^2\), повторяем тот же шаг. Каждый раз показатель \(p\) уменьшается на \(2\). Поэтому в \(N\) показатель \(p\) может быть только чётным.

Из уравнения следует \(p\mid x^2+y^2\). По лемме для простых \(p\equiv3\pmod4\) получаем \(p\mid x\) и \(p\mid y\). Тогда \(p^2\mid x^2+y^2=pz^2\), значит \(p\mid z\). Делим \(x,y,z\) на \(p\) и получаем новое целое решение меньшего размера. Если существовало ненулевое решение, повторение дало бы бесконечный спуск. Следовательно, ненулевых решений нет, и единственное решение - \(x=y=z=0\).