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

\(153=9\cdot17\), значит, \(9\mid153\). \(154=11\cdot14\), значит, \(11\mid154\). \(221=13\cdot17\), значит, \(13\mid221\). Все три утверждения верны.

Пусть \(a=5x\), \(b=5y\), где \(x,y\) - целые. Тогда \(7a+4b=35x+20y=5(7x+4y)\). Следовательно, \(5\mid 7a+4b\).

\(1260=126\cdot10=(2\cdot3^2\cdot7)(2\cdot5)=2^2\cdot3^2\cdot5\cdot7\).

\(840=84\cdot10=(2^2\cdot3\cdot7)(2\cdot5)=2^3\cdot3\cdot5\cdot7\). Поэтому число делителей равно \((3+1)(1+1)(1+1)(1+1)=32\).

Если \(d\mid n\), то вместе с \(d\) есть парный делитель \(\frac nd\). Разные делители образуют пары, кроме случая \(d=\frac nd\), то есть \(d^2=n\). Поэтому непарный делитель существует ровно тогда, когда \(n\) - квадрат. Следовательно, количество делителей нечетно ровно для полных квадратов.

Среди трех последовательных чисел одно делится на \(3\), а хотя бы одно четно. Значит, произведение делится на \(3\) и на \(2\). Так как \(\gcd(2,3)=1\), произведение делится на \(6\).

Среди четырех последовательных чисел одно делится на \(3\). Также среди них есть два четных числа, одно из которых делится на \(4\). Эти два четных числа вместе дают множитель \(8\). Следовательно, произведение делится на \(8\cdot3=24\).

Из \(a\mid b\) следует \(b=ak\), а из \(b\mid c\) следует \(c=bm\), где \(k,m\) - целые. Тогда \(c=(ak)m=a(km)\). Так как \(km\) - целое число, \(a\mid c\).

Имеем \(n\equiv -3\pmod{n+3}\). Поэтому \(n^2+n+1\equiv 9-3+1=7\pmod{n+3}\). Значит, \(n+3\mid7\). Отсюда \(n+3=\pm1,\pm7\), то есть \(n=-2,-4,4,-10\). Проверка обратной подстановкой подтверждает все четыре значения.

Если \(p>3\), то \(p\not\equiv0\pmod3\). При \(p\equiv1\pmod3\) число \(p+8\equiv0\pmod3\), а при \(p\equiv2\pmod3\) число \(p+4\equiv0\pmod3\). В обоих случаях одно из чисел больше \(3\) и делится на \(3\), значит, составное. Проверяем \(p=3\): получаем \(3,7,11\), все простые. Ответ: \(p=3\).

Варианты для произведения \((\alpha_i+1)\): \(12\), \(6\cdot2\), \(4\cdot3\), \(3\cdot2\cdot2\). Они дают кандидатов \(2^{11}\), \(2^5\cdot3=96\), \(2^3\cdot3^2=72\), \(2^2\cdot3\cdot5=60\). Наименьшее из них \(60\). У числа \(60=2^2\cdot3\cdot5\) действительно \((2+1)(1+1)(1+1)=12\) делителей.

Показатель двойки можно выбрать как \(1,2,3,4,5\): \(5\) вариантов. Показатель \(3\) имеет \(3\) варианта: \(0,1,2\). Показатель \(5\) имеет \(2\) варианта: \(0,1\). Итого \(5\cdot3\cdot2=30\) четных делителей.

Имеем \(n(n^2-1)(n^2-4)=n(n-1)(n+1)(n-2)(n+2)\), то есть произведение пяти последовательных целых чисел \(n-2,n-1,n,n+1,n+2\). Среди них есть число, делящееся на \(5\), есть число, делящееся на \(3\), и достаточно множителей \(2\), чтобы получить \(8\): среди пяти последовательных чисел есть либо число, делящееся на \(4\), и еще одно четное число, либо число, делящееся на \(8\). Значит, произведение делится на \(8\cdot3\cdot5=120\).

Для любого \(n\) произведение трех последовательных чисел делится на \(6\), значит, \(m=6\) подходит. Если некоторое \(m\) подходит для всех \(n\), то при \(n=1\) оно делит \(1\cdot2\cdot3=6\). Поэтому \(m\le 6\) в смысле делимости, и наибольшее \(m\) равно \(6\).

Произведение четырех последовательных чисел всегда делится на \(24\): среди них есть множитель \(3\), а два четных числа вместе дают множитель \(8\). Значит, \(24\) подходит. Если \(m\) подходит для всех \(n\), то при \(n=1\) оно делит \(1\cdot2\cdot3\cdot4=24\). Следовательно, наибольшее \(m=24\).

Если \(2n+1\mid n^2+n+3\), то \(2n+1\mid 4(n^2+n+3)\). Но \(4(n^2+n+3)=4n^2+4n+12=(2n+1)^2+11\). Значит, \(2n+1\mid 11\). Так как \(n\) положительно, \(2n+1\ge3\), поэтому \(2n+1=11\), откуда \(n=5\). Проверка: \(n^2+n+3=33\), \(2n+1=11\), подходит.

Так как \(p>3\) - простое, оно нечетно и не делится на \(3\). Числа \(p-1\) и \(p+1\) - два соседних четных числа; одно из них делится на \(4\), другое на \(2\), значит, их произведение делится на \(8\). Кроме того, среди \(p-1,p,p+1\) одно число делится на \(3\), но \(p\) не делится на \(3\), значит, \(3\mid(p-1)(p+1)\). Так как \(8\) и \(3\) взаимно просты, \(24\mid p^2-1\).

Если \(p\ne3\), то \(p^2\equiv1\pmod3\), поэтому \(p^2+2\equiv0\pmod3\). При \(p>3\) это число больше \(3\), значит, оно составное. При \(p=2\) получаем \(p^2+2=6\), тоже составное. При \(p=3\) получаем \(11\), простое. Ответ: \(p=3\).

Пусть \(p^\alpha\) - степень простого \(p\) в разложении \(a\), а \(p^\beta\) - в разложении \(b\). Из \(a^2\mid b^2\) следует \(2\alpha\le2\beta\), значит, \(\alpha\le\beta\). Это верно для каждого простого \(p\), поэтому все простые степени числа \(a\) входят в \(b\). Следовательно, \(a\mid b\).

Если \(n=p^2\), где \(p\) простое, то его делители: \(1,p,p^2\), их ровно \(3\). Обратно, пусть \(n=q_1^{\alpha_1}\cdots q_s^{\alpha_s}\). Тогда \(\tau(n)=(\alpha_1+1)\cdots(\alpha_s+1)=3\). Так как \(3\) простое, произведение может иметь только один множитель, равный \(3\). Значит, \(s=1\) и \(\alpha_1=2\), то есть \(n=q_1^2\), квадрат простого.

Каждое число от \(1\) до \(2n\) единственно представляется в виде \(2^tq\), где \(q\) нечетно. Возможных нечетных \(q\) не больше \(n\): это \(1,3,5,\ldots,2n-1\). Среди \(n+1\) выбранных чисел по принципу Дирихле найдутся два с одинаковой нечетной частью \(q\): \(2^aq\) и \(2^bq\), где пусть \(a

Если \(\tau(n)=15\), то возможны структуры \(p^{14}\) или \(p^4q^2\). Первый вариант невыгоден и, чтобы делиться на \(12\), потребовал бы огромного числа. Во втором варианте нужно поставить больший показатель на меньший простой. Так как число должно делиться на \(12=2^2\cdot3\), берем \(2^4\cdot3^2=144\). У него \((4+1)(2+1)=15\) делителей, и оно делится на \(12\). Вариант \(2^2\cdot3^4=324\) больше, а добавление других простых увеличит число. Ответ: \(144\).

По модулю \(2\) всегда \(n^5\equiv n\), значит, \(2\mid n^5-n\). По модулю \(3\) проверяем остатки \(0,1,2\): в каждом случае \(n^5\equiv n\). По модулю \(5\) также для остатков \(0,\pm1,\pm2\) получаем \(n^5\equiv n\). Значит, \(30=2\cdot3\cdot5\mid n^5-n\) для всех \(n\). С другой стороны, при \(n=2\) имеем \(2^5-2=30\), поэтому любой универсальный делитель \(m\) должен делить \(30\). Следовательно, наибольшее \(m=30\).

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

\(\gcd(252,198)=\gcd(198,54)=\gcd(54,36)=\gcd(36,18)=18\). Ответ: \(18\).

\(84=2^2\cdot3\cdot7\), \(126=2\cdot3^2\cdot7\). Поэтому \(\gcd=2\cdot3\cdot7=42\), \(\operatorname{lcm}=2^2\cdot3^2\cdot7=252\).

\(96=2^5\cdot3\), \(180=2^2\cdot3^2\cdot5\). Тогда \(\gcd=2^2\cdot3=12\), \(\operatorname{lcm}=2^5\cdot3^2\cdot5=1440\). Получаем \(96\cdot180=17280\) и \(12\cdot1440=17280\).

Если \(d\mid n\) и \(d\mid n+1\), то \(d\mid(n+1)-n=1\). Значит, \(d=1\). Поэтому \(\gcd(n,n+1)=1\).

Любой общий делитель \(d\) чисел \(n\) и \(2n+1\) делит \(2n\), а значит, делит \((2n+1)-2n=1\). Поэтому \(d=1\), и НОД равен \(1\).

\(\gcd(48,180)=12\), \(\operatorname{lcm}(48,180)=720\). Так как оба числа умножены на \(n\), получаем \(\gcd(48n,180n)=12n\) и \(\operatorname{lcm}(48n,180n)=720n\).

Имеем \(90n=18\cdot630\), откуда \(n=126\). Проверка: \(\gcd(126,90)=18\), \(\operatorname{lcm}(126,90)=630\), значит, ответ верен.

Пусть \(d=\gcd(n,n+2)\). Тогда \(d\mid(n+2)-n=2\), значит, \(d\in\{1,2\}\). Если \(n\) четно, то оба числа четны и НОД равен \(2\). Если \(n\) нечетно, оба числа нечетны, общего делителя \(2\) нет, значит, НОД равен \(1\).

Если \(d\mid n\) и \(d\mid n^2+n+1\), то \(d\mid n(n+1)\). Тогда \(d\) делит разность \((n^2+n+1)-n(n+1)=1\). Значит, \(d=1\).

Пусть \(d\mid a+b\) и \(d\mid a-b\). Тогда \(d\mid (a+b)+(a-b)=2a\) и \(d\mid(a+b)-(a-b)=2b\). Так как \(\gcd(a,b)=1\), общий делитель не может содержать нечетный простой множитель. Поэтому \(d\mid2\).

По модулю \(n+2\) имеем \(n\equiv -2\). Тогда \(n^2+3n+5\equiv4-6+5=3\). Следовательно, \(\gcd(n+2,n^2+3n+5)=\gcd(n+2,3)\). Он больше \(1\) тогда и только тогда, когда \(3\mid n+2\), то есть \(n\equiv1\pmod3\).

\(36n=12\cdot180\), значит, \(n=60\). Проверяем: \(\gcd(60,36)=12\), \(\operatorname{lcm}(60,36)=180\). Ответ: \(60\).

Предположим, что простой \(p\) делит и \(a+b\), и \(ab\). Из \(p\mid ab\) следует \(p\mid a\) или \(p\mid b\). Если \(p\mid a\), то из \(p\mid a+b\) получаем \(p\mid b\), противоречие с \(\gcd(a,b)=1\). Случай \(p\mid b\) аналогичен. Значит, общих простых делителей нет, и НОД равен \(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\).

По модулю \(n-1\) имеем \(n\equiv1\). Тогда \(n^2+n+1\equiv1+1+1=3\). Следовательно, НОД равен \(\gcd(n-1,3)\), значит, он делит \(3\). Он равен \(3\) тогда и только тогда, когда \(3\mid n-1\), то есть \(n\equiv1\pmod3\).

Для чисел вида \(a^m-1\) верно \(\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1\). Поэтому искомый НОД равен \(2^6-1=63\).

Если простой \(p\) делит \(a^m\), то \(p\mid a\). Если бы тот же \(p\) делил \(b^n\), то \(p\mid b\), что противоречит \(\gcd(a,b)=1\). Значит, общих простых делителей у \(a^m\) и \(b^n\) нет, и их НОД равен \(1\).

Пусть \(d=\gcd(a^2+b^2,a+b)\). Тогда \(a\equiv -b\pmod d\), поэтому \(a^2+b^2\equiv2b^2\pmod d\). Значит, \(d\mid2b^2\). Но \(\gcd(a+b,b)=\gcd(a,b)=1\), следовательно, \(\gcd(d,b)=1\). Поэтому из \(d\mid2b^2\) получаем \(d\mid2\).

По модулю \(n+6\) имеем \(n\equiv -6\), поэтому \(n^2+4\equiv36+4=40\). Значит, НОД равен \(\gcd(n+6,40)\). Он больше \(1\), если \(n+6\) делится на \(2\) или \(5\). Поэтому \(n\) четно или \(n\equiv4\pmod5\).

Пусть \(d=\gcd(n^2+n+1,n^2+2n+3)\). Тогда \(d\mid(n^2+2n+3)-(n^2+n+1)=n+2\). По модулю \(d\) имеем \(n\equiv-2\), поэтому из \(d\mid n^2+n+1\) получаем \(d\mid4-2+1=3\). Значит, \(d\) равен \(1\) или \(3\). Оба выражения делятся на \(3\) тогда и только тогда, когда \(n\equiv1\pmod3\). Следовательно, НОД равен \(3\) при \(n\equiv1\pmod3\), и \(1\) иначе.

Пусть \(m\ge n\) и \(m=qn+r\). Так как \(a^n\equiv1\pmod{a^n-1}\), имеем \(a^m=a^{qn+r}\equiv a^r\pmod{a^n-1}\). Поэтому \(\gcd(a^m-1,a^n-1)=\gcd(a^r-1,a^n-1)\). Это ровно шаг алгоритма Евклида для пары показателей \((m,n)\). Повторяя, приходим к \(d=\gcd(m,n)\). Тогда НОД равен \(a^d-1\).

Пусть \(a=12x\), \(b=12y\), \(\gcd(x,y)=1\). Тогда \(\operatorname{lcm}(a,b)=12xy=720\), значит, \(xy=60\). Так как \(x\) и \(y\) взаимно просты, каждая простая степень из \(60=2^2\cdot3\cdot5\) целиком идет либо в \(x\), либо в \(y\). Неупорядоченные пары \((x,y)\): \((1,60)\), \((3,20)\), \((4,15)\), \((5,12)\). Поэтому пары \((a,b)\): \((12,720)\), \((36,240)\), \((48,180)\), \((60,144)\).

В полном кубе все показатели простых кратны \(3\). Чтобы куб делился на \(18=2\cdot3^2\), показатель двойки должен быть хотя бы \(3\), и показатель тройки тоже хотя бы \(3\). Значит, каждый такой куб делится на \(2^3\cdot3^3=216\). Это значение достижимо: можно взять все три куба равными \(216=6^3\). Поэтому наименьший возможный НОД равен \(216\).

Пусть \(d=\gcd(a,b)\), \(a=dx\), \(b=dy\), где \(\gcd(x,y)=1\). Тогда \(\operatorname{lcm}(a,b)=dxy\), а \(a+b=d(x+y)\). Так как \(\gcd(x+y,xy)=1\), получаем \(\gcd(a+b,\operatorname{lcm}(a,b))=d\). Значит, \(d=\gcd(154,840)=14\).

Тогда \(a=14x\), \(b=14y\), \(x+y=11\), а \(\operatorname{lcm}(a,b)=14xy=840\), то есть \(xy=60\). Числа \(x,y\) - корни уравнения \(t^2-11t+60=0\), откуда \(\{x,y\}=\{5,6\}\). Следовательно, \(\{a,b\}=\{70,84\}\).

\(7\cdot289=2023\), поэтому \(2026=7\cdot289+3\). Остаток равен \(3\).

Если \(n=2k\), то \(n^2=4k^2\equiv0\pmod4\). Если \(n=2k+1\), то \(n^2=4k^2+4k+1\equiv1\pmod4\).

Квадраты остатков \(0,1,2,3,4,5,6,7\) по модулю \(8\) равны \(0,1,4,1,0,1,4,1\). Значит, возможны только \(0,1,4\).

Последние цифры степеней \(3\): \(3,9,7,1\), цикл длины \(4\). Так как \(2025\equiv1\pmod4\), последняя цифра равна \(3\).

Квадраты по модулю \(5\): \(0^2\equiv0\), \(1^2\equiv1\), \(2^2\equiv4\), \(3^2\equiv4\), \(4^2\equiv1\). Подходят \(n\equiv1\) и \(n\equiv4\pmod5\).

Квадрат по модулю \(4\) равен \(0\) или \(1\). Поэтому \(x^2+y^2\) может иметь остаток \(0,1,2\), но не \(3\). Правая часть имеет остаток \(3\). Противоречие.

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

Таблица значений \(n^2+n+1\) по модулю \(7\) для \(n=0,1,2,3,4,5,6\): \(1,3,0,6,0,3,1\). Поэтому \(n\equiv2\) или \(n\equiv4\pmod7\).

Любой квадрат по модулю \(4\) равен \(0\) или \(1\). Остатки \(2\) и \(3\) не появляются, значит, квадрат не может иметь такие остатки.

Цикл: \(7,9,3,1\). Так как \(2026\equiv2\pmod4\), берем вторую цифру цикла. Ответ: \(9\).

Если \(n\equiv0\pmod2\), то \(n^2+n\equiv0\). Если \(n\equiv1\pmod2\), то \(n^2+n\equiv1+1\equiv0\pmod2\). Значит, выражение всегда четно.

Каждый куб по модулю \(9\) равен \(0,\pm1\). Сумма трех таких остатков лежит среди \(-3,-2,-1,0,1,2,3\), то есть по модулю \(9\) среди \(6,7,8,0,1,2,3\). Остатков \(4\) и \(5\) нет.

Квадрат по модулю \(8\) равен \(0,1\) или \(4\). Сумма трех таких остатков может дать \(0,1,2,3,4,5,6\), но не \(7\). Поэтому сумма трех квадратов не может быть сравнима с \(7\) по модулю \(8\). Число \(8t+7\) как раз имеет остаток \(7\). Противоречие.

Правая часть \(3y^2+2\equiv2\pmod3\). Но квадрат по модулю \(3\) равен только \(0\) или \(1\). Значит, левая часть не может иметь остаток \(2\). Противоречие.

Если число не делится на \(3\), его квадрат имеет остаток \(1\) по модулю \(3\). Если хотя бы одно из \(x,y\) не делится на \(3\), сумма квадратов имеет остаток \(1\) или \(2\), но не \(0\), кроме случая когда оба квадрата дают \(0\). Поэтому \(x\) и \(y\) оба делятся на \(3\).

Проверка остатков по модулю \(13\) дает нули только при \(n\equiv3\) и \(n\equiv9\). Действительно, \(3^2+3+1=13\), \(9^2+9+1=91=7\cdot13\). Другие остатки дают ненулевые значения. Ответ: \(n\equiv3\) или \(9\pmod{13}\).

Для \(n=0,1,\ldots,10\) значения \(n^2+n+1\) по модулю \(11\) равны \(1,3,7,2,10,9,10,2,7,3,1\). Нуля среди них нет, значит, делимость на \(11\) невозможна.

Если \(x\) четно, то \(x^4\equiv0\pmod{16}\); если \(x\) нечетно, то \(x^2\equiv1\) или \(9\pmod{16}\), а \(x^4\equiv1\pmod{16}\). Значит, \(x^4+y^4\) может иметь остаток \(0,1,2\), но не \(15\). Правая часть имеет остаток \(15\). Противоречие.

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

\(3^{20}=(3^4)^5=81^5\). По модулю \(100\): \(81^2\equiv61\), \(81^4\equiv61^2\equiv21\), \(81^5\equiv21\cdot81\equiv1\). Значит, последние две цифры: \(01\).

Из уравнения следует \(3\mid x^2+y^2\). По таблице квадратов modulo \(3\) получаем \(3\mid x\) и \(3\mid y\). Пусть \(x=3x_1\), \(y=3y_1\). Тогда \(9x_1^2+9y_1^2=3z^2\), значит, \(z^2=3(x_1^2+y_1^2)\), и \(3\mid z\). Получаем, что все \(x,y,z\) делятся на \(3\). Если есть ненулевое решение, можно делить все три числа на \(3\) бесконечно, что невозможно для ненулевых целых чисел. Значит, ненулевых решений нет.

По модулю \(5\) получаем \(x^2\equiv2\pmod5\). Но квадраты по модулю \(5\) равны только \(0,1,4\). Остаток \(2\) невозможен. Значит, решений нет.

Квадратичные остатки по модулю \(7\): \(0,1,2,4\). Чтобы сумма двух таких остатков была \(0\), возможен только вариант \(0+0\): числа \(1,2,4\) имеют противоположные остатки \(6,5,3\), которые квадратами не являются. Значит, \(x^2\equiv0\) и \(y^2\equiv0\pmod7\), откуда \(7\mid x\) и \(7\mid y\).

Из задачи о трех квадратах по модулю \(8\) следует: сумма трех квадратов не может иметь остаток \(7\) по модулю \(8\). Поэтому ни одно число вида \(8t+7\) не представляется в виде \(x^2+y^2+z^2\). Таких натуральных чисел бесконечно много: \(7,15,23,31,\ldots\). Следовательно, требуемых чисел бесконечно много.

\(x\equiv1-3\equiv-2\equiv5\pmod7\).

\(3\cdot5=15\equiv1\pmod7\). Значит, \(x\equiv5\pmod7\).

\(5\cdot5=25\equiv1\pmod{12}\). Поэтому обратный элемент к \(5\) по модулю \(12\) равен \(5\).

Числа, равные \(2\) по модулю \(3\): \(2,5,8,11,\ldots\). Из них \(11\equiv1\pmod5\). Значит, \(x\equiv11\pmod{15}\).

Число \(2x\) четно, значит, по модулю \(4\) оно может иметь остаток \(0\) или \(2\). Остаток \(1\) невозможен. Также \(\gcd(2,4)=2\nmid1\), поэтому решений нет.

\(\gcd(4,10)=2\), и \(2\mid6\). Делим на \(2\): \(2x\equiv3\pmod5\). Обратный к \(2\) по модулю \(5\) равен \(3\), значит, \(x\equiv9\equiv4\pmod5\). По модулю \(10\): \(x\equiv4\) или \(9\).

Делим \(6,12,18\) на \(6\): \(x\equiv2\pmod3\). По модулю \(18\) это классы \(2,5,8,11,14,17\).

Получаем \(3x\equiv2\pmod5\). Обратный к \(3\) по модулю \(5\) равен \(2\), поэтому \(x\equiv4\pmod5\). По модулю \(15\): \(x\equiv4,9,14\).

Из чисел \(3,7,11,15,19,\ldots\), сравнимых с \(3\) по модулю \(4\), число \(7\) имеет остаток \(2\) по модулю \(5\). Ответ: \(x\equiv7\pmod{20}\).

Первое условие дает \(x\equiv2\pmod3\). Второе дает \(x\equiv0\pmod3\). Это невозможно одновременно. Решений нет.

Подставим: \(6k+4\equiv1\pmod9\), значит, \(6k\equiv6\pmod9\). Делим на \(3\): \(2k\equiv2\pmod3\), откуда \(k\equiv1\pmod3\). Тогда \(x=6(3t+1)+4=18t+10\). Ответ: \(x\equiv10\pmod{18}\).

Числа вида \(5k+2\): \(2,7,12,17,\ldots\). Первое из них, дающее остаток \(3\) по модулю \(7\), это \(17\). Ответ: \(17\).

Сравнение эквивалентно уравнению \(ax-my=b\) в целых \(x,y\). Все числа вида \(ax-my\) делятся на \(d=\gcd(a,m)\), значит, необходимо \(d\mid b\). Обратно, если \(d\mid b\), то по тождеству Безу существуют \(u,v\), для которых \(au+mv=d\). Умножив на \(\frac bd\), получаем представление \(b\) в виде \(aX+mY\), то есть решение сравнения.

Если \(2n+1\mid n^2+n+7\), то \(2n+1\mid4(n^2+n+7)\). Но \(4(n^2+n+7)=(2n+1)^2+27\). Значит, \(2n+1\mid27\). Для положительного \(n\): \(2n+1=3,9,27\), откуда \(n=1,4,13\). Все три подходят.

Из \(x\equiv4\pmod{12}\) следует \(x\equiv1\pmod3\). Но первое условие требует \(x\equiv2\pmod3\). Противоречие. Следовательно, решений нет.

Пусть \(x=8a+5\). Условие modulo \(9\): \(8a+5\equiv2\), то есть \(-a\equiv-3\), \(a\equiv3\pmod9\). Значит, \(x\equiv29\pmod{72}\). Теперь \(x=29+72t\), и по модулю \(5\): \(4+2t\equiv1\), откуда \(2t\equiv2\), \(t\equiv1\pmod5\). Получаем \(x\equiv101\pmod{360}\).

Сравнение \(4x\equiv8\pmod{12}\) после деления на \(4\) дает \(x\equiv2\pmod3\). Совмещаем с \(x\equiv3\pmod5\). Числа \(3,8,13,\ldots\) по модулю \(5\); число \(8\equiv2\pmod3\). Значит, \(x\equiv8\pmod{15}\). По модулю \(60\) получаем \(x\equiv8,23,38,53\).

Условия \(n\equiv1\pmod2\), \(n\equiv2\pmod3\) дают \(n\equiv5\pmod6\). Проверяем \(5,11,17,23,\ldots\); первое число, сравнимое с \(3\) по модулю \(5\), это \(23\). Ответ: \(23\).

Так как \(6\mid18\), делим на \(6\): \(2x\equiv3\pmod5\). Обратный к \(2\) по модулю \(5\) равен \(3\), поэтому \(x\equiv9\equiv4\pmod5\). По модулю \(30\): \(x\equiv4,9,14,19,24,29\).

Число \(7\) дает остаток \(3\) по модулю \(4\) и остаток \(7\) по модулю \(25\). Так как \(4\) и \(25\) взаимно просты, решение единственно по модулю \(100\). Ответ: \(x\equiv7\pmod{100}\).

Пусть \(d=\gcd(m,n)\). Если решение \(x\) есть, то \(x-r\) делится на \(m\), а \(x-s\) делится на \(n\), значит, оба делятся на \(d\). Тогда \(r-s=(x-s)-(x-r)\) делится на \(d\).

Обратно, пусть \(d\mid r-s\). Ищем \(x=r+mk\). Нужно \(r+mk\equiv s\pmod n\), то есть \(mk\equiv s-r\pmod n\). Это линейное сравнение имеет решение ровно потому, что \(\gcd(m,n)=d\mid s-r\). Значит, исходная система совместна.

Если \(3n+2\mid n^2+5n+9\), то он делит \(9(n^2+5n+9)=9n^2+45n+81\). Вычтем \((3n+2)^2=9n^2+12n+4\): получим, что \(3n+2\mid33n+77\). Теперь \(3(33n+77)-33(3n+2)=165\), значит, \(3n+2\mid165\). Положительные делители \(165\), сравнимые с \(2\) по модулю \(3\): \(5\) и \(11\). Поэтому \(3n+2=5\) или \(11\), откуда \(n=1\) или \(3\). Проверка показывает, что оба подходят.

Первые три условия дают \(n\equiv29\pmod{30}\). Пусть \(n=7k\). Тогда \(7k\equiv29\pmod{30}\). Обратный к \(7\) по модулю \(30\) равен \(13\), поэтому \(k\equiv29\cdot13\equiv17\pmod{30}\). Наименьшее положительное \(k=17\), значит, \(n=119\).

Сравнение \(6x\equiv12\pmod9\) сокращаем на \(3\): \(2x\equiv4\pmod3\), то есть \(-x\equiv1\pmod3\), значит, \(x\equiv2\pmod3\). Теперь решаем систему по взаимно простым модулям \(3,4,5,7\): \(x\equiv2\pmod3\), \(x\equiv1\pmod4\), \(x\equiv2\pmod5\), \(x\equiv3\pmod7\).

Совмещаем \(x\equiv1\pmod4\) и \(x\equiv2\pmod5\): получаем \(x\equiv17\pmod{20}\). Это число уже дает \(17\equiv2\pmod3\) и \(17\equiv3\pmod7\). Так как модули \(3,4,5,7\) взаимно просты, ответ единственен по модулю \(420\): \(x\equiv17\pmod{420}\).

Делим на \(2\): \(2x+3y=5\). Одно решение: \(x=1\), \(y=1\). Тогда все решения имеют вид \(x=1+3t\), \(y=1-2t\), где \(t\in\mathbb Z\). Проверка: \(2(1+3t)+3(1-2t)=5\).

Из \(2x=18-3y\) следует, что \(y\) четно. Так как \(y>0\) и \(3y<18\), имеем \(y=2\) или \(y=4\). Тогда \(x=6\) или \(x=3\). Ответ: \((6,2)\), \((3,4)\).

Положительные делители \(24\): \(1,2,3,4,6,8,12,24\). Для каждого \(x\) имеем \(y=\frac{24}{x}\). Поэтому получаем \((1,24)\), \((2,12)\), \((3,8)\), \((4,6)\), \((6,4)\), \((8,3)\), \((12,2)\), \((24,1)\).

Имеем \((x-y)(x+y)=15\). Положительные пары множителей одинаковой четности: \((1,15)\) и \((3,5)\). Они дают \((x,y)=(8,7)\) и \((4,1)\). Это все решения.

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

Одно решение: \(x=-3\), \(y=2\), так как \(7(-3)+11\cdot2=1\). Все решения: \(x=-3+11t\), \(y=2-7t\), где \(t\in\mathbb Z\).

По модулю \(5\): \(8y\equiv67\), то есть \(3y\equiv2\pmod5\). Отсюда \(y\equiv4\pmod5\). Поскольку \(8y<67\), имеем \(y\le8\), значит, \(y=4\). Тогда \(x=\frac{67-32}{5}=7\). Ответ: \((7,4)\).

Получаем \((x+1)(y+1)=48\). Значит, \(x+1\) и \(y+1\) - делители \(48\), не меньшие \(2\). Отсюда решения: \((1,23)\), \((2,15)\), \((3,11)\), \((5,7)\), \((7,5)\), \((11,3)\), \((15,2)\), \((23,1)\).

Имеем \(xy-2x-5y=0\), значит, \((x-5)(y-2)=10\). Положительные делители \(10\): \(1,2,5,10\). Поэтому решения: \((6,12)\), \((7,7)\), \((10,4)\), \((15,3)\).

\((x-y)(x+y)=56\). Оба множителя должны иметь одинаковую четность, значит, оба четны. Подходящие пары: \((2,28)\) и \((4,14)\). Получаем \((x,y)=(15,13)\) и \((9,5)\).

Из \(8x+8y=xy\) получаем \(xy-8x-8y=0\), значит, \((x-8)(y-8)=64\). Поэтому \(x=8+d\), \(y=8+\frac{64}{d}\), где \(d\) пробегает положительные делители \(64\).

По модулю \(3\) получаем \(x^2\equiv2\pmod3\). Но квадрат по модулю \(3\) может иметь только остаток \(0\) или \(1\). Противоречие. Решений нет.

Имеем \(xy+2x+3y+6=60\), то есть \((x+3)(y+2)=60\). Поскольку \(x\ge1\), \(y\ge1\), нужно \(x+3\ge4\), \(y+2\ge3\). Проверяя делители \(60\), получаем решения \((1,13)\), \((2,10)\), \((3,8)\), \((7,4)\), \((9,3)\), \((12,2)\), \((17,1)\).

\((x-y)(x+y)=68\). Подходящие положительные пары одной четности: только \((2,34)\). Пара \((4,17)\) не подходит по четности. Отсюда \(x=\frac{2+34}{2}=18\), \(y=\frac{34-2}{2}=16\). Ответ: \((18,16)\).

Умножаем: \(10x+10y=xy\). Тогда \(xy-10x-10y=0\), и \((x-10)(y-10)=100\). Следовательно, \(x=10+d\), \(y=10+\frac{100}{d}\), где \(d\) - положительный делитель \(100\). Это полное описание всех решений.

Перепишем: \((x+1)^2-y^2=21\). Тогда \((x+1-y)(x+1+y)=21\). Пары положительных множителей: \((1,21)\) и \((3,7)\). Они дают соответственно \((x,y)=(10,10)\) и \((4,2)\). Других решений нет.

Имеем \(xy-x-2y+2=19\), то есть \((x-2)(y-1)=19\). Так как \(19\) простое, возможны пары множителей \((1,19)\) и \((19,1)\). Получаем \((x,y)=(3,20)\) и \((21,2)\).

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

Получаем \(xy-x-y+1=2\), то есть \((x-1)(y-1)=2\). Поэтому \((x-1,y-1)=(1,2)\) или \((2,1)\). Ответ: \((2,3)\), \((3,2)\).

Из \(xy-4x-4y=5\) получаем \((x-4)(y-4)=21\). Положительные делители \(21\): \(1,3,7,21\). Отсюда решения \((5,25)\), \((7,11)\), \((11,7)\), \((25,5)\). Отрицательные множители не дают положительных \(x,y\).

Уравнение равносильно \((x-y)^2=x+y\). Если \(x=y\), получаем \(0=2x\), что невозможно для положительного \(x\). Пусть \(x>y\) и \(d=x-y\). Тогда \(d^2=2y+d\), откуда \(y=\frac{d^2-d}{2}\), \(x=\frac{d^2+d}{2}\). Нужно \(d\ge2\). Так как уравнение симметрично, все решения имеют вид \(\left(\frac{d(d+1)}{2},\frac{d(d-1)}{2}\right)\) и \(\left(\frac{d(d-1)}{2},\frac{d(d+1)}{2}\right)\), где \(d\ge2\) - целое.

Пусть \(x\le y\). Тогда \(xy\le x+y+2\). Если \(x\ge3\), то \(xy\ge3y\), а \(x+y+2\le2y+2\), что невозможно при \(y\ge3\). Значит, \(x=1\) или \(x=2\). При \(x=1\): \(y\mid y+3\), значит, \(y\mid3\), и \(y=1,3\). При \(x=2\): \(2y\mid y+4\), поэтому \(y\le4\); проверка \(y=2,3,4\) дает только \(y=4\). С учетом симметрии: \((1,1)\), \((1,3)\), \((3,1)\), \((2,4)\), \((4,2)\).

Разложим: \((x-y)(x+y)=2(x+y)+15\). Тогда \((x+y)(x-y-2)=15\). Пусть \(A=x+y\), \(B=x-y-2\). Имеем \(AB=15\), \(A>0\), \(B>0\). Проверяем пары \((15,1)\), \((5,3)\), \((3,5)\), \((1,15)\). Так как \(y=\frac{A-B-2}{2}\), положительное \(y\) получается только для \((A,B)=(15,1)\). Тогда \(y=6\), \(x=9\). Ответ: \((9,6)\).

Уравнение симметрично, поэтому считаем \(x\ge y\). Тогда \(x^2\le x^2+xy+y^2=x+y+30\le2x+30\). Значит, \(x^2-2x-30\le0\), откуда \(x\le6\).

Проверяем \(x=1,2,3,4,5,6\) в уравнении как квадратное относительно \(y\). При \(x=1\) получаем \(y^2=30\), нет решений. При \(x=2\): \(y^2+y-28=0\), нет целого положительного \(y\). При \(x=3\): \(y^2+2y-24=0\), \(y=4\), но это противоречит \(x\ge y\). При \(x=4\): \(y^2+3y-18=0\), \(y=3\). При \(x=5\): \(y^2+4y-10=0\), нет целого \(y\). При \(x=6\): \(y^2+5y=0\), нет положительного \(y\). Значит, при \(x\ge y\) есть только \((4,3)\). По симметрии также есть \((3,4)\). Ответ: \((4,3)\), \((3,4)\).

Если \(a\) нечетно, то \(a=2k+1\). Тогда \(a^2=4k^2+4k+1\), что нечетно. Значит, при четном \(a^2\) число \(a\) не может быть нечетным, то есть \(a\) четно.

Так как \(a^2=a\cdot a\) и простое \(p\) делит это произведение, то по лемме Евклида \(p\) делит хотя бы один из множителей. Оба множителя равны \(a\), значит, \(p\mid a\).

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

Пусть \(\sqrt{2}=\frac{a}{b}\), где \(\gcd(a,b)=1\). Тогда \(a^2=2b^2\). Из этого следует, что \(a\) четно, \(a=2c\). Тогда \(4c^2=2b^2\), значит, \(b^2=2c^2\), и \(b\) четно. Получили общий делитель \(2\) у \(a\) и \(b\), противоречие.

Из \(x^2=3y^2\) следует \(3\mid x^2\), значит, \(x=3u\). Тогда \(9u^2=3y^2\), откуда \(y^2=3u^2\). Следовательно, \(3\mid y\). Деление \(x\) и \(y\) на \(3\) дает меньшее положительное решение, что невозможно по спуску.

Пусть \(\sqrt{3}=\frac{a}{b}\), \(\gcd(a,b)=1\). Тогда \(a^2=3b^2\), значит, \(3\mid a\), \(a=3c\). Получаем \(9c^2=3b^2\), то есть \(b^2=3c^2\), и \(3\mid b\). Противоречие с \(\gcd(a,b)=1\).

Пусть \(\sqrt{5}=\frac{a}{b}\) в несократимом виде. Тогда \(a^2=5b^2\), откуда \(5\mid a\). Пусть \(a=5c\). Тогда \(25c^2=5b^2\), значит, \(b^2=5c^2\), и \(5\mid b\). Противоречие с несократимостью дроби.

Из \(x^2=8y^2\) следует, что \(x\) четно. Пусть \(x=2u\). Тогда \(4u^2=8y^2\), то есть \(u^2=2y^2\). Но такое уравнение не имеет положительных целых решений. Значит, исходное уравнение тоже не имеет решений.

Из \(x^2=12y^2\) следует, что \(x\) четно: \(x=2u\). Тогда \(4u^2=12y^2\), то есть \(u^2=3y^2\). Но уравнение \(u^2=3y^2\) не имеет положительных целых решений по спуску с простым \(3\). Противоречие.

Квадраты по модулю \(3\) дают только \(0\) и \(1\). Чтобы сумма двух таких остатков делилась на \(3\), единственная возможность - \(0+0\). Значит, \(x^2\equiv0\pmod3\) и \(y^2\equiv0\pmod3\). Поэтому \(3\mid x\) и \(3\mid y\).

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

Квадраты по модулю \(5\): \(0,1,4\). Тогда \(2y^2\) может иметь остатки \(0,2,3\). Сумма \(x^2+2y^2\) может быть \(0\) по модулю \(5\) только в случае \(0+0\). Значит, \(x^2\equiv0\) и \(y^2\equiv0\pmod5\), откуда \(5\mid x\), \(5\mid y\).

Из \(5\mid x^2+2y^2\) следует \(5\mid x\), \(5\mid y\). Пусть \(x=5x_1\), \(y=5y_1\). Тогда \(25x_1^2+50y_1^2=5z^2\), откуда \(z^2=5x_1^2+10y_1^2\), значит, \(5\mid z\). Делим все переменные на \(5\) и получаем меньшее положительное решение. Спуск невозможен.

Квадратичные остатки по модулю \(7\): \(0,1,2,4\). Ни две ненулевые величины из множества \(\{1,2,4\}\) не дают сумму \(0\) по модулю \(7\). Поэтому \(x^2+y^2\equiv0\pmod7\) возможно только при \(x^2\equiv y^2\equiv0\pmod7\). Значит, \(7\mid x\), \(7\mid y\).

Из уравнения следует \(7\mid x^2+y^2\), значит, \(7\mid x\) и \(7\mid y\). Пусть \(x=7x_1\), \(y=7y_1\). Тогда \(49x_1^2+49y_1^2=7z^2\), откуда \(z^2=7x_1^2+7y_1^2\), значит, \(7\mid z\). Деление всех переменных на \(7\) дает меньшее решение того же вида. Бесконечный спуск невозможен.

Пусть \(\sqrt{6}=\frac{a}{b}\) в несократимом виде. Тогда \(a^2=6b^2\), значит, \(a\) четно: \(a=2c\). Получаем \(4c^2=6b^2\), то есть \(2c^2=3b^2\). Правая часть делится на \(2\), значит, \(b^2\) четно, и \(b\) четно. Это противоречит несократимости дроби.

Из \(x^2=2y^2\) следует, что \(x\) четно, \(x=2u\). Тогда \(y^2=2u^2\), значит, \(y\) четно. Поэтому \(x\) и \(y\) имеют общий делитель \(2\), что противоречит взаимной простоте.

Так как \(3\mid x^2\), имеем \(x=3u\). Тогда \(9u^2=45y^2\), откуда \(u^2=5y^2\). Но уравнение \(u^2=5y^2\) не имеет положительных целых решений: оно заставляет \(u\) и \(y\) делиться на \(5\) и запускает спуск. Противоречие.

Из \(a^2=2b^2\) следует, что \(a\) и \(b\) четны. Тогда \(a=2a_1\), \(b=2b_1\), и \(\left(\frac{a_1}{b_1}\right)^2=2\). Но \(b_1=\frac{b}{2}

Предположим, что \(3\mid x^2+y^2\). Тогда по модулю \(3\) оба квадрата должны быть \(0\), значит, \(3\mid x\) и \(3\mid y\). Это противоречит \(\gcd(x,y)=1\). Следовательно, \(x^2+y^2\) не делится на \(3\).

Предположим, что решение существует, и выберем решение с минимальной суммой \(x+y\). Если \(x=y\), то \(2x^2=3x^2\), невозможно. Пусть \(x>y\). Уравнение \(x^2-3xy+y^2=0\) как квадратное по \(x\) имеет второй корень \(x'=3y-x\). По Виету \(xx'=y^2\), значит, \(x'>0\), а так как \(x>y\), то \(x'=\frac{y^2}{x}

Как квадратное по \(x\), уравнение имеет вид \(x^2-4yx+y^2=0\). Его дискриминант должен быть квадратом: \(D=16y^2-4y^2=12y^2\). Значит, существует целое \(u\), для которого \(u^2=12y^2\). Но такое уравнение не имеет положительных целых решений, как было доказано ранее. Противоречие.

Перепишем как \(x^2-5yx+2y^2=0\). Тогда дискриминант \(D=25y^2-8y^2=17y^2\) должен быть квадратом целого числа. Это означало бы \(u^2=17y^2\) для некоторого положительного \(u\). Но уравнение \(u^2=17y^2\) невозможно по тому же спуску с простым \(17\). Противоречие.

Предположим, что решение существует, и выберем его с минимальной суммой \(x+y\). Пусть \(x\ge y\). Если \(y=1\), то \(x^2+1=3x+2\), то есть \(x^2-3x-1=0\), что не имеет целого корня.

Значит, \(y\ge2\). Рассмотрим уравнение как квадратное по \(x\): \(x^2-3yx+(y^2-2)=0\). Второй корень \(x'=3y-x\) является целым. По Виету \(xx'=y^2-2>0\), значит, \(x'>0\). Если \(x=y\), то \(2y^2=3y^2+2\), невозможно, поэтому \(x>y\). Тогда \(x'=\frac{y^2-2}{x}

Имеем \(2,4,3,1\), затем цикл повторяется с периодом \(4\). Так как \(17\equiv1\pmod4\), получаем \(2^{17}\equiv2\pmod5\).

Цикл последних цифр: \(3,9,7,1\). Поскольку \(25\equiv1\pmod4\), последняя цифра равна \(3\).

\(4^2=16\equiv2\pmod7\), \(4^3\equiv8\equiv1\pmod7\). Значит, \(4^{12}=(4^3)^4\equiv1\pmod7\).

Число \(7\) простое и \(7\nmid3\). По малой теореме Ферма \(3^6\equiv1\pmod7\). Поэтому \(7\mid3^6-1\).

\(\gcd(2,8)=2\ne1\), поэтому теорема Эйлера неприменима. Но \(2^3=8\equiv0\pmod8\), значит, любая степень \(2^n\) при \(n\ge3\) делится на \(8\). Следовательно, \(2^{10}\equiv0\pmod8\).

Так как \(11\) простое, \(5^{10}\equiv1\pmod{11}\). \(2026\equiv6\pmod{10}\), значит, \(5^{2026}\equiv5^6\). \(5^2\equiv3\), \(5^4\equiv9\), поэтому \(5^6\equiv9\cdot3=27\equiv5\pmod{11}\).

По Ферма \(2^{12}\equiv1\pmod{13}\). Так как \(100\equiv4\pmod{12}\), имеем \(2^{100}\equiv2^4=16\equiv3\pmod{13}\).

\(7^2=49\equiv4\pmod9\), \(7^3\equiv4\cdot7=28\equiv1\pmod9\). Так как \(50\equiv2\pmod3\), получаем \(7^{50}\equiv7^2\equiv4\pmod9\).

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

\(11\equiv-1\pmod{12}\). Показатель \(2025\) нечетен, поэтому \(11^{2025}\equiv(-1)^{2025}\equiv-1\equiv11\pmod{12}\).

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

Из предыдущей задачи \(\operatorname{ord}_7(3)=6\). Поэтому \(3^n\equiv1\pmod7\) тогда и только тогда, когда \(6\mid n\). Ответ: все положительные кратные \(6\).

Так как \(2026\equiv2\pmod4\), имеем \(2^{2026}\equiv2^2\equiv4\pmod5\) и \(3^{2026}\equiv3^2\equiv9\equiv4\pmod5\). Сумма дает \(4+4=8\equiv3\pmod5\).

Так как \(13\) простое и \(13\nmid5\), имеем \(5^{12}\equiv1\pmod{13}\). Тогда \(5^{12k}=(5^{12})^k\equiv1^k\equiv1\pmod{13}\). Значит, \(13\mid5^{12k}-1\).

\(9^1\equiv9\), \(9^2\equiv81\), \(9^3\equiv29\), \(9^4\equiv61\), \(9^5\equiv49\), \(9^6\equiv41\), \(9^7\equiv69\), \(9^8\equiv21\), \(9^9\equiv89\), \(9^{10}\equiv1\pmod{100}\). Так как \(2026\equiv6\pmod{10}\), получаем \(9^{2026}\equiv9^6\equiv41\pmod{100}\). Последние две цифры: \(41\).

По модулю \(4\): \(3^{2026}\equiv1\), так как показатель четный. По модулю \(7\): \(3^6\equiv1\), а \(2026\equiv4\pmod6\), значит, \(3^{2026}\equiv3^4=81\equiv4\pmod7\). Нужно число, которое равно \(1\) по модулю \(4\) и \(4\) по модулю \(7\). Это \(25\). Ответ: \(25\).

Если \(p\mid a\), то \(a^p-a\equiv0-0\equiv0\pmod p\). Если \(p\nmid a\), то по Ферма \(a^{p-1}\equiv1\pmod p\). Умножая на \(a\), получаем \(a^p\equiv a\pmod p\). В обоих случаях \(p\mid a^p-a\).

По Ферма \(a^{p-1}\equiv1\pmod p\). Но \(a\cdot a^{p-2}=a^{p-1}\). Следовательно, \(a\cdot a^{p-2}\equiv1\pmod p\), то есть \(a^{p-2}\) - обратный элемент.

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

\(2^5=32\equiv1\pmod{31}\). Так как \(1000\) делится на \(5\), имеем \(2^{1000}=(2^5)^{200}\equiv1\pmod{31}\).

При \(p=2\): \(2^2+1=5\), не делится на \(2\). Пусть \(p\) нечетное простое. По Ферма в форме \(a^p\equiv a\pmod p\) имеем \(2^p\equiv2\pmod p\). Тогда \(2^p+1\equiv3\pmod p\). Чтобы \(p\mid2^p+1\), нужно \(p\mid3\), то есть \(p=3\). Проверка: \(2^3+1=9\), делится на \(3\). Ответ: \(p=3\).

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

По Ферма \(3^p\equiv3\pmod p\) для любого простого \(p\). Поэтому \(3^p+2\equiv5\pmod p\). Если \(p\mid3^p+2\), то \(p\mid5\), значит, \(p=5\). Проверка: \(3^5+2=243+2=245\), делится на \(5\). Ответ: \(p=5\).

Из условия \(2^{2^n}\equiv-1\pmod p\). Возводя в квадрат, получаем \(2^{2^{n+1}}\equiv1\pmod p\). Значит, порядок \(2\) по модулю \(p\) делит \(2^{n+1}\). Но порядок не делит \(2^n\), потому что \(2^{2^n}\equiv-1\not\equiv1\pmod p\). Так как делители \(2^{n+1}\) являются степенями двойки, порядок равен \(2^{n+1}\). Порядок элемента по модулю простого \(p\) делит \(p-1\), следовательно, \(2^{n+1}\mid p-1\). Значит, \(p\equiv1\pmod{2^{n+1}}\).

Числа \(x\equiv1\pmod4\): \(1,5,9,13,17,\ldots\). Первое из них, дающее остаток \(2\) по модулю \(5\), равно \(17\). Ответ: \(17\), все решения \(x\equiv17\pmod{20}\).

Числа \(4,9,14,19,24,29,34,\ldots\). Первое, сравнимое с \(6\) по модулю \(7\), равно \(34\). Ответ: \(x\equiv34\pmod{35}\).

Подставим: \(8k+5\equiv7\pmod9\), значит, \(8k\equiv2\pmod9\). Так как \(8\equiv-1\), получаем \(-k\equiv2\), то есть \(k\equiv7\pmod9\). Тогда \(x=8(9t+7)+5=72t+61\). Ответ: \(x\equiv61\pmod{72}\).

Если \(x\equiv0\pmod4\), то \(x\) четно, то есть \(x\equiv0\pmod2\). Это противоречит \(x\equiv1\pmod2\). Решений нет.

Условия означают, что \(x-3\) делится и на \(5\), и на \(7\). Так как \(5\) и \(7\) взаимно просты, \(35\mid x-3\). Поэтому \(x\equiv3\pmod{35}\).

Из \(x\equiv2\pmod4\) проверяем \(2,6,10,14,\ldots\). Остаток \(1\) по модулю \(3\) впервые дает \(10\), значит, \(x\equiv10\pmod{12}\). Теперь \(10,22,34,46,58,\ldots\); первое число с остатком \(3\) по модулю \(5\) равно \(58\). Ответ: \(x\equiv58\pmod{60}\).

Получаем \(n\equiv1\pmod2\), \(n\equiv1\pmod3\), \(n\equiv2\pmod5\). Число \(7\) подходит: \(8\) делится на \(2\), \(9\) на \(3\), \(10\) на \(5\). Так как модули попарно взаимно просты, все решения \(n\equiv7\pmod{30}\), и наименьшее положительное \(n=7\).

Остатки \(5\) и \(9\) оба равны \(1\) по модулю \(4\), значит, система совместна. Проверяем числа \(5,13,21,\ldots\) по модулю \(8\); \(21\equiv9\pmod{12}\). Ответ: \(x\equiv21\pmod{24}\).

Пусть \(x=6k+4\). Тогда \(6k+4\equiv10\pmod{15}\), то есть \(6k\equiv6\pmod{15}\). Делим на \(3\): \(2k\equiv2\pmod5\), значит, \(k\equiv1\pmod5\). Тогда \(x=6(5t+1)+4=30t+10\). Ответ: \(x\equiv10\pmod{30}\).

Из \(x\equiv4\pmod6\) следует, что \(x\) четно. Из \(x\equiv9\pmod{10}\) следует, что \(x\) нечетно. Противоречие. Решений нет.

Условия равносильны \(x\equiv-1\pmod3\), \(x\equiv-1\pmod5\), \(x\equiv-1\pmod7\). Поэтому \(x+1\) делится на \(3\cdot5\cdot7=105\). Наименьшее положительное \(x=104\). Все решения: \(x\equiv104\pmod{105}\).

Первые три сравнения дают \(x\equiv23\pmod{30}\). Проверяем \(23,53,83,\ldots\) по модулю \(7\). \(53\equiv4\pmod7\). Значит, наименьшее решение \(53\), а все решения \(x\equiv53\pmod{210}\).

Пусть \(d=\gcd(m,n)\). Если решение \(x\) есть, то \(x-a\) делится на \(m\), а \(x-b\) делится на \(n\), значит, обе разности делятся на \(d\). Тогда \(a-b=(x-b)-(x-a)\) делится на \(d\).

Обратно, пусть \(d\mid a-b\). Ищем \(x=a+mt\). Нужно \(a+mt\equiv b\pmod n\), то есть \(mt\equiv b-a\pmod n\). Это линейное сравнение разрешимо, потому что \(\gcd(m,n)=d\mid b-a\). Значит, система имеет решение.

Возьмем \(n=60\). Тогда \(n+2=62\) делится на \(2\), \(n+3=63\) делится на \(3\), \(n+4=64\) делится на \(4\), \(n+5=65\) делится на \(5\). Все эти числа больше соответствующих делителей, значит, составные.

Рассмотрим числа \((k+1)!+2,(k+1)!+3,\ldots,(k+1)!+(k+1)\). Для каждого \(r=2,3,\ldots,k+1\) число \((k+1)!+r\) делится на \(r\), потому что \((k+1)!\) делится на \(r\). Оно больше \(r\), значит, составное. Таких чисел \(k\).