Глава
Теория
Пробный тур отличается от тематического листка: в условии не написано, какой метод применять. Поэтому главная цель — научиться быстро классифицировать задачу, выбрать первый осмысленный ход и не застрять в длинном переборе.
В этом модуле задачи устроены как тренировочные варианты: от коротких технических вопросов к задачам, где нужно соединить две идеи. После решения важно не только получить ответ, но и сформулировать, почему выбранный метод был естественным.
Если задача просит “докажите делимость”, разложите делитель и проверьте остатки. Если есть “найдите все \(n\)”, попробуйте получить малый делитель из выражения. Если есть “существуют ли”, подумайте о конструкции, а не о поиске маленького примера.
Для mock-тура полезно сначала пометить задачи: техника, стандартный метод, одна скрытая идея, сильная задача. Это помогает не тратить всё время на одну середину варианта.
Примеры
Задача выглядит как степень, но решается разложением делителя.
Задача. Докажите, что \(30\mid n^5-n\) для любого целого \(n\).
Нужно доказать делимость на \(2\), \(3\) и \(5\). По малой теореме Ферма или проверке остатков \(n^5\equiv n\) по модулям \(2,3,5\). Значит \(n^5-n\) делится на каждое из чисел \(2,3,5\). Они попарно взаимно просты, следовательно, \(30\mid n^5-n\).
Комментарий. Метод выбирается по разложению \(30=2\cdot3\cdot5\).
Факторизация превращает уравнение в список делителей.
Задача. Решите \(xy+2x+y=31\) в натуральных числах.
Умножать не нужно: добавим \(2\). Получаем \((x+1)(y+2)=33\). Пары делителей \(33\): \((3,11),(11,3),(33,1),(1,33)\). С учётом \(x,y>0\) подходят \((x+1,y+2)=(3,11),(11,3)\). Ответ: \((x,y)=(2,9),(10,1)\).
Комментарий. После решения обязательно проверяем положительность.
Скрытая техника — выразить многочлен через делитель.
Задача. Найдите все натуральные \(n\), для которых \(3n+1\mid n^2+n+1\).
Если \(3n+1\mid n^2+n+1\), то \(3n+1\mid9(n^2+n+1)\). Но \(9(n^2+n+1)=(3n+1)^2+3(3n+1)+5\). Значит \(3n+1\mid5\). При \(n\ge1\) имеем \(3n+1\ge4\), поэтому \(3n+1=5\), откуда \(n=\frac43\), невозможно. Ответ: решений нет.
Комментарий. Коэффициент \(9\) выбран, чтобы появился \((3n+1)^2\).
Последние цифры — это задача о цикле остатков.
Задача. Найдите последние две цифры \(13^{100}\).
Работаем по модулю \(100\). \(13^2=169\equiv69\), \(13^4\equiv69^2\equiv61\), \(13^{20}\equiv1\pmod{100}\). Тогда \(13^{100}=(13^{20})^5\equiv1\pmod{100}\). Последние две цифры: \(01\).
Комментарий. В ответе две цифры: \(01\), а не просто \(1\).
Когда нужно доказать существование блока, явное маленькое число не обязательно.
Задача. Докажите, что существуют \(8\) последовательных составных чисел.
Возьмём \(N=9!\). Тогда \(N+2,N+3,\ldots,N+9\) делятся соответственно на \(2,3,\ldots,9\) и больше этих делителей. Поэтому все они составные.
Комментарий. Такая конструкция работает для любого числа последовательных составных чисел.
В mock-туре иногда нужно вовремя увидеть контрпример.
Задача. Верно ли, что каждое число вида \(n^2+n+41\) простое?
Нет. При \(n=41\) получаем \(41^2+41+41=41(41+1+1)=41\cdot43\), составное число.
Комментарий. Слова “каждое” и “для всех” всегда требуют проверки крайних или специальных значений.
Задачи
Докажите, что \(n^2+n\) чётно при любом целом \(n\).
Вынесите \(n\).
\(n^2+n=n(n+1)\). Из двух соседних чисел одно чётно, значит произведение чётно.
Найдите последнюю цифру \(2^{2026}\).
Цикл последних цифр степеней \(2\): \(2,4,8,6\).
Так как \(2026\equiv2\pmod4\), последняя цифра равна \(4\).
Докажите, что любые два соседних нечётных числа взаимно просты или имеют НОД \(2\)? Исправьте формулировку и докажите верное утверждение.
Два нечётных числа не могут быть соседними целыми; вероятно, речь о числах, отличающихся на \(2\).
Верная формулировка: любые два нечётных числа, отличающиеся на \(2\), взаимно просты или имеют общий делитель? Пусть числа \(n\) и \(n+2\), где \(n\) нечётно. Их общий делитель делит \(2\). Так как оба числа нечётны, общий делитель не делится на \(2\). Значит НОД равен \(1\).
Какие остатки может давать квадрат целого числа по модулю \(3\)?
Проверьте \(0,1,2\).
Если \(n\equiv0,1,2\pmod3\), то \(n^2\equiv0,1,1\pmod3\). Возможны только \(0\) и \(1\).
Найдите цифру \(x\), если число \(72x5\) делится на \(9\).
Сумма цифр должна делиться на \(9\).
Сумма цифр равна \(7+2+x+5=14+x\). Нужно \(14+x\equiv0\pmod9\). Так как \(x\) — цифра, \(x=4\).
Докажите, что \(24\mid n(n+1)(n+2)(n+3)\) для любого целого \(n\).
Докажите делимость на \(8\) и на \(3\).
Среди четырёх последовательных чисел одно делится на \(3\). Также среди них есть два чётных, причём одно из них делится на \(4\), поэтому произведение делится на \(8\). Так как \(8\) и \(3\) взаимно просты, произведение делится на \(24\).
Решите в натуральных числах \(xy+x+y=47\).
Добавьте \(1\).
Получаем \((x+1)(y+1)=48\). Пары делителей \(48\), большие \(1\), дают \((x,y)=(1,23),(2,15),(3,11),(5,7),(7,5),(11,3),(15,2),(23,1)\).
Найдите \(\gcd(n^2+n+1,n+1)\).
Замените \(n\) на \(-1\) по модулю \(n+1\).
По модулю \(n+1\) имеем \(n\equiv-1\). Тогда \(n^2+n+1\equiv1-1+1=1\). Значит общий делитель делит \(1\), и НОД равен \(1\).
Докажите, что уравнение \(x^2=3y^2\) не имеет решений в натуральных числах.
Если \(3\mid x^2\), то \(3\mid x\).
Из \(x^2=3y^2\) следует \(3\mid x^2\), значит \(3\mid x\). Пусть \(x=3t\). Тогда \(9t^2=3y^2\), откуда \(y^2=3t^2\), значит \(3\mid y\). Получили меньшее решение \((t,\frac{y}{3})\). Повторяя, получаем бесконечное деление на \(3\), невозможное для натуральных чисел.
Найдите все натуральные \(n\), для которых \(n+3\mid n^2+2\).
По модулю \(n+3\): \(n\equiv-3\).
Имеем \(n^2+2\equiv9+2=11\pmod{n+3}\). Поэтому \(n+3\mid11\). Так как \(n\ge1\), \(n+3\ge4\), значит \(n+3=11\), \(n=8\). Проверка проходит.
Найдите последние две цифры \(11^{2025}\).
Проверьте закономерность \(11^k\pmod{100}\).
Для \(k=1,\ldots,10\) получаем \(11,21,31,\ldots,91,01\), то есть цикл длины \(10\). Так как \(2025\equiv5\pmod{10}\), последние две цифры равны \(51\).
Решите систему \(n\equiv2\pmod5\), \(n\equiv3\pmod7\).
Пусть \(n=5k+2\).
Подставим: \(5k+2\equiv3\pmod7\), значит \(5k\equiv1\pmod7\). Обратный к \(5\) по модулю \(7\) равен \(3\), поэтому \(k\equiv3\pmod7\). Тогда \(n=5(7t+3)+2=35t+17\).
Найдите все \(n\pmod3\), для которых \(3\mid n^2+n+1\).
Проверьте остатки \(0,1,2\).
При \(n\equiv0\) получаем \(1\), при \(n\equiv1\) получаем \(3\equiv0\), при \(n\equiv2\) получаем \(7\equiv1\pmod3\). Значит подходит только \(n\equiv1\pmod3\).
Пусть нечётное простое \(p\) делит \(a^2+1\). Докажите, что \(p\equiv1\pmod4\).
Из \(a^2\equiv-1\pmod p\) следует \(a^4\equiv1\pmod p\).
Так как \(p\mid a^2+1\), имеем \(a^2\equiv-1\pmod p\). Тогда \(a^4\equiv1\pmod p\), но \(a^2 ot\equiv1\pmod p\). Значит порядок \(a\) по модулю \(p\) равен \(4\). Порядок делит \(p-1\), следовательно, \(4\mid p-1\), то есть \(p\equiv1\pmod4\).
Найдите все натуральные \(n\), для которых \(2n-1\mid n^2+1\).
Умножьте на \(4\).
Пусть \(d=2n-1\). Если \(d\mid n^2+1\), то \(d\mid4(n^2+1)\). Но \(4(n^2+1)=d^2+2d+5\). Поэтому \(d\mid5\). Возможны \(d=1\) и \(d=5\), откуда \(n=1\) или \(n=3\). Оба подходят.
Найдите все натуральные \(x>y\), для которых \(x^2-y^2=840\).
Положите \(x-y=2u\), \(x+y=2v\).
Так как \(x-y\) и \(x+y\) одной чётности, а произведение равно \(840\), оба множителя чётны. Пусть \(x-y=2u\), \(x+y=2v\). Тогда \(uv=210\), \(u
Докажите, что \(5\mid2^{4n}-1\) для любого натурального \(n\).
Найдите \(2^4\pmod5\).
Так как \(2^4=16\equiv1\pmod5\), то \(2^{4n}=(2^4)^n\equiv1^n\equiv1\pmod5\). Значит \(5\mid2^{4n}-1\).
Пусть \(\gcd(m,10)=1\). Докажите, что существует число, состоящее только из цифр \(0\) и \(1\), которое делится на \(m\).
Достаточно построить число из одних единиц.
По принципу Дирихле среди \(R_1,\ldots,R_m\) либо одно число делится на \(m\), либо два имеют одинаковый остаток. Во втором случае их разность равна \(10^iR_j\) для некоторого \(j\) и делится на \(m\). Так как \(10^i\) обратимо по модулю \(m\), получаем \(m\mid R_j\). Число \(R_j\) состоит только из единиц, значит также только из цифр \(0\) и \(1\).
Опишите все натуральные числа, имеющие ровно \(6\) положительных делителей.
Используйте формулу \( au(n)=(\alpha_1+1)\cdots(\alpha_s+1)\).
Если \(n=p_1^{\alpha_1}\cdots p_s^{\alpha_s}\), то число делителей равно \((\alpha_1+1)\cdots(\alpha_s+1)\). Нужно получить \(6\). Возможны разложения \(6=6\) и \(6=3\cdot2\). Поэтому \(n=p^5\) или \(n=p^2q\), где \(p,q\) — разные простые.
Докажите, что если квадрат натурального числа оканчивается цифрой \(5\), то его последние две цифры — \(25\).
Число, квадрат которого оканчивается на \(5\), само оканчивается на \(5\).
Пусть число равно \(10a+5\). Тогда \((10a+5)^2=100a^2+100a+25=100a(a+1)+25\). Значит последние две цифры квадрата равны \(25\).
Пусть \(n\) — нечётное натуральное число. Докажите, что \(n\mid1^n+2^n+\cdots+(n-1)^n\).
Сгруппируйте \(a\) и \(n-a\).
Для каждого \(a=1,\ldots,n-1\) число \(n-a\) тоже входит в сумму. Так как \(n\) нечётно, \(a^n+(n-a)^n\equiv a^n+(-a)^n=0\pmod n\). Все слагаемые разбиваются на такие пары, значит вся сумма делится на \(n\).
Найдите все простые \(p\), для которых \(p\mid2^p+1\).
Для нечётного простого используйте малую теорему Ферма.
При \(p=2\) имеем \(2^2+1=5\), не делится на \(2\). Пусть \(p\) нечётное. По малой теореме Ферма \(2^p\equiv2\pmod p\). Тогда \(2^p+1\equiv3\pmod p\). Значит нужно \(p\mid3\), откуда \(p=3\). Проверка: \(3\mid9\).
Докажите, что существует бесконечно много чисел, состоящих только из цифр \(0\) и \(1\), которые делятся на \(2027\).
Сначала постройте одно кратное из единиц, затем дописывайте нули справа.
Так как \(\gcd(2027,10)=1\), существует репьюнит \(R_s\), делящийся на \(2027\). Тогда для любого \(t\ge0\) число \(R_s\cdot10^t\) тоже делится на \(2027\) и состоит из единиц, после которых идут нули. При разных \(t\) получаем бесконечно много разных чисел.
Докажите, что для любого \(k\ge1\) существуют \(k\) последовательных натуральных чисел, каждое из которых делится на квадрат некоторого простого числа.
Выберите разные простые \(p_1,\ldots,p_k\) и задайте \(n+i\equiv0\pmod{p_i^2}\).
Выберем попарно различные простые \(p_1,\ldots,p_k\). Рассмотрим систему \(n\equiv-1\pmod{p_1^2}\), \(n\equiv-2\pmod{p_2^2}\), \(\ldots\), \(n\equiv-k\pmod{p_k^2}\). Модули \(p_i^2\) попарно взаимно просты, поэтому по CRT существует решение \(n_0\). Тогда каждое число \(n_0+i\) делится на \(p_i^2\). Прибавив к \(n_0\) достаточно большое кратное \(p_1^2\cdots p_k^2\), получаем положительные последовательные числа.
Лестницы