Теория чисел. Книга 2

Пусть \(d=\gcd(n+4,n^2+2n+10)\). По модулю \(n+4\) имеем \(n\equiv-4\), поэтому \(n^2+2n+10\equiv16-8+10=18\). Следовательно, \(d=\gcd(n+4,18)\), значит возможны только делители \(18\): \(1,2,3,6,9,18\). Каждый из них достигается: для делителя \(r\mid18\) возьмём \(n+4=r+18\). Тогда \( \gcd(n+4,18)=r \).

Если \(d\mid n+1\), то \(n\equiv-1\pmod d\). Тогда \(n^2+n+1\equiv1-1+1=1\pmod d\). Общий делитель должен делить \(1\), значит он равен \(1\).

Любой общий делитель \(d\) чисел \(3n+2\) и \(5n+3\) делит комбинацию \(5(3n+2)-3(5n+3)=1\). Поэтому \(d=1\), и числа взаимно просты.

По модулю \(n+3\) имеем \(n\equiv-3\), значит \(n^2+1\equiv10\). Поэтому \( \gcd(n^2+1,n+3)=\gcd(10,n+3) \). Этот НОД больше \(1\), если \(n+3\) делится на \(2\) или на \(5\). Следовательно, \(n\) нечётно или \(n\equiv2\pmod5\).

Заметим, что \((2n+1)^2=4n^2+4n+1\). Если \(d\) делит \(2n+1\) и \(4n^2+4n+3\), то \(d\) делит разность \(2\). Но \(2n+1\) нечётно, значит его общий делитель со вторым числом не может быть равен \(2\). Поэтому \(d=1\).

Имеем \(n^3-1=(n-1)(n^2+n+1)\) и \(n^2-1=(n-1)(n+1)\). Поэтому НОД равен \((n-1)\gcd(n^2+n+1,n+1)\). Последний НОД равен \(1\), так как при \(n\equiv-1\) выражение \(n^2+n+1\) даёт остаток \(1\). Следовательно, весь НОД равен \(n-1\).

Пусть \(d\) - общий делитель. Так как \(d\mid2n+1\), имеем \((2n+1)^2\equiv0\pmod d\). Но \(4(n^2+n+1)=(2n+1)^2+3\), значит \(d\mid3\). Поэтому НОД больше \(1\) только если \(3\mid2n+1\), то есть \(n\equiv1\pmod3\). При этом условии \(3\) действительно делит оба числа. Ответ: \(n\equiv1\pmod3\).

Пусть нечётный простой \(p\) делит оба числа. Из \(a+b\equiv0\pmod p\) следует \(b\equiv-a\). Тогда \(a^2+b^2\equiv2a^2\pmod p\). Так как \(p\ne2\), получаем \(p\mid a\), а значит \(p\mid b\), что противоречит \( \gcd(a,b)=1 \). Значит, возможен только делитель \(2\). Он появляется тогда и только тогда, когда \(a+b\) и \(a^2+b^2\) чётны, то есть когда \(a,b\) оба нечётны. В этом случае \(a^2+b^2\equiv2\pmod4\), поэтому НОД ровно \(2\).

Пусть \(m=n+2\). Тогда \(n^2+3n+3=m^2-m+1\), а \(n^2+5n+7=m^2+m+1\). Их общий делитель делит разность \(2m\). Но \(m^2-m+1\) взаимно просто с \(m\), потому что по модулю \(m\) оно даёт остаток \(1\). Следовательно, общий делитель может делить только \(2\). При этом \(m^2-m+1\) всегда нечётно, поэтому общий делитель не равен \(2\). Значит, НОД равен \(1\).

Так как \( \gcd(m,n)=1 \), общий факт для степеней даёт \( \gcd(a^m-1,a^n-1)=a^1-1=a-1 \). Если доказывать напрямую, общий делитель сохраняется при замене пары показателей \((m,n)\) на \((m-n,n)\), пока алгоритм Евклида не приведёт к показателю \(1\).

Общий делитель делит разность \((3^n+2)-(3^n-1)=3\). Значит, возможен только общий простой делитель \(3\). Но \(3^n-1\equiv -1\pmod3\), поэтому \(3\) не делит первое число. Следовательно, общий делитель равен \(1\).

Пусть \(d\) - общий делитель. Тогда \(d\mid n(n^2+2)-(n^3+3)=2n-3\). Значит \(2n\equiv3\pmod d\). Умножим \(n^2+2\) на \(4\): получаем \(4n^2+8\equiv9+8=17\pmod d\). Поэтому \(d\mid17\). Общий делитель больше \(1\) возможен только при \(17\mid d\), то есть при \(2n\equiv3\pmod{17}\). Так как \(2^{-1}\equiv9\pmod{17}\), получаем \(n\equiv27\equiv10\pmod{17}\). Проверка подстановкой показывает, что при таких \(n\) оба выражения делятся на \(17\).

Пусть \(d\) делит оба числа. Тогда \(d\mid (n+1)!+1-(n+1)(n!+1)=-n\). Значит \(d\mid n\), а тогда \(d\mid n!\). Но \(d\mid n!+1\), поэтому \(d\mid1\). Следовательно, \(d=1\).

Пусть \(d\) - общий делитель. Тогда \(d\mid p^3+1-p(p^2+1)=1-p\). Значит, \(d\mid p-1\). По модулю \(p-1\) имеем \(p\equiv1\), поэтому \(p^2+1\equiv2\). Следовательно, общий делитель может делить только \(2\). Если \(p=2\), то получаем \(\gcd(5,9)=1\). Если \(p\) нечётно, то \(p^2+1\) и \(p^3+1\) чётны, значит НОД равен \(2\). Ответ: все нечётные простые \(p\).

Пусть \(g=\gcd(m,n)\). Число \(a^g-b^g\) делит оба выражения. Обратно, пусть \(d\) делит оба. Так как \( \gcd(b,d)=1 \), существует обратный элемент \(b^{-1}\pmod d\). Из \(a^m\equiv b^m\) и \(a^n\equiv b^n\) получаем \((ab^{-1})^m\equiv1\) и \((ab^{-1})^n\equiv1\pmod d\). По алгоритму Евклида для показателей \((ab^{-1})^g\equiv1\pmod d\). Значит, \(a^g\equiv b^g\pmod d\), то есть \(d\mid a^g-b^g\).

Так как \(4^m-1=2^{2m}-1\), применяем формулу для степеней: \( \gcd(2^{2m}-1,2^n-1)=2^{\gcd(2m,n)}-1 \). Это и есть ответ.

Пусть \(d\) - НОД. По модулю \(x+y\) имеем \(x\equiv-y\), поэтому \(x^{2k}+y^{2k}\equiv2y^{2k}\pmod d\). Так как \( \gcd(y,x+y)=1 \), общий делитель \(d\) делит \(2\). Следовательно, возможны только \(1\) и \(2\). Если \(x,y\) оба нечётны, то \(x+y\) чётно и \(x^{2k}+y^{2k}\) чётно, значит НОД равен \(2\). Если один из них чётен, другой нечётен, то \(x+y\) нечётно, значит НОД равен \(1\).

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

Имеем \(u_{n+1}=u_n(u_n-1)+1\), поэтому \(u_{n+1}\equiv1\pmod{u_n}\). Если \(u_k\equiv1\pmod{u_n}\), то \(u_{k+1}=u_k^2-u_k+1\equiv1-1+1=1\pmod{u_n}\). Следовательно, для любого \(m>n\) выполнено \(u_m\equiv1\pmod{u_n}\). Поэтому общий делитель \(u_m\) и \(u_n\) делит \(1\), и НОД равен \(1\).

Обозначим \(Q=a^2+ab+b^2\). Если \(3\mid n\), то \(a^3-b^3=(a-b)Q\), значит \(a^3\equiv b^3\pmod Q\), и потому \(Q\mid a^n-b^n\). В этом случае НОД равен \(Q\). Пусть теперь \(3\nmid n\). Рассмотрим простой \(p\ne3\), делящий \(Q\) и \(a^n-b^n\). Так как \(p\nmid b\), положим \(t\equiv ab^{-1}\pmod p\). Из \(Q\equiv0\) следует \(t^2+t+1\equiv0\), то есть \(t^3\equiv1\) и \(t\not\equiv1\). Значит, порядок \(t\) равен \(3\). Но из \(a^n\equiv b^n\) следует \(t^n\equiv1\), поэтому \(3\mid n\), противоречие. Следовательно, при \(3\nmid n\) возможен только общий простой делитель \(3\). Число \(3\) делит \(Q\) тогда и только тогда, когда \(a\equiv b\pmod3\); из взаимной простоты тогда \(a,b\) не делятся на \(3\), и \(Q\) делится на \(3\), но не на \(9\). При том же условии \(a^n-b^n\) делится на \(3\). Ответ: если \(3\mid n\), НОД равен \(Q\); если \(3\nmid n\) и \(a\equiv b\pmod3\), НОД равен \(3\); в остальных случаях НОД равен \(1\).

Если число чётно, \(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\).

\(2^1\equiv2\), \(2^2\equiv4\), \(2^3\equiv8\equiv1\pmod7\). Раньше \(1\) не появлялась, поэтому порядок равен \(3\).

\(3,9,27,81,243\) по модулю \(11\) дают \(3,9,5,4,1\). Поэтому \( \operatorname{ord}_{11}(3)=5 \).

Так как порядок \(2\) по модулю \(7\) равен \(3\), уменьшаем показатель: \(100\equiv1\pmod3\). Поэтому \(2^{100}\equiv2\pmod7\).

Степени \(3\) по модулю \(10\): \(3,9,7,1\), затем цикл повторяется. Так как \(2026\equiv2\pmod4\), последняя цифра равна \(9\).

\(5^2=25\equiv12\equiv-1\pmod{13}\). Тогда \(5^4\equiv1\). Порядок не равен \(1\) или \(2\), потому что \(5\not\equiv1\) и \(5^2\not\equiv1\). Значит, порядок равен \(4\).

Пусть \(k=qd+r\), где \(0\le r

Если \(d=\operatorname{ord}_m(a)\), то из \(a^r\equiv1\) и \(a^s\equiv1\) следует \(d\mid r\) и \(d\mid s\). Поэтому \(d\mid\gcd(r,s)\), а значит \(a^{\gcd(r,s)}\equiv1\pmod m\).

Из \(2^m\equiv1\pmod p\) следует \( \operatorname{ord}_p(2)\mid m \). Так как \(p\) простое и \(2\not\equiv0\pmod p\), порядок также делит \(p-1\). Следовательно, он делит \(\gcd(m,p-1)\).

При \(p=2\) делимости нет. Если \(p\) нечётно, то по малой теореме Ферма \(2^p\equiv2\pmod p\). Тогда \(2^p+1\equiv3\pmod p\), значит \(p\mid3\), откуда \(p=3\). Проверка: \(2^3+1=9\) делится на \(3\).

Из \(a^2+a+1\equiv0\pmod p\) получаем \(a^3-1=(a-1)(a^2+a+1)\equiv0\pmod p\). Если \(a\equiv1\pmod p\), то \(3\equiv0\pmod p\), значит \(p=3\). Если \(a\not\equiv1\), то порядок \(a\) равен \(3\), поэтому \(3\mid p-1\), то есть \(p\equiv1\pmod3\).

Вычислим \(7^2=49\), \(7^4\equiv49^2=2401\equiv1\pmod{100}\). Так как \(100\) делится на \(4\), получаем \(7^{100}=(7^4)^{25}\equiv1\pmod{100}\). Последние две цифры - \(01\).

Имеем \(5^2=25\not\equiv1\pmod{31}\), а \(5^3=125\equiv1\pmod{31}\). Значит, \( \operatorname{ord}_{31}(5)=3 \). Поэтому \(5^n\equiv1\pmod{31}\) тогда и только тогда, когда \(3\mid n\).

Вычислим: \(2^4=16\equiv-1\pmod{17}\), значит \(2^8\equiv1\). Порядок \(2\) по модулю \(17\) равен \(8\), потому что меньшие делители \(1,2,4\) не дают \(1\). Тогда \(2^n\equiv-1\) ровно тогда, когда \(n\equiv4\pmod8\).

Из \(p\mid a^n+1\) следует \(a^n\equiv-1\pmod p\). Тогда \(a^{2n}\equiv1\), поэтому порядок делит \(2n\). Если бы порядок делил \(n\), то было бы \(a^n\equiv1\pmod p\), что противоречит \(a^n\equiv-1\pmod p\), так как \(p\) нечётно.

Число \(2^{16}+1\) нечётно, значит \(q\ne2\). Из \(2^{16}\equiv-1\pmod q\) получаем \(2^{32}\equiv1\). При этом \(2^{16}\not\equiv1\), а порядок делит \(32\). Единственный делитель \(32\), который не делит \(16\), равен \(32\). Значит, порядок \(2\) по модулю \(q\) равен \(32\). Поэтому \(32\mid q-1\), то есть \(q\equiv1\pmod{32}\).

\(3^4+1=82=2\cdot41\). Значит, возможны \(p=2\) и \(p=41\). Для понимания метода: если \(p\ne2\) делит \(3^4+1\), то \(3^4\equiv-1\), значит порядок \(3\) по модулю \(p\) равен \(8\), и потому \(8\mid p-1\). Из делителей \(82\) это выполняется только для \(41\).

Из условия \(a^{2^r}\equiv-1\pmod p\). Тогда \(a^{2^{r+1}}\equiv1\), значит порядок \(a\) по модулю \(p\) делит \(2^{r+1}\). Но порядок не делит \(2^r\), потому что тогда \(a^{2^r}\equiv1\), а не \(-1\). Среди делителей \(2^{r+1}\) единственный, который не делит \(2^r\), равен \(2^{r+1}\). Значит, порядок равен \(2^{r+1}\), и он делит \(p-1\).

Пусть \(q\) - общий простой делитель \(F_m\) и \(F_n\), \(m

Возьмём \(F_n=2^{2^n}+1\) для \(n\ge k-1\). Любой простой делитель \(q\) числа \(F_n\) нечётен и по ферматовой лемме удовлетворяет \(q\equiv1\pmod{2^{n+1}}\), значит тем более \(q\equiv1\pmod{2^k}\). Числа \(F_n\) попарно взаимно просты, поэтому их простые делители при разных \(n\) не повторяются. Следовательно, таких простых бесконечно много.

Пусть \(d=\operatorname{ord}_p(a)\). Из \(a^6\equiv1\pmod p\) следует \(d\mid6\). Условия \(p\nmid a^3-1\) и \(p\nmid a^2-1\) означают, что \(d\nmid3\) и \(d\nmid2\). Среди делителей \(6\) только \(6\) не делит ни \(2\), ни \(3\). Значит, \(d=6\). Порядок по простому модулю делит \(p-1\), поэтому \(6\mid p-1\), то есть \(p\equiv1\pmod6\).

По Ферма \(2^{10}\equiv1\pmod{11}\). Так как \(2026\equiv6\pmod{10}\), получаем \(2^{2026}\equiv2^6=64\equiv9\pmod{11}\).

Так как \(\gcd(2,9)=1\), по Эйлеру \(2^6\equiv1\pmod9\). Поскольку \(100\equiv4\pmod6\), имеем \(2^{100}\equiv2^4=16\equiv7\pmod9\).

Прямо: \(7\cdot2=14\equiv1\pmod{13}\). Значит, обратный элемент равен \(2\). По Ферма это согласуется с тем, что \(7^{12}\equiv1\), значит \(7^{11}\) тоже обратный.

Так как \(11\) простое, \(10!\equiv-1\equiv10\pmod{11}\).

Используем формулу: \(\varphi(45)=45(1-1/3)(1-1/5)=45\cdot2/3\cdot4/5=24\).

Если \(p\mid a\), то \(a^p-a\) делится на \(p\). Если \(p\nmid a\), то \(a^{p-1}\equiv1\pmod p\), и после умножения на \(a\) получаем \(a^p\equiv a\pmod p\).

По Ферма \(7^{12}\equiv1\pmod{13}\). Так как \(100\equiv4\pmod{12}\), получаем \(7^{100}\equiv7^4\). \(7^2=49\equiv10\), значит \(7^4\equiv100\equiv9\pmod{13}\).

\(\gcd(3,100)=1\), \(\varphi(100)=40\). По Эйлеру \(3^{40}\equiv1\pmod{100}\), значит \(3^{80}\equiv1\pmod{100}\). Последние две цифры: \(01\).

По Вильсону \(10!\equiv-1\pmod{11}\). Но \(10!=10\cdot9\cdot8!\equiv(-1)(-2)8!\equiv2\cdot8!\). Значит, \(2\cdot8!\equiv10\), откуда \(8!\equiv5\pmod{11}\).

По Вильсону \((p-1)!\equiv-1\pmod p\). Но \((p-1)!\equiv(p-1)(p-2)!\equiv-(p-2)!\pmod p\). Значит, \(-(p-2)!\equiv-1\), откуда \((p-2)!\equiv1\pmod p\).

Имеем \((p-1)!=(p-1)(p-2)(p-3)!\equiv(-1)(-2)(p-3)!\equiv2(p-3)!\pmod p\). По Вильсону это равно \(-1\). Значит, \(2(p-3)!\equiv-1\), откуда \((p-3)!\equiv -2^{-1}\pmod p\). Так как \(2^{-1}\equiv (p+1)/2\), получаем \((p-3)!\equiv (p-1)/2\pmod p\).

Заметим, что \(7^4\equiv1\pmod{100}\). Так как \(222\equiv2\pmod4\), получаем \(7^{222}\equiv7^2=49\pmod{100}\).

По форме Ферма \(a^p\equiv a\pmod p\). Умножая на \(a\), получаем \(a^{p+1}\equiv a^2\pmod p\). Значит, \(p\mid a^{p+1}-a^2\).

Так как \(8!\) содержит множители \(3\) и \(6\), произведение делится на \(9\). Поэтому \(8!\equiv0\pmod9\), а не \(-1\). Противоречия нет: теорема Вильсона утверждает сравнение \((p-1)!\equiv-1\pmod p\) для простого \(p\), а \(9\) составное.

По теореме Эйлера \(a^{\varphi(n)}\equiv1\pmod n\). Но \(a\cdot a^{\varphi(n)-1}=a^{\varphi(n)}\). Значит, \(a^{\varphi(n)-1}\) действительно является обратным элементом.

При \(p=2\) число \(2^{p-1}+1=3\) не делится на \(2\). Если \(p\) нечётно, то по Ферма \(2^{p-1}\equiv1\pmod p\). Тогда \(2^{p-1}+1\equiv2\pmod p\), что не равно \(0\). Ответ: таких простых нет.

В множестве \(1,2,\ldots,p-1\) каждый остаток имеет обратный. Остатки, равные своим обратным, удовлетворяют \(x^2\equiv1\pmod p\), значит \(x\equiv1\) или \(x\equiv-1\pmod p\). Все остальные остатки разбиваются на пары \(x,x^{-1}\), произведение каждой пары равно \(1\). Поэтому \((p-1)!\equiv1\cdot(-1)\equiv-1\pmod p\).

Самобратные элементы удовлетворяют \(x^2\equiv1\pmod p\), то есть это \(1\) и \(-1\). Произведение всех ненулевых остатков равно \((p-1)!\equiv-1\pmod p\). Если убрать множители \(1\) и \(-1\), то оставшееся произведение равно \((-1)/(1\cdot(-1))\equiv1\pmod p\).

\(\gcd(11,72)=1\), \(\varphi(72)=72(1-1/2)(1-1/3)=24\). Поэтому \(11^{24}\equiv1\pmod{72}\). Так как \(2026\equiv10\pmod{24}\), нужно найти \(11^{10}\pmod{72}\). \(11^2=121\equiv49\), \(11^4\equiv49^2=2401\equiv25\), \(11^8\equiv25^2=625\equiv49\). Тогда \(11^{10}=11^8\cdot11^2\equiv49\cdot49=2401\equiv25\pmod{72}\).

Пусть \(n\) составное. Если \(n=4\), то \(3!=6\equiv2\pmod4\), не \(-1\). Пусть теперь \(n\ne4\). Запишем \(n=ab\), где \(1

\(72=2^3\cdot3^2\), поэтому \(v_2(72)=3\).

\(1000=2^3\cdot5^3\). Поэтому \(v_5(1000)=3\).

По формуле Лежандра \(v_3(50!)=16+5+1=22\).

Количество нулей равно \(v_5(80!)=\lfloor80/5\rfloor+\lfloor80/25\rfloor=16+3=19\).

\(v_2(100!)=50+25+12+6+3+1=97\). Значит, наибольшее \(k\) равно \(97\).

\(v_2(2026!)=1013+506+253+126+63+31+15+7+3+1=2018\).

Нужно \(2k\le v_2(100!)=97\) и \(k\le v_3(100!)=48\). Поэтому \(k\le48\) в обоих случаях, и ответ \(48\).

\(v_3(30!)=10+3+1=14\), \(v_3(10!)=3+1=4\), \(v_3(20!)=6+2=8\). Поэтому \(v_3\left(\binom{30}{10}\right)=14-4-8=2\).

Пусть \(a=p^r u\), \(b=p^s v\), где \(p\nmid u\) и \(p\nmid v\). Тогда \(ab=p^{r+s}uv\), причём \(p\nmid uv\). Значит, показатель \(p\) в \(ab\) равен \(r+s\), то есть \(v_p(a)+v_p(b)\).

Так как \(12=2^2\cdot3\), число нулей равно \(\min(\lfloor v_2(100!)/2\rfloor, v_3(100!))=\min(48,48)=48\).

По формуле Лежандра \(v_2(n!)=\lfloor n/2\rfloor+\lfloor n/4\rfloor+\cdots\). Каждое слагаемое не превосходит соответствующего \(n/2^i\), а хотя бы первое строго меньше или вся сумма floors строго меньше \(n/2+n/4+\cdots=n\). Значит, \(v_2(n!)

\(v_2(200!)=197\), \(v_3(200!)=66+22+7+2=97\), \(v_5(200!)=40+8+1=49\). Так как \(30^k\) требует по \(k\) каждого простого \(2,3,5\), ответ равен \(\min(197,97,49)=49\).

\(v_5(100!)=20+4=24\), \(v_5(25!)=5+1=6\), \(v_5(75!)=15+3=18\). Разность \(24-6-18=0\). Значит, \(\binom{100}{25}\) не делится на \(5\).

\(\prod_{i=1}^{100} i(i+1)=(1\cdot2\cdots100)(2\cdot3\cdots101)=100!\cdot101!\). Поэтому показатель двойки равен \(v_2(100!)+v_2(101!)=97+97=194\). Ответ: \(194\).

\(v_2(100!)=97\), \(v_2(50!)=25+12+6+3+1=47\). Поэтому искомый показатель равен \(97-47=50\).

Нужно доказать, что \(v_2((2n)!)-2v_2(n!)>0\). Пусть \(n=2^t u\), где \(u\) нечётно. В сумме Лежандра рассмотрим слагаемое \(2^{t+1}\): \(\lfloor2n/2^{t+1}\rfloor-2\lfloor n/2^{t+1}\rfloor=\lfloor u\rfloor-2\lfloor u/2\rfloor=1\). Остальные слагаемые неотрицательны, значит \(v_2\left(\binom{2n}{n}\right)\ge1\).

Пусть \(A=(m+1)(m+2)\cdots(m+n)\). Среди этих \(n\) чисел не меньше \(\lfloor n/p\rfloor\) кратны \(p\), не меньше \(\lfloor n/p^2\rfloor\) кратны \(p^2\), и так далее. Поэтому \(v_p(A)\ge\lfloor n/p\rfloor+\lfloor n/p^2\rfloor+\cdots=v_p(n!)\). Это верно для каждого простого \(p\), значит \(n!\mid A\).

Из формулы Лежандра следует известное тождество \(v_2(n!)=\lfloor n/2\rfloor+\lfloor n/4\rfloor+\cdots=n-s_2(n)\), где \(s_2(n)\) - сумма цифр в двоичной записи \(n\). Условие \(2^{n-1}\mid n!\) равносильно \(v_2(n!)\ge n-1\), то есть \(n-s_2(n)\ge n-1\). Отсюда \(s_2(n)\le1\). Для натурального \(n\) это возможно только тогда, когда в двоичной записи ровно одна единица, то есть \(n\) является степенью двойки. Проверка обратного направления: если \(n=2^r\), то \(s_2(n)=1\), значит \(v_2(n!)=n-1\), и делимость выполнена.

\(v_2(150!)=75+37+18+9+4+2+1=146\). \(v_3(150!)=50+16+5+1=72\). Для \(36^k=2^{2k}3^{2k}\) нужно \(2k\le146\) и \(2k\le72\), поэтому \(k\le73\) и \(k\le36\). Ответ: \(36\).

По Лежандру \(v_3(n!)=\lfloor n/3\rfloor+\lfloor n/9\rfloor+\cdots\). Эта сумма строго меньше \(n/3+n/9+\cdots=n/2\), а значит тем более меньше \(n\). Поэтому \(v_3(n!)

По LTE \(v_3(10^{2025}-1)=v_3(10-1)+v_3(2025)=v_3(9)+4=2+4=6\).

По LTE \(v_7(8^{100}-1)=v_7(7)+v_7(100)=1+0=1\).

\(v_5(6^{50}-1)=v_5(5)+v_5(50)=1+2=3\).

Так как \(3\mid2+1\) и \(100\) чётно, \(v_3(2^{100}-1)=v_3(3)+v_3(100)=1\).

\(v_2(3^{100}-1)=v_2(2)+v_2(4)+v_2(100)-1=1+2+2-1=4\).

\(v_7(8^n-1)=1+v_7(n)\). Нужно \(1+v_7(n)\ge3\), то есть \(v_7(n)\ge2\). Ответ: все \(n\), кратные \(49\).

Из задачи 1 \(v_3(10^{2025}-1)=6\). Так как \(9^k=3^{2k}\), получаем \(2k\le6\), значит \(k=3\).

По LTE \(v_5(11^n-1)=v_5(10)+v_5(n)=1+v_5(n)\).

\(v_3(4^n-1)=v_3(3)+v_3(n)=1+v_3(n)\).

По случаю \(a+b\): \(v_3(5^{2n}-1)=v_3(6)+v_3(2n)=1+v_3(n)\).

Если \(n\) нечётно, то \(v_2(5^n-1)=v_2(5-1)=2\). Если \(n\) чётно, то \(v_2(5^n-1)=v_2(4)+v_2(6)+v_2(n)-1=2+1+v_2(n)-1=2+v_2(n)\).

Если \(n\) нечётно, \(v_2(3^n-1)=v_2(2)=1\), не хватает. Если \(n\) чётно, то \(v_2(3^n-1)=v_2(2)+v_2(4)+v_2(n)-1=2+v_2(n)\). Нужно \(2+v_2(n)\ge4\), то есть \(v_2(n)\ge2\). Ответ: \(4\mid n\).

Нужно \(1+v_3(n)\ge5\), то есть \(v_3(n)\ge4\). Ответ: \(81\mid n\).

По LTE \(v_p(a^{p^{r-1}}-b^{p^{r-1}})=v_p(a-b)+v_p(p^{r-1})\). Так как \(p\mid a-b\), первое слагаемое не меньше \(1\), а второе равно \(r-1\). Итого показатель не меньше \(r\), значит делимость на \(p^r\) доказана.

\(2^{2n}-1=4^n-1\). Так как \(3\mid4-1\), \(v_3(4^n-1)=1+v_3(n)\). Следовательно, \(k=1+v_3(n)\).

По LTE \(v_3(13^n-1)=v_3(12)+v_3(n)=1+v_3(n)\).

По LTE \(v_3(10^n-1)=v_3(9)+v_3(n)=2+v_3(n)\). Нужно \(2+v_3(n)\ge n\). Проверяем: \(n=1,2,3\) подходят. Если \(n\ge4\), то \(v_3(n)\le n-3\) с большим запасом; точнее \(2+v_3(n)

Нужно \(1+v_7(n)\ge n\). При \(n=1\) условие выполнено. Если \(n\ge2\), то \(v_7(n)\le \log_7 n

По LTE \(v_p(a^n-b^n)=v_p(a-b)+v_p(n)=1+v_p(n)\). Делимость \(p^r\mid a^n-b^n\) равносильна \(1+v_p(n)\ge r\), то есть \(v_p(n)\ge r-1\). Это равносильно \(p^{r-1}\mid n\).

\(v_2(3^{2^m}-1)=v_2(3-1)+v_2(3+1)+v_2(2^m)-1=1+2+m-1=m+2\).

Имеем \(xy+2x+3y+6=60\), то есть \((x+3)(y+2)=60\). Так как \(x,y>0\), нужно \(x+3\ge 4\), \(y+2\ge 3\). Подходящие пары делителей \(60\): \((4,15),(5,12),(6,10),(10,6),(12,5),(15,4),(20,3)\). Отсюда получаем \((1,13),(2,10),(3,8),(7,4),(9,3),(12,2),(17,1)\). Все они проверяются подстановкой.

Из \(10x+10y=xy\) получаем \(xy-10x-10y=0\), значит \((x-10)(y-10)=100\). Поэтому \(x=10+d\), \(y=10+\frac{100}{d}\), где \(d\) пробегает положительные делители \(100\). Ответ: \((11,110),(12,60),(14,35),(15,30),(20,20),(30,15),(35,14),(60,12),(110,11)\).

Пишем \((x-y)(x+y)=105\). Оба множителя должны иметь одинаковую чётность; так как произведение нечётно, оба множителя нечётные. Пары делителей: \((1,105),(3,35),(5,21),(7,15)\). Они дают \((x,y)=(53,52),(19,16),(13,8),(11,4)\).

По модулю \(n+5\) имеем \(n^2+7\equiv 25+7=32\). Следовательно, \(n+5\mid 32\). Так как \(n+5>5\), возможны \(n+5=8,16,32\). Получаем \(n=3,11,27\). Проверка показывает, что все три значения подходят.

Если \(q=2\), то \(p^2=124\), что невозможно. Значит \(p,q\) нечётные, и \(p-q\), \(p+q\) — чётные положительные множители \(120\). Проверяем пары \((2,60),(4,30),(6,20),(10,12)\). Они дают \((p,q)=(31,29),(17,13),(13,7),(11,1)\). Последняя пара не подходит, так как \(1\) не простое. Ответ: \((31,29),(17,13),(13,7)\).

Уравнение равносильно \(xy-4x-7y=9\). Добавляем \(28\): \((x-7)(y-4)=37\). Так как \(37\) простое, возможны только пары множителей \((1,37)\) и \((37,1)\). Получаем \((x,y)=(8,41)\) и \((44,5)\).

Получаем \(8x+8y+8=xy\), то есть \(xy-8x-8y=8\). Поэтому \((x-8)(y-8)=72\). Для каждого положительного делителя \(d\mid 72\) имеем \(x=8+d\), \(y=8+\frac{72}{d}\). Значит решения: \((9,80),(10,44),(11,32),(12,26),(14,20),(16,17),(17,16),(20,14),(26,12),(32,11),(44,10),(80,9)\).

Перепишем уравнение как \((x+y)(x-y)-2(x+y)=21\), то есть \((x+y)(x-y-2)=21\). Пусть \(A=x+y\), \(B=x-y-2\). Возможные положительные пары \((A,B)\): \((1,21),(3,7),(7,3),(21,1)\). Первые две дают неположительное \(y\). Из \((7,3)\) получаем \(x=6,y=1\), из \((21,1)\) получаем \(x=12,y=9\). Ответ: \((6,1),(12,9)\).

Имеем \((x+2)^2-y^2=15\), то есть \((x+2-y)(x+2+y)=15\). Пары положительных множителей одинаковой чётности: \((1,15)\) и \((3,5)\), обе нечётные. Из них получаем \((x,y)=(6,7)\) и \((2,1)\). Проверка в исходном уравнении подтверждает оба решения.

Если \(2n+1\mid n^2+n+10\), то \(2n+1\mid 4(n^2+n+10)\). Но \(4n^2+4n+40=(2n+1)^2+39\). Значит \(2n+1\mid 39\). Так как \(2n+1>1\) и нечётно, возможны \(2n+1=3,13,39\). Получаем \(n=1,6,19\). Все три значения подходят.

Квадрат целого числа по модулю \(4\) равен \(0\) или \(1\). Правая часть \(4xy+3\equiv 3\pmod 4\). Левая часть может принимать по модулю \(4\) значения \(0,1,2\), но не \(3\). Противоречие. Следовательно, целых решений нет.

Из уравнения получаем \(y(x+1)=x^2-x-11\). Но \(x^2-x-11=(x+1)(x-2)-9\). Значит \(x+1\mid 9\). Так как \(x>0\), имеем \(x+1=3\) или \(9\). При \(x=2\) получаем \(y=-3\), не подходит. При \(x=8\) получаем \(9y=45\), то есть \(y=5\). Ответ: \((8,5)\).

Так как \(x\le y\le z\), то \(1=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}\le \frac{3}{x}\), значит \(x\le 3\). При \(x=1\) оставшаяся сумма равна \(0\), невозможно. При \(x=2\) получаем \(\frac{1}{y}+\frac{1}{z}=\frac{1}{2}\), то есть \((y-2)(z-2)=4\). С учётом \(y\le z\): \((y,z)=(3,6),(4,4)\). При \(x=3\) получаем \(\frac{1}{y}+\frac{1}{z}=\frac{2}{3}\). Так как \(y\ge 3\), максимум левой части равен \(\frac{2}{3}\), значит \(y=z=3\). Ответ: \((2,3,6),(2,4,4),(3,3,3)\).

Имеем \(x^2+y^2=(60-x-y)^2\). После раскрытия и сокращения: \(xy-60x-60y+1800=0\), то есть \((x-60)(y-60)=1800\). Так как \(x,y<60\), положим \(a=60-x\), \(b=60-y\). Тогда \(ab=1800\), а гипотенуза равна \(a+b-60\), поэтому нужно \(a<60\), \(b<60\), \(a+b>60\). Подходящие пары делителей: \((36,50)\) и \((40,45)\), а также перестановки. Получаем стороны \(24,10,26\) и \(20,15,25\). Ответ: \((10,24,26)\) и \((15,20,25)\).

Уравнение равносильно \((x-y)^2=x+y\). Пусть \(d=|x-y|\). Тогда \(x+y=d^2\). Если \(x\ge y\), то \(x-y=d\), откуда \(x=\frac{d^2+d}{2}\), \(y=\frac{d^2-d}{2}\). Для положительности нужно \(d\ge 2\). Обратно, при любом \(d\ge 2\) эти числа положительны и удовлетворяют уравнению. С учётом перестановки ответ: \(\left(\frac{d(d+1)}{2},\frac{d(d-1)}{2}\right)\) и перестановка, где \(d=2,3,4,\ldots\).

Если \(x,y\ge 2\), то \(x^2+y^2-xy-1=(x-y)^2+xy-1\ge 3>0\), значит \(x^2+y^2>xy+1\). Тогда делимость невозможна, потому что положительный делитель больше положительного числа. Если \(x=1\), условие даёт \(1+y^2\mid y+1\), что возможно только при \(y=1\). Аналогично при \(y=1\). Пара \((1,1)\) действительно подходит: \(2\mid 2\). Ответ: \((1,1)\).

Если \(N+1\) составное, берём блок \(N+2,N+3,\ldots,2N+1\). Любое простое \(p\le N\) делит произведение любых \(N\) последовательных чисел, потому что среди них есть число, кратное \(p\). Простые числа \(p\) из промежутка \(N+2\le p\le 2N+1\) входят в блок как отдельные множители. Число \(N+1\) не является простым, значит простых в пропущенной точке нет.

Если \(N+1\) простое, берём блок \(N+3,N+4,\ldots,2N+2\). Простые \(p\le N\) снова покрыты блоком длины \(N\). Простое \(N+1\) делит последний член \(2N+2=2(N+1)\). Число \(N+2\) не является простым: если \(N+1\) простое и больше \(3\), то \(N+1\) нечётно, значит \(N+2\) чётно и больше \(2\); случай \(N=2\) исключён условием. Простые \(p\) между \(N+3\) и \(2N+1\) входят в блок. Значит нужный блок существует в обоих случаях.

Из \(x\le y\le z\) следует \(\frac{3}{x}\ge \frac{1}{2}\), значит \(x\le 6\). При \(x=1\) сумма уже больше \(\frac{1}{2}\), при \(x=2\) оставшиеся дроби должны суммироваться в \(0\), невозможно.

Если \(x=3\), то \(\frac{1}{y}+\frac{1}{z}=\frac{1}{6}\), то есть \((y-6)(z-6)=36\). С учётом \(y\le z\): \((y,z)=(7,42),(8,24),(9,18),(10,15),(12,12)\).

Если \(x=4\), то \(\frac{1}{y}+\frac{1}{z}=\frac{1}{4}\), поэтому \((y-4)(z-4)=16\). Получаем \((5,20),(6,12),(8,8)\).

Если \(x=5\), то \(\frac{1}{y}+\frac{1}{z}=\frac{3}{10}\). Умножая и дописывая произведение, получаем \((3y-10)(3z-10)=100\). При \(y\ge 5\) и \(y\le z\) подходит только \(3y-10=5\), то есть \((y,z)=(5,10)\).

Если \(x=6\), то \(\frac{1}{y}+\frac{1}{z}=\frac{1}{3}\). Так как \(y,z\ge 6\), максимум равен \(\frac{1}{3}\), значит \(y=z=6\). Ответ: \((3,7,42),(3,8,24),(3,9,18),(3,10,15),(3,12,12),(4,5,20),(4,6,12),(4,8,8),(5,5,10),(6,6,6)\).

Пусть \(D=n^2+3n+3\). Из \(n^2\equiv -3n-3\pmod D\) получаем \(n^3\equiv -3n^2-3n\equiv 9n+9-3n=6n+9\pmod D\). Поэтому \(n^3-1\equiv 6n+8\pmod D\), и \(D\mid 6n+8\). Для \(n\ge 5\) имеем \(D=n^2+3n+3>6n+8\), что невозможно. Проверяем \(n=1,2,3,4\): при \(n=1\) получаем \(7\mid 0\), подходит; при \(n=2,3,4\) делимости нет. Ответ: \(n=1\).

Из порядка \(x\le y\le z\) следует \(\frac{3}{x}\ge \frac{2}{3}\), значит \(x\le 4\). \(x=1\) невозможен, так как \(\frac{1}{x}=1>\frac{2}{3}\).

При \(x=2\): \(\frac{1}{y}+\frac{1}{z}=\frac{1}{6}\), поэтому \((y-6)(z-6)=36\). С учётом \(y\le z\): \((y,z)=(7,42),(8,24),(9,18),(10,15),(12,12)\).

При \(x=3\): \(\frac{1}{y}+\frac{1}{z}=\frac{1}{3}\), поэтому \((y-3)(z-3)=9\). Получаем \((y,z)=(4,12),(6,6)\).

При \(x=4\): \(\frac{1}{y}+\frac{1}{z}=\frac{5}{12}\). Умножение и дополнение дают \((5y-12)(5z-12)=144\). Нужно \(y\ge 4\), \(y\le z\), значит \(5y-12\le 12\) и этот делитель сравним с \(3\) по модулю \(5\). Среди делителей \(144\), не превосходящих \(12\), подходят \(3\) и \(8\); \(3\) даёт \(y=3\), что нельзя, а \(8\) даёт \(y=4,z=6\). Ответ: \((2,7,42),(2,8,24),(2,9,18),(2,10,15),(2,12,12),(3,4,12),(3,6,6),(4,4,6)\).

Если \(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\).

Подставим: \(9t+4\equiv 7\pmod {11}\), то есть \(9t\equiv 3\pmod {11}\). Так как \(9^{-1}\equiv 5\pmod {11}\), имеем \(t\equiv 15\equiv 4\pmod {11}\). Поэтому \(x=9(11s+4)+4=99s+40\). Ответ: \(x\equiv 40\pmod {99}\).

Из первых двух условий: \(x=4a+1\), \(4a+1\equiv 2\pmod 5\), значит \(4a\equiv 1\), \(a\equiv 4\pmod 5\). Тогда \(x\equiv 17\pmod {20}\). Теперь \(20b+17\equiv 3\pmod 7\), то есть \(6b\equiv 0\pmod 7\), значит \(b\equiv 0\pmod 7\). Наименьшее положительное решение \(x=17\).

Если \(x\equiv 2\pmod 6\), то \(x\equiv 2\pmod 3\). Если \(x\equiv 3\pmod 9\), то \(x\equiv 0\pmod 3\). Одно и то же число не может иметь два разных остатка по модулю \(3\). Значит решений нет.

Общий делитель \(12\) и \(18\) равен \(6\), а \(17-5=12\) делится на \(6\), значит система совместна. Пусть \(x=12t+5\). Тогда \(12t+5\equiv 17\pmod {18}\), то есть \(12t\equiv 12\pmod {18}\). Делим на \(6\): \(2t\equiv 2\pmod 3\), значит \(t\equiv 1\pmod 3\). Поэтому \(x=12(3s+1)+5=36s+17\). Ответ: \(x\equiv 17\pmod {36}\).

Условия означают \(N\equiv -1\pmod 3\), \(N\equiv -1\pmod 5\), \(N\equiv -1\pmod 7\). Значит \(N\equiv -1\pmod {105}\). Например, \(N=104\).

Нужно \(N\equiv 3\pmod 4\), \(N\equiv 3\pmod 5\), \(N\equiv 6\pmod 9\). Первые два условия дают \(N\equiv 3\pmod {20}\). Пусть \(N=20t+3\). Тогда \(20t+3\equiv 6\pmod 9\), то есть \(2t\equiv 3\pmod 9\). Обратный к \(2\) по модулю \(9\) равен \(5\), значит \(t\equiv 15\equiv 6\pmod 9\). Наименьшее \(N=20\cdot 6+3=123\).

Из \(4n+1\equiv 0\pmod 9\) получаем \(4n\equiv 8\), значит \(n\equiv 2\pmod 9\). Из \(5n-2\equiv 0\pmod {11}\) получаем \(5n\equiv 2\), а \(5^{-1}\equiv 9\pmod {11}\), значит \(n\equiv 18\equiv 7\pmod {11}\). Решаем \(n=9t+2\), \(9t+2\equiv 7\pmod {11}\), то есть \(9t\equiv 5\). Так как \(9^{-1}\equiv 5\), \(t\equiv 25\equiv 3\pmod {11}\). Ответ: \(n\equiv 29\pmod {99}\).

Зададим \(N+1\equiv 0\pmod 2\), \(N+2\equiv 0\pmod 3\), \(N+3\equiv 0\pmod 5\), \(N+4\equiv 0\pmod 7\). То есть \(N\equiv 1\pmod 2\), \(N\equiv 1\pmod 3\), \(N\equiv 2\pmod 5\), \(N\equiv 3\pmod 7\). По CRT есть решение по модулю \(210\). Одно решение \(N=157\). Тогда \(158,159,160,161\) делятся соответственно на \(2,3,5,7\) и больше этих делителей, значит составные.

Имеем \(385=5\cdot 7\cdot 11\). По каждому из модулей \(5,7,11\) сравнение \(x^2\equiv 1\) имеет два решения: \(x\equiv 1\) и \(x\equiv -1\). Модули попарно взаимно просты, значит решения комбинируются независимо. Всего \(2^3=8\) решений по модулю \(385\).

Получаем четыре системы. \((1,1)\) даёт \(x\equiv 1\). \((-1,-1)\) даёт \(x\equiv -1\equiv 34\). Для \(x\equiv 1\pmod 5\), \(x\equiv -1\pmod 7\): числа \(1,6,11,16,21,26,31\), подходит \(6\). Для \(x\equiv -1\pmod 5\), \(x\equiv 1\pmod 7\): подходит \(29\). Ответ: \(1,6,29,34\pmod {35}\).

Пусть \(d=\gcd(m,n)\). Если \(x\) — решение, то \(m\mid x-a\), \(n\mid x-b\), поэтому \(d\mid (x-a)\) и \(d\mid (x-b)\), значит \(d\mid a-b\). Обратно, пусть \(d\mid a-b\). Пишем \(m=dm_1\), \(n=dn_1\), \(\gcd(m_1,n_1)=1\). Ищем \(x=a+mt\). Нужно \(a+d m_1t\equiv b\pmod {dn_1}\), то есть \(m_1t\equiv \frac{b-a}{d}\pmod {n_1}\). Так как \(m_1\) взаимно просто с \(n_1\), обратный элемент существует, и \(t\) можно выбрать. Значит система совместна.

Нужно решить систему \(N\equiv -1\pmod 3\), \(N\equiv -2\pmod 5\), \(N\equiv -3\pmod 7\), \(N\equiv -4\pmod {11}\), \(N\equiv -5\pmod {13}\). Модули попарно взаимно просты, значит по CRT есть решение по модулю \(M=3\cdot 5\cdot 7\cdot 11\cdot 13\). Если \(N_0\) — одно решение, то все \(N=N_0+tM\) тоже решения. Таких \(N\) бесконечно много.

Потребуем \(n\equiv 0\pmod 5\), \(n+2\equiv 0\pmod 7\), \(n+6\equiv 0\pmod {11}\). Это система \(n\equiv 0\pmod 5\), \(n\equiv 5\pmod 7\), \(n\equiv 5\pmod {11}\). Модули взаимно просты, поэтому есть решение \(n_0\) по модулю \(385\). Все \(n=n_0+385t\) имеют те же делимости. При достаточно больших \(t\) числа \(n,n+2,n+6\) больше соответствующих делителей, значит составные. Таких \(t\) бесконечно много.

Модули \(8,3,5,7\) попарно взаимно просты. По модулю \(8\) все нечётные остатки \(1,3,5,7\) дают квадрат \(1\), значит \(4\) решения. По каждому из модулей \(3,5,7\) есть по \(2\) решения: \(\pm 1\). Всего по CRT получаем \(4\cdot 2\cdot 2\cdot 2=32\) решения.

Для \(k=2\) это обычная CRT. Пусть утверждение верно для \(k-1\) модулей. Тогда первые \(k-1\) условий дают одно сравнение \(x\equiv r\pmod M\), где \(M=m_1\cdots m_{k-1}\). Так как \(m_k\) взаимно просто с каждым \(m_i\), имеем \(\gcd(M,m_k)=1\). По CRT система \(x\equiv r\pmod M\), \(x\equiv r_k\pmod {m_k}\) совместна. Индукция завершена.

Пусть \(A=(k+1)!\). Тогда числа \(A+2,A+3,\ldots,A+(k+1)\) образуют \(k\) последовательных чисел. Для каждого \(j=2,\ldots,k+1\) число \(A+j\) делится на \(j\), потому что \(A\) делится на \(j\). Кроме того, \(A+j>j\), значит \(A+j\) составное. Получен нужный блок.

Выберем различные простые \(p_1,\ldots,p_k>k\). Рассмотрим систему \(N+i\equiv 0\pmod {p_i}\) для \(i=1,\ldots,k\), то есть \(N\equiv -i\pmod {p_i}\). Модули попарно взаимно просты, поэтому по CRT есть решение \(N_0\) по модулю \(P=p_1\cdots p_k\). Все числа \(N=N_0+tP\) также подходят. При достаточно большом \(t\) имеем \(N+i>p_i\), значит каждое \(N+i\) составное и имеет назначенный простой делитель \(p_i>k\).

Так как \(m_i>1\), можно выбрать остаток \(b_i\), отличный от \(a_i\) по модулю \(m_i\). По CRT существует \(x_0\), такое что \(x_0\equiv b_i\pmod {m_i}\) для всех \(i\). Тогда все числа \(x=x_0+tM\), где \(M=m_1\cdots m_k\), имеют те же остатки по всем модулям. Следовательно, они избегают всех запрещённых классов, и таких чисел бесконечно много.

Выберем попарно различные простые \(p_1,\ldots,p_k\), настолько большие, что \(p_i>|a_i-a_j|\) для всех \(i,j\), и \(p_i>0\). Система \(N\equiv -a_i\pmod {p_i}\) совместна по CRT. Пусть \(N_0\) — решение, \(P=p_1\cdots p_k\). Тогда \(N=N_0+tP\) сохраняет все делимости \(p_i\mid N+a_i\). При достаточно больших \(t\) все \(N+a_i\) положительны и больше \(p_i\), значит составные. Таких \(t\) бесконечно много.

Для нечётного простого \(p\) сравнение \(u^2\equiv 1\pmod p\) имеет только решения \(u\equiv \pm 1\pmod p\), потому что \((u-1)(u+1)\equiv 0\pmod p\). Поэтому требование “не сравнимо с \(\pm 1\) ни по одному модулю \(p_i\)” несовместимо с \(x^2\equiv 1\pmod {p_i}\) для любого нечётного простого. Значит такого \(x\) не существует ни при каких \(p_i\). Ответ: утверждение неверно.