Теория курса

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

Book 1. Introduction to Olympiad Number Theory

1. Делимость и разложение на простые множители
2. НОД, НОК и алгоритм Евклида
3. Модульная арифметика I: остатки и противоречия
4. Модульная арифметика II: линейные сравнения и системы
5. Диофантовы уравнения I: факторизация и оценки
6. Бесконечный спуск I
7. Ферма, Эйлер и циклы степеней
8. Китайская теорема об остатках
9. Подсчет делителей
10. Цифры, системы счисления и периодичность
11. Смешанные задачи I
12. Пробные олимпиады I

Глава

Делимость и разложение на простые множители

Модуль вводит точный язык делимости, простые числа, разложение на множители, подсчет делителей и первые олимпиадные приемы: последовательные числа, параметры и факториальные конструкции.

Ключевая идея Делимость в олимпиадной теории чисел - это не быстрое деление, а способ видеть структуру целого числа. Запись \(a\mid b\) означает, что \(b=ak\) для некоторого целого \(k\). Разложение на простые множители превращает число в набор показателей степеней простых чисел. Поэтому многие задачи становятся задачами о том, какие простые множители и в каких степенях обязаны присутствовать. Основные факты Если \(d\mid a\) и \(d\mid b\), то \(d\mid xa+yb\) для любых целых \(x,y\). Если \(a\mid b\) и \(b\mid c\), то \(a\mid c\). Каждое число \(n>1\) единственным образом раскладывается в произведение простых степеней. Если \(n=p_1^{\alpha_1}\cdots p_s^{\alpha_s}\), то число положительных делителей равно \((\alpha_1+1)\cdots(\alpha_s+1)\). Если простое \(p\mid ab\), то \(p\mid a\) или \(p\mid b\). Среди \(k\) последовательных целых чисел всегда есть число, делящееся на \(k\), но для делимости на \(k!\) нужно аккуратно собрать простые степени. Когда применять метод В условии есть слова "делится", "делитель", "простое число", "разложение", "количество делителей". Нужно доказать делимость выражения для всех целых \(n\). Нужно найти все параметры, при которых одно выражение делит другое. Нужно построить число с заданными делителями или заданным количеством делителей. Нужно опровергнуть неверное утверждение о делимости одним контрпримером. Как распознать метод Если делитель содержит переменную, попробуйте заменить переменную по модулю этого делителя. Например, при условии \(n+3\mid f(n)\) удобно писать \(n\equiv -3\pmod{n+3}\). Если выражение похоже на произведение соседних чисел, разложите его на последовательные множители. Если задача о количестве делителей, сразу переходите к простым показателям. Типичные ошибки Из \(ab\mid c\) или \(d\mid ab\) делают неверный вывод о делимости отдельных множителей. Называют \(1\) простым числом, из-за чего ломается единственность разложения. Доказывают делимость на \(2\), \(3\), \(5\), но забывают проверить, что эти числа попарно взаимно просты. При подсчете делителей забывают вариант нулевого показателя простого множителя. В задачах "для всех \(n\)" проверяют несколько примеров вместо доказательства. Мини-чеклист Можно ли записать делимость как \(b=ak\)? Можно ли взять остаток выражения по переменному делителю? Нужно ли разложить выражение на множители? Какие простые степени должны делить число? Если ищется наибольший универсальный делитель, какой маленький \(n\) дает верхнюю границу?

Пример 1. Делимость как точное равенство Первый навык - переводить символ \(a\mid b\) в равенство с целым множителем. Задача. Пусть \(12\mid n\). Докажите, что \(3\mid n\) и \(4\mid n\). Решение. Из \(12\mid n\) следует \(n=12k\) для некоторого целого \(k\). Тогда \(n=3(4k)\), значит, \(3\mid n\). Также \(n=4(3k)\), значит, \(4\mid n\). Комментарий. Не нужно делить приблизительно; вся работа идет с целым множителем. Пример 2. Линейная комбинация Одно из главных свойств делимости: из двух делимых выражений можно строить новые. Задача. Если \(7\mid a\) и \(7\mid b\), докажите, что \(7\mid 5a-3b\). Решение. Запишем \(a=7x\), \(b=7y\). Тогда \(5a-3b=35x-21y=7(5x-3y)\). Так как \(5x-3y\) - целое число, получаем \(7\mid 5a-3b\). Комментарий. Эта идея позже станет языком НОД и алгоритма Евклида. Пример 3. Разложение и делители Количество делителей считается не списком делителей, а выбором показателей простых. Задача. Найдите число положительных делителей числа \(1260\). Решение. Разложим: \(1260=126\cdot 10=2^2\cdot 3^2\cdot 5\cdot 7\). Делитель имеет вид \(2^a3^b5^c7^d\), где \(a=0,1,2\), \(b=0,1,2\), \(c=0,1\), \(d=0,1\). Поэтому число делителей равно \(3\cdot 3\cdot 2\cdot 2=36\). Комментарий. Нулевой показатель означает, что данный простой множитель не входит в делитель. Пример 4. Три последовательных числа Произведение соседних чисел почти всегда содержит нужные простые множители. Задача. Докажите, что \(6\mid n(n+1)(n+2)\) для любого целого \(n\). Решение. Среди трех последовательных чисел одно делится на \(3\). Среди любых двух соседних чисел одно четно, значит, среди трех тоже есть четное число. Поэтому произведение делится и на \(2\), и на \(3\). Так как \(2\) и \(3\) взаимно просты, произведение делится на \(6\). Комментарий. Важно явно объединять делимость на взаимно простые множители. Пример 5. Неверное утверждение В олимпиадных задачах полезно быстро видеть, где свойство делимости нельзя применять. Задача. Верно ли, что из \(6\mid ab\) следует \(6\mid a\) или \(6\mid b\)? Решение. Нет. Возьмем \(a=2\), \(b=3\). Тогда \(ab=6\), значит, \(6\mid ab\). Но \(6\nmid 2\) и \(6\nmid 3\). Утверждение неверно. Комментарий. Похожее утверждение верно для простого делителя \(p\), но не для составного \(6\). Пример 6. Переменный делитель Когда делитель содержит \(n\), часто надо заменить \(n\) на удобный остаток. Задача. Найдите все целые \(n\), для которых \(n+3\mid n^2+n+1\). Решение. По модулю \(n+3\) имеем \(n\equiv -3\). Поэтому \(n^2+n+1\equiv 9-3+1=7\pmod{n+3}\). Значит, \(n+3\mid 7\). Отсюда \(n+3\in\{\pm1,\pm7\}\), и \(n\in\{-2,-4,4,-10\}\). Все эти значения подходят. Комментарий. Это типичный прием: остаток выражения превращается в маленькую константу. Пример 7. Наибольший универсальный делитель Для утверждения «делится при всех \(n\)» нужна и нижняя, и верхняя оценка. Задача. Найдите наибольшее \(m\), такое что \(m\mid n(n+1)(n+2)\) для любого целого \(n\). Решение. Из предыдущего примера известно, что \(6\) всегда делит произведение трех последовательных чисел. Значит, \(m\ge 6\) возможно.С другой стороны, при \(n=1\) произведение равно \(1\cdot2\cdot3=6\). Поэтому любой универсальный делитель \(m\) должен делить \(6\). Следовательно, наибольшее \(m\) равно \(6\). Комментарий. Малое значение \(n\) часто дает верхнюю границу на ответ. Пример 8. Длинная цепочка составных чисел Факториал позволяет заранее встроить много делителей. Задача. Докажите, что существует \(10\) последовательных составных натуральных чисел. Решение. Рассмотрим числа \(11!+2,11!+3,\ldots,11!+11\). Число \(11!+k\) делится на \(k\), потому что \(11!\) делится на \(k\) при \(2\le k\le 11\). Кроме того, \(11!+k>k\). Значит, каждое из этих чисел имеет нетривиальный делитель \(k\) и является составным. Мы получили \(10\) последовательных составных чисел. Комментарий. Та же конструкция дает цепочку любой заданной длины.

Глава

НОД, НОК и алгоритм Евклида

Модуль усиливает вычислительный НОД до олимпиадного инструмента: алгоритм Евклида, линейные комбинации, НОД выражений, связь НОД и НОК, взаимная простота и числа вида \(a^m-1\).

Ключевая идея НОД измеряет общую часть двух чисел, а НОК - минимальное число, содержащее обе структуры как делители. Олимпиадный смысл НОД не в вычислении, а в том, что общий делитель можно переносить между выражениями. Алгоритм Евклида основан на равенстве \(\gcd(a,b)=\gcd(b,a-b)\) и, сильнее, \(\gcd(a,b)=\gcd(b,r)\), где \(r\) - остаток от деления \(a\) на \(b\). Основные факты \(\gcd(a,b)\operatorname{lcm}(a,b)=ab\) для положительных \(a,b\). Если \(d=\gcd(a,b)\), то \(a=dx\), \(b=dy\), где \(\gcd(x,y)=1\). \(\gcd(a,b)=\gcd(a,b-a)=\gcd(b,a\bmod b)\). Если \(\gcd(a,b)=1\) и \(a\mid bc\), то \(a\mid c\). Общий делитель выражений делит любую их целочисленную линейную комбинацию. Для \(a>1\): \(\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1\). Когда применять метод Нужно найти общий делитель двух выражений с параметром. В задаче есть одновременно НОД и НОК. Нужно сократить большую пару чисел без разложения на простые множители. Встречаются числа вида \(a^m-1\) и \(a^n-1\). Нужно доказать взаимную простоту двух выражений. Как распознать метод Если два выражения зависят от \(n\), попробуйте вычесть одно из другого или составить линейную комбинацию, чтобы уменьшить степень. Часто НОД делит маленькую константу. Если даны НОД и НОК двух чисел, почти всегда стоит записать \(a=dx\), \(b=dy\), \(\gcd(x,y)=1\). Тогда НОК равен \(dxy\). Типичные ошибки Механически считают НОД больших чисел разложением, хотя Евклид короче. Используют формулу \(ab=\gcd(a,b)\operatorname{lcm}(a,b)\) для трех чисел, где она неверна. После записи \(a=dx\), \(b=dy\) забывают условие \(\gcd(x,y)=1\). Сокращают сравнение или делимость на число, не проверив взаимную простоту. В задачах с \(a^m-1\) пытаются раскрывать степени вместо Евклида по показателям. Мини-чеклист Можно ли заменить пару \((a,b)\) на \((b,a-b)\) или \((b,r)\)? Можно ли составить маленькую линейную комбинацию выражений? Если известны НОД и НОК, записаны ли \(a=dx\), \(b=dy\)? Проверена ли взаимная простота оставшихся частей? Для степеней \(a^m-1\) можно ли применить алгоритм Евклида к показателям?

Пример 1. Алгоритм Евклида Учимся уменьшать пару чисел без полного разложения. Задача. Найдите \(\gcd(252,198)\). Решение. \(\gcd(252,198)=\gcd(198,54)=\gcd(54,36)=\gcd(36,18)=18\). Ответ: \(18\). Комментарий. На каждом шаге заменяем большее число остатком от деления на меньшее. Пример 2. НОД и НОК через простые степени Минимальные и максимальные показатели дают НОД и НОК. Задача. Найдите \(\gcd(84,126)\) и \(\operatorname{lcm}(84,126)\). Решение. \(84=2^2\cdot3\cdot7\), \(126=2\cdot3^2\cdot7\). Поэтому \(\gcd(84,126)=2\cdot3\cdot7=42\), а \(\operatorname{lcm}(84,126)=2^2\cdot3^2\cdot7=252\). Комментарий. НОД берет меньшие показатели, НОК - большие. Пример 3. Когда известны НОД и НОК Связь \(ab=\gcd(a,b)\operatorname{lcm}(a,b)\) часто сразу находит неизвестное число. Задача. Найдите \(n\), если \(\gcd(n,70)=14\) и \(\operatorname{lcm}(n,70)=420\). Решение. Для двух положительных чисел \(n\cdot70=\gcd(n,70)\operatorname{lcm}(n,70)\). Значит, \(70n=14\cdot420\), откуда \(n=84\). Проверка: \(\gcd(84,70)=14\), \(\operatorname{lcm}(84,70)=420\). Комментарий. Формула требует именно двух чисел. Пример 4. НОД выражений с параметром Общий делитель часто делит маленькую константу. Задача. Докажите, что \(\gcd(n^2+1,n+3)\) делит \(10\). Решение. Пусть \(d=\gcd(n^2+1,n+3)\). Тогда \(n\equiv -3\pmod d\), поэтому \(n^2+1\equiv 9+1=10\pmod d\). Так как \(d\mid n^2+1\), получаем \(d\mid10\). Комментарий. Это основной прием для задач вида \(\gcd(f(n),g(n))\). Пример 5. Взаимная простота соседних чисел Простейший пример НОД, равного единице. Задача. Докажите, что \(\gcd(n,n+1)=1\). Решение. Любой общий делитель чисел \(n\) и \(n+1\) делит их разность \((n+1)-n=1\). Значит, общий делитель может быть только \(1\). Комментарий. Разность соседних чисел - самый короткий путь. Пример 6. Деление при взаимной простоте Это один из самых часто используемых фактов в теории чисел. Задача. Пусть \(\gcd(a,b)=1\) и \(a\mid bc\). Докажите, что \(a\mid c\). Решение. Все простые множители числа \(a\) не входят в \(b\), потому что \(\gcd(a,b)=1\). Но произведение \(bc\) делится на \(a\), значит, все простые множители \(a\) с нужными степенями должны входить в \(c\). Следовательно, \(a\mid c\). Комментарий. Позже это станет аккуратным инструментом в сравнениях. Пример 7. Степени минус один Алгоритм Евклида можно применять к показателям. Задача. Найдите \(\gcd(2^{18}-1,2^{30}-1)\). Решение. Используем формулу \(\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1\). Так как \(\gcd(18,30)=6\), получаем \(2^6-1=63\). Комментарий. Формулу можно доказать тем же Евклидом: \(a^m-1\) делится на \(a^d-1\), когда \(d\mid m\). Пример 8. НОД повторяющихся блоков Иногда НОД целого семейства чисел виден из общего множителя. Задача. Найдите НОД всех шестизначных чисел вида \(\overline{abcabc}\). Решение. Такое число равно \(1000\cdot\overline{abc}+\overline{abc}=1001\cdot\overline{abc}\). Значит, все такие числа делятся на \(1001\). С другой стороны, среди трехзначных блоков есть взаимно простые, например \(100\) и \(101\), поэтому общего множителя сверх \(1001\) быть не обязано. НОД всего семейства равен \(1001\). Комментарий. Это уже не вычисление одной пары, а НОД семейства.

Глава

Модульная арифметика

Остатки, сравнения, действия по модулю, циклы степеней и противоречия по модулю.

1. Остатки Когда целое число \(a\) делится на положительное целое число \(m\), его можно записать в виде \[ a=mq+r,\qquad 0\le r Число \(r\) называется остатком. Модульная арифметика позволяет работать с остатками вместо больших чисел. 2. Сравнение по модулю Запись \[ a\equiv b\pmod m \] означает, что \(a\) и \(b\) дают одинаковый остаток при делении на \(m\). Равносильно: \[ m\mid a-b. \] Например, \(17\equiv2\pmod5\), потому что \(17-2=15\) делится на \(5\). 3. Действия со сравнениями Если \[ a\equiv b\pmod m,\qquad c\equiv d\pmod m, \] то \[ a+c\equiv b+d\pmod m, \] \[ ac\equiv bd\pmod m. \] То есть остатки можно складывать, вычитать и умножать. 4. Степени и циклы Степени часто повторяются по модулю. Например, по модулю \(10\): \[ 2^1\equiv2,\quad 2^2\equiv4,\quad 2^3\equiv8,\quad 2^4\equiv6,\quad 2^5\equiv2. \] Последние цифры степеней двойки повторяются циклом длины \(4\): \(2,4,8,6\). 5. Противоречие по модулю Чтобы доказать, что уравнение не имеет целых решений, можно рассмотреть обе части по небольшому модулю. Если возможные остатки не совпадают, уравнение невозможно. Например, квадрат целого числа не может давать остаток \(2\) при делении на \(4\), потому что квадраты дают только \(0\) или \(1\pmod4\). 6. Признаки делимости как модульная арифметика Правила с цифрами объясняются через модули. Так как \[ 10\equiv1\pmod9, \] каждая степень \(10\) тоже сравнима с \(1\pmod9\). Поэтому число имеет тот же остаток по модулю \(9\), что и сумма его цифр.

Пример 1. Остаток числа Этот пример связывает обычное деление с остатками: число нужно записать в виде \(mq+r\), где \(0\le r Задача. Найдите остаток от деления \(137\) на \(5\). Решение. Так как \(137=5\cdot27+2\), остаток равен \(2\). Пример 2. Записать сравнение Этот пример показывает, что сравнение по модулю записывает остаток после деления. Задача. Заполните пропуск: \(83\equiv \square \pmod 7\), где в пропуске одно из чисел \(0,1,2,3,4,5,6\). Решение. \(83=7\cdot11+6\), значит \(83\equiv6\pmod7\). Пример 3. Сложение остатков Этот пример учит складывать остатки, а затем упрощать результат по модулю. Задача. Если \(a\equiv4\pmod9\) и \(b\equiv7\pmod9\), найдите \(a+b\pmod9\). Решение. \(a+b\equiv4+7=11\equiv2\pmod9\). Пример 4. Последняя цифра степени Этот пример показывает, что последние цифры степеней повторяются циклами. Задача. Найдите последнюю цифру числа \(2^{25}\). Решение. Длина цикла равна \(4\). Так как \(25\equiv1\pmod4\), число \(2^{25}\) имеет ту же последнюю цифру, что и \(2^1\), то есть \(2\). Пример 5. Степень по модулю семь Этот пример учит использовать цикл степеней по модулю \(7\), чтобы не вычислять большую степень. Задача. Найдите остаток от деления \(3^{20}\) на \(7\). Решение. По модулю \(7\): \(3^1\equiv3\), \(3^2\equiv2\), \(3^3\equiv6\), \(3^4\equiv4\), \(3^5\equiv5\), \(3^6\equiv1\). Так как \(20\equiv2\pmod6\), получаем \(3^{20}\equiv3^2\equiv2\pmod7\). Пример 6. Квадраты по модулю четыре Этот пример показывает важный факт: квадрат целого числа имеет не все остатки по модулю \(4\). Задача. Докажите, что квадрат любого целого числа сравним с \(0\) или \(1\pmod4\). Решение. Если \(n=2k\), то \(n^2=4k^2\equiv0\pmod4\). Если \(n=2k+1\), то \(n^2=4k^2+4k+1\equiv1\pmod4\). Пример 7. Квадрат такого вида невозможен Этот пример учит доказывать невозможность решений через противоречие по модулю. Задача. Докажите, что уравнение \(x^2=4y+2\) не имеет целых решений. Решение. Правая часть удовлетворяет \(4y+2\equiv2\pmod4\). Но квадрат дает только \(0\) или \(1\pmod4\). Получаем противоречие. Пример 8. Всегда делится на пять Этот пример показывает, как проверка всех остатков по модулю \(5\) дает доказательство для любого целого \(n\). Задача. Докажите, что \(5\mid n^5-n\) для любого целого \(n\). Решение. Достаточно проверить \(n\equiv0,1,2,3,4\pmod5\). Получаем \(0^5-0=0\), \(1^5-1=0\), \(2^5-2=30\), \(3^5-3=240\), \(4^5-4=1020\), и все эти числа делятся на \(5\). Поэтому \(5\mid n^5-n\).

Глава

Модульная арифметика I: остатки и противоречия

Модуль учит использовать остатки как инструмент доказательства невозможности: таблицы квадратов и кубов, выбор модуля, последние цифры и первые модульные противоречия.

Ключевая идея Сравнения позволяют заменить бесконечно много целых чисел конечной таблицей остатков. Чтобы доказать невозможность, часто достаточно найти модуль, в котором левая и правая части всегда попадают в разные наборы остатков. В этом модуле главное - не вычислять механически, а выбирать модуль: \(3,4,5,7,8,9,11,16\) часто дают быстрые противоречия. Основные факты \(a\equiv b\pmod m\) означает, что \(m\mid a-b\). Если \(a\equiv b\pmod m\), то можно складывать, вычитать и умножать сравнения. Квадраты по модулю \(4\) дают только \(0,1\); по модулю \(8\) - только \(0,1,4\). Кубы по модулю \(9\) дают только \(0,1,8\), то есть \(0,\pm1\). Последняя цифра - это остаток по модулю \(10\), последние две цифры - остаток по модулю \(100\). Противоречие по одному модулю доказывает отсутствие целочисленных решений. Когда применять метод Нужно доказать, что у уравнения нет целочисленных решений. В выражении есть квадраты, кубы, четвертые степени или последние цифры. Нужно найти все \(n\), для которых выражение делится на небольшое число. В задаче важна четность, но одной четности недостаточно. Большие степени имеют повторяющиеся остатки. Как распознать метод Если справа стоит число вида \(4k+3\), \(8k+7\), \(3k+2\), попробуйте таблицы квадратов. Если есть кубы, проверьте модуль \(7\) или \(9\). Если речь о последней цифре, ищите цикл степеней. Правильный модуль обычно маленький и делает одну сторону очень ограниченной: например, квадрат по модулю \(8\) не может дать \(2,3,5,6,7\). Типичные ошибки Делят сравнение на число без проверки, можно ли это делать. Проверяют остатки только положительных чисел и забывают, что отрицательные дают те же классы. Доказывают, что конкретный модуль не дал противоречия, и ошибочно решают, что решения существуют. Путают «квадрат может иметь остаток \(1\)» и «число с остатком \(1\) обязательно квадрат». В задачах на последние две цифры используют только модуль \(10\). Мини-чеклист Какие остатки дают квадраты или кубы по выбранному модулю? Какие остатки может иметь левая часть? Какие остатки имеет правая часть? Есть ли пересечение между этими наборами? Если решений нет по модулю \(m\), записано ли противоречие явно?

Пример 1. Остатки и сравнения Сравнение фиксирует остаток, но позволяет работать с числами без деления нацело. Задача. Найдите остаток \(2026^2+2026\) при делении на \(5\). Решение. \(2026\equiv1\pmod5\). Тогда \(2026^2+2026\equiv1^2+1=2\pmod5\). Остаток равен \(2\). Комментарий. Сначала заменяем число его остатком, затем считаем. Пример 2. Таблица квадратов по модулю 8 Квадраты имеют очень мало остатков. Задача. Покажите, что квадрат целого числа по модулю \(8\) может иметь только остаток \(0,1,4\). Решение. Проверим остатки \(0,1,2,\ldots,7\). Их квадраты по модулю \(8\): \(0,1,4,1,0,1,4,1\). Значит, возможны только \(0,1,4\). Комментарий. Эта таблица будет использоваться много раз. Пример 3. Невозможность \(4z+3\) Сумма двух квадратов не может иметь остаток \(3\) по модулю \(4\). Задача. Докажите, что \(x^2+y^2=4z+3\) не имеет целочисленных решений. Решение. Квадрат по модулю \(4\) равен \(0\) или \(1\). Поэтому сумма двух квадратов по модулю \(4\) может быть \(0,1,2\), но не \(3\). Правая часть \(4z+3\equiv3\pmod4\). Противоречие. Комментарий. Модуль \(4\) выбран из вида правой части. Пример 4. Невозможность \(8z+7\) Модуль \(8\) сильнее обычной четности. Задача. Докажите, что \(x^2+y^2=8z+7\) не имеет целочисленных решений. Решение. Квадраты по модулю \(8\) дают \(0,1,4\). Сумма двух таких остатков может быть \(0,1,2,4,5\), но не \(7\). Правая часть равна \(7\) по модулю \(8\). Противоречие. Комментарий. Здесь модуль \(4\) был бы слабее, а модуль \(8\) решает задачу. Пример 5. Делимость \(n^2+n+1\) на 7 Иногда проще проверить все остатки по небольшому модулю. Задача. Найдите все остатки \(n\pmod7\), при которых \(7\mid n^2+n+1\). Решение. Проверяем \(n=0,1,2,3,4,5,6\). Значения \(n^2+n+1\) по модулю \(7\): \(1,3,0,6,0,3,1\). Поэтому подходят \(n\equiv2\) и \(n\equiv4\pmod7\). Комментарий. Таблица из семи строк вполне допустима, если она дает полный ответ. Пример 6. Кубы по модулю 9 Кубы по модулю \(9\) дают только три остатка. Задача. Покажите, что куб целого числа по модулю \(9\) равен \(0,1\) или \(8\). Решение. Проверим остатки \(0,\ldots,8\): кубы дают \(0,1,8,0,1,8,0,1,8\). Значит, возможны только \(0,1,8\), то есть \(0,\pm1\). Комментарий. Эта таблица полезна для задач о суммах кубов. Пример 7. Последняя цифра степени Последняя цифра - это работа по модулю \(10\). Задача. Найдите последнюю цифру \(7^{2026}\). Решение. Последние цифры степеней \(7\) идут циклом: \(7,9,3,1\). Длина цикла \(4\). Так как \(2026\equiv2\pmod4\), берем вторую цифру цикла: \(9\). Комментарий. Не надо вычислять большую степень. Пример 8. Правильный модуль Иногда модуль виден по коэффициенту перед переменной. Задача. Докажите, что уравнение \(x^2=3y^2+2\) не имеет целочисленных решений. Решение. Рассмотрим уравнение по модулю \(3\). Правая часть \(3y^2+2\equiv2\pmod3\). Но квадрат по модулю \(3\) может быть только \(0\) или \(1\). Противоречие. Комментарий. Модуль \(3\) выбран потому, что правая часть почти кратна \(3\).

Глава

Сравнения и остатки

Классы остатков, линейные сравнения, совместимые остатки и олимпиадные рассуждения по модулю.

1. Классы остатков По модулю \(m\) каждое целое число попадает ровно в один из классов \[ 0,1,2,\ldots,m-1. \] Например, по модулю \(5\) число \(23\) находится в классе \(3\), потому что \[ 23\equiv3\pmod5. \] 2. Сравнение как инструмент Запись \[ a\equiv b\pmod m \] означает, что \(a-b\) делится на \(m\). Это превращает задачи с большими числами в задачи о маленьких остатках. 3. Решение линейных сравнений Сравнение вида \[ ax\equiv b\pmod m \] называется линейным сравнением. Если \(\gcd(a,m)=1\), то у \(a\) есть обратный элемент по модулю \(m\), и сравнение имеет ровно одно решение по модулю \(m\). Пример: \[ 3x\equiv5\pmod7. \] Так как \(3\cdot5\equiv1\pmod7\), умножаем обе части на \(5\): \[ x\equiv25\equiv4\pmod7. \] 4. Почему делить опасно В обычных уравнениях мы часто делим обе части. В сравнениях деление разрешено только тогда, когда делитель обратим по модулю. Например, \[ 2x\equiv2\pmod6 \] нельзя просто разделить на \(2\) и получить только \(x\equiv1\pmod6\). На самом деле решения: \[ x\equiv1,4\pmod6. \] 5. Совместимые остатки Иногда число должно удовлетворять нескольким условиям: \[ n\equiv a\pmod m,\qquad n\equiv b\pmod k. \] Когда модули маленькие, можно выписать один класс остатков и проверить второе условие. Это подготовка к китайской теореме об остатках. 6. Остатки в олимпиадных задачах Остатки помогают доказывать невозможность, находить вид числа или сокращать много случаев до нескольких. Полезные вопросы: Какой модуль делает выражение проще? Какие остатки возможны? Может ли общий делитель, квадрат или степень дать противоречие?

Пример 1. Класс остатка Этот пример показывает, как стандартный остаток задаёт класс остатка числа по выбранному модулю. Задача. Найдите класс остатка числа \(94\) по модулю \(9\). Решение. Так как \(94=9\cdot10+4\), получаем \(94\equiv4\pmod9\). Пример 2. Отрицательный остаток Этот пример напоминает, что отрицательные числа тоже нужно приводить к стандартным остаткам от 0 до m-1. Задача. Запишите \(-17\) как стандартный остаток по модулю \(6\). Решение. \(-17+18=1\), значит \(-17\equiv1\pmod6\). Пример 3. Равносильные сравнения Этот пример связывает запись сравнения с условием делимости, которое стоит за этой записью. Задача. Объясните, почему \(a\equiv b\pmod m\) равносильно \(m\mid a-b\). Решение. Если \(a=mq+r\) и \(b=mk+r\), то \(a-b=m(q-k)\), значит \(m\mid a-b\). Обратно, если \(m\mid a-b\), то числа отличаются на кратное \(m\), поэтому имеют одинаковый остаток по модулю \(m\). Пример 4. Решить простое сравнение Этот пример показывает, как решить линейное сравнение с помощью обратного элемента по модулю. Задача. Решите \(4x\equiv3\pmod7\). Решение. Так как \(4\cdot2=8\equiv1\pmod7\), умножаем обе части на \(2\). Получаем \(x\equiv6\pmod7\). Пример 5. Два решения Этот пример показывает, как решить линейное сравнение с помощью обратного элемента по модулю. Задача. Решите \(2x\equiv4\pmod6\). Решение. Проверяя остатки по модулю \(6\), видим, что подходят \(x=2\) и \(x=5\). Значит, \(x\equiv2,5\pmod6\). Иначе: после деления на \(2\) получаем \(x\equiv2\pmod3\), что дает остатки \(2\) и \(5\) по модулю \(6\). Пример 6. Совместимые остатки I Этот пример учит выписывать один класс остатков и проверять второе условие. Задача. Найдите наименьшее положительное целое \(n\), такое что \(n\equiv2\pmod3\) и \(n\equiv1\pmod5\). Решение. Числа \(1\pmod5\): \(1,6,11,16,\ldots\). Проверяя по модулю \(3\), получаем \(1,0,2,1,\ldots\). Первое подходящее число - \(11\). Пример 7. Остаток многочлена Этот пример показывает, что выражение по модулю удобно считать после приведения переменной к остатку. Задача. Если \(n\equiv5\pmod8\), найдите \(n^2+3n+1\pmod8\). Решение. \(n^2+3n+1\equiv5^2+3\cdot5+1=25+15+1=41\equiv1\pmod8\). Пример 8. Сравнимые квадраты Этот пример показывает, как доказывать свойство сравнений умножением сравнимых величин. Задача. Докажите: если \(a\equiv b\pmod m\), то \(a^2\equiv b^2\pmod m\). Решение. Так как \(a\equiv b\pmod m\), можно перемножить сравнения: \(a\cdot a\equiv b\cdot b\pmod m\). Значит, \(a^2\equiv b^2\pmod m\).

Глава

Модульная арифметика II: линейные сравнения и системы

Модуль учит решать линейные сравнения, работать с обратными элементами, понимать когда можно делить, проверять совместимость систем и строить числа с заданными остатками.

Ключевая идея Линейное сравнение \(ax\equiv b\pmod m\) похоже на линейное уравнение, но делить в нем можно не всегда. Главный вопрос: совместим ли коэффициент \(a\) с модулем \(m\)? Если \(\gcd(a,m)=1\), у \(a\) есть обратный элемент по модулю \(m\). Если \(\gcd(a,m)>1\), сравнение может не иметь решений или иметь несколько классов решений. Основные факты Сравнение \(ax\equiv b\pmod m\) имеет решения тогда и только тогда, когда \(\gcd(a,m)\mid b\). Если \(d=\gcd(a,m)\mid b\), то можно разделить \(a,b,m\) на \(d\) и решить \(\frac adx\equiv\frac bd\pmod{\frac md}\). Если \(\gcd(a,m)=1\), то \(a\) имеет обратный элемент по модулю \(m\). Система \(x\equiv r\pmod m\), \(x\equiv s\pmod n\) совместна тогда и только тогда, когда \(r\equiv s\pmod{\gcd(m,n)}\). Если модули взаимно просты, решение системы единственно по модулю произведения модулей. Когда применять метод В задаче требуется найти число по нескольким остаткам. Дано выражение вида \(ax+b\), делящееся на \(m\). Нужно понять, можно ли разделить сравнение на общий множитель. Остаточные условия имеют не взаимно простые модули. Делимость \(f(n)\mid g(n)\) сводится к условию, что переменный делитель делит константу. Как распознать метод Если условие звучит как "число дает такие-то остатки", сразу записывайте систему сравнений. Если встречается \(ax\equiv b\pmod m\), сначала вычислите \(\gcd(a,m)\), а не пытайтесь делить на \(a\). Для систем с не взаимно простыми модулями сначала проверьте совместимость по общему делителю модулей. Типичные ошибки Делят \(6x\equiv12\pmod{18}\) на \(6\) и оставляют модуль \(18\), теряя решения. Забывают, что одно сравнение может иметь несколько решений по исходному модулю. Применяют китайскую теорему об остатках к не взаимно простым модулям без проверки совместимости. Находят одно решение системы, но не указывают модуль всех решений. В задачах на делимость выражений не проверяют найденные кандидаты. Мини-чеклист Каков \(\gcd(a,m)\) в сравнении \(ax\equiv b\pmod m\)? Делит ли этот НОД правую часть? После сокращения изменился ли модуль? Совместны ли остатки по общим делителям модулей? В каком модуле нужно записать окончательный ответ?

Пример 1. Обратный элемент Если коэффициент взаимно прост с модулем, его можно обратить. Задача. Решите \(3x\equiv5\pmod7\). Решение. Обратный к \(3\) по модулю \(7\) равен \(5\), потому что \(3\cdot5\equiv1\). Умножаем: \(x\equiv5\cdot5=25\equiv4\pmod7\). Комментарий. Это корректная замена деления. Пример 2. Нет решений Перед делением смотрим на НОД. Задача. Решите \(6x\equiv5\pmod9\). Решение. \(\gcd(6,9)=3\), но \(3\nmid5\). Значит, сравнение не имеет решений. Комментарий. Одна проверка НОД сразу закрывает задачу. Пример 3. Несколько решений Если общий делитель делит правую часть, решений будет несколько. Задача. Решите \(6x\equiv12\pmod{18}\). Решение. Делим \(6,12,18\) на \(6\): \(x\equiv2\pmod3\). По модулю \(18\) это дает \(x\equiv2,5,8,11,14,17\pmod{18}\). Комментарий. Модуль изменился: это главное место ошибки. Пример 4. Простая система Для взаимно простых модулей решение единственно по модулю произведения. Задача. Решите систему \(x\equiv2\pmod3\), \(x\equiv3\pmod5\). Решение. Числа \(2,5,8,11,\ldots\) имеют остаток \(2\) по модулю \(3\). Среди них \(8\equiv3\pmod5\). Значит, \(x\equiv8\pmod{15}\). Комментарий. Можно решать перебором одного класса. Пример 5. Несовместимые условия Не взаимно простые модули требуют проверки по общему делителю. Задача. Докажите, что система \(x\equiv2\pmod6\), \(x\equiv3\pmod9\) не имеет решений. Решение. Если \(x\equiv2\pmod6\), то \(x\equiv2\pmod3\). Если \(x\equiv3\pmod9\), то \(x\equiv0\pmod3\). Одно число не может иметь два разных остатка по модулю \(3\). Решений нет. Комментарий. Это совместимость по \(\gcd(6,9)=3\). Пример 6. Совместимые не взаимно простые модули Если остатки согласованы по общему делителю, систему можно решать. Задача. Решите \(x\equiv4\pmod6\), \(x\equiv10\pmod{15}\). Решение. Оба остатка дают \(1\) по модулю \(3\), значит, совместимость есть. Пусть \(x=6k+4\). Тогда \(6k+4\equiv10\pmod{15}\), то есть \(6k\equiv6\pmod{15}\). Делим на \(3\): \(2k\equiv2\pmod5\), откуда \(k\equiv1\pmod5\). Значит, \(x\equiv10\pmod{30}\). Комментарий. Ответ записан по модулю \(\operatorname{lcm}(6,15)=30\). Пример 7. Система из условия Иногда задача уже содержит скрытое противоречие. Задача. Найдите все \(x\pmod{84}\), для которых \(x\equiv2\pmod3\), \(x\equiv3\pmod7\), \(x\equiv4\pmod{12}\). Решение. Из \(x\equiv4\pmod{12}\) следует \(x\equiv1\pmod3\). Но первое условие требует \(x\equiv2\pmod3\). Противоречие, решений нет. Комментарий. Сначала проверяем совместимость, потом считаем. Пример 8. Делимость сводится к константе Переменный делитель можно заставить делить маленькое число. Задача. Найдите все положительные \(n\), для которых \(2n+1\mid n^2+n+7\). Решение. Если \(2n+1\mid n^2+n+7\), то он делит \(4(n^2+n+7)=(2n+1)^2+27\). Значит, \(2n+1\mid27\). Так как \(n>0\), \(2n+1\in\{3,9,27\}\). Получаем \(n=1,4,13\), и все три значения подходят. Комментарий. Это не прямое сравнение, но оно приводит к линейному ограничению.

Глава

Диофантовы уравнения

Целые решения, линейные диофантовы уравнения, факторизация, препятствия по модулю и ограничения на положительность.

1. Что такое диофантово уравнение? Диофантово уравнение - это уравнение, в котором решения ищутся в целых числах, иногда в положительных целых числах. Например, \[ 3x+5y=17 \] в теории чисел означает: найти целые пары \((x,y)\). 2. Линейные диофантовы уравнения Уравнение \[ ax+by=c \] имеет целые решения тогда и только тогда, когда \[ \gcd(a,b)\mid c. \] Это условие необходимо, потому что любой общий делитель \(a\) и \(b\) делит \(ax+by\). Оно также достаточно: алгоритм Евклида позволяет представить \(\gcd(a,b)\) как линейную комбинацию \(a\) и \(b\). 3. Общее решение Если \((x_0,y_0)\) - одно решение уравнения \(ax+by=c\), а \(g=\gcd(a,b)\), то все целые решения имеют вид \[ x=x_0+\frac{b}{g}t,\qquad y=y_0-\frac{a}{g}t, \] где \(t\) - целое число. 4. Метод факторизации Многие диофантовы уравнения становятся проще после разложения: \[ xy+x+y=11 \] можно переписать как \[ (x+1)(y+1)=12. \] После этого решения дают целые делители числа \(12\). 5. Препятствия по модулю Иногда уравнение не имеет целых решений из-за остатков. Например, если квадрат не может давать нужный остаток по модулю \(3\) или \(4\), уравнение невозможно. 6. Неотрицательные и положительные решения В олимпиадных задачах часто ищут положительные или неотрицательные решения. После получения параметрического вида ограничения на знак ограничивают параметр.

Пример 1. Проверка целых решений Это первое препятствие: НОД должен делить свободный член. Задача. Определите, имеет ли уравнение \(6x+10y=15\) целые решения. Решение. \(\gcd(6,10)=2\). Левая часть всегда четна, а \(15\) нечетно. Поэтому целых решений нет. Пример 2. Одно решение Безу Свяжите это напрямую с алгоритмом Евклида из модуля 2. Задача. Найдите одно целое решение уравнения \(3x+5y=1\). Решение. Так как \(2\cdot3-1\cdot5=1\), одно решение: \((x,y)=(2,-1)\). Пример 3. Все линейные решения Подчеркните, что параметр двигает точку по прямой, не меняя значение. Задача. Найдите все целые решения уравнения \(3x+5y=17\). Решение. Одно решение: \((4,1)\), потому что \(3\cdot4+5\cdot1=17\). Так как \(\gcd(3,5)=1\), все решения имеют вид \(x=4+5t\), \(y=1-3t\), где \(t\in\mathbb Z\). Пример 4. Уравнение на пары множителей Задачи на пары множителей тренируют полноту решения. Задача. Решите \(xy=18\) в положительных целых числах. Решение. Положительные пары множителей: \((1,18),(2,9),(3,6),(6,3),(9,2),(18,1)\). Пример 5. Довести до произведения Это важный олимпиадный прием факторизации. Задача. Решите \(xy+x+y=11\) в положительных целых числах. Решение. Перепишем как \((x+1)(y+1)=12\). Так как \(x,y>0\), оба множителя не меньше \(2\). Пары: \((2,6),(3,4),(4,3),(6,2)\), поэтому \((x,y)=(1,5),(2,3),(3,2),(5,1)\). Пример 6. Разность квадратов Следите, чтобы ученики не забывали отрицательные пары множителей. Задача. Найдите все целые решения уравнения \(x^2-y^2=15\). Решение. Пусть \(a=x-y\), \(b=x+y\). Тогда \(ab=15\), причем \(a,b\) одной четности. Пары множителей нечетные: \((1,15),(3,5),(5,3),(15,1)\) и их отрицательные пары. Из \(x=(a+b)/2\), \(y=(b-a)/2\) получаем \((8,7),(4,1),(4,-1),(8,-7)\) и соответствующие отрицательные пары \((-8,-7),(-4,-1),(-4,1),(-8,7)\). Пример 7. Препятствие по модулю Эта задача связывает модуль 4 с диофантовыми уравнениями. Задача. Докажите, что уравнение \(x^2+y^2=4z+3\) не имеет целых решений. Решение. Квадраты дают \(0\) или \(1\pmod4\). Поэтому \(x^2+y^2\) может давать \(0,1\) или \(2\pmod4\), а \(4z+3\equiv3\pmod4\). Противоречие. Пример 8. Произведение плюс сумма Ученикам может понадобиться помощь в подборе сдвинутых множителей. Задача. Найдите все целые решения уравнения \(xy-2x+3y=7\). Решение. Имеем \((x+3)(y-2)=xy-2x+3y-6\). Так как \(xy-2x+3y=7\), получаем \((x+3)(y-2)=1\). Значит, \((x+3,y-2)=(1,1)\) или \((-1,-1)\). Решения: \((-2,3)\) и \((-4,1)\).

Глава

Диофантовы уравнения I: факторизация и оценки

Модуль учит решать первые диофантовы уравнения олимпиадного типа: линейные уравнения, дополнение до произведения, разность квадратов, уравнения с обратными величинами, модульные запреты и оценки.

Ключевая идея Диофантово уравнение - это уравнение, в котором ищутся целые или натуральные решения. Здесь нельзя просто применить формулу и забыть об ограничении: каждое преобразование должно сохранять целочисленность. Главная мысль первого модуля: сначала превратить уравнение в форму, где видны делимость, множители, остатки или границы. Часто полезно не раскрывать скобки, а наоборот, добавить недостающий член и получить произведение. Основные факты Линейное уравнение \(ax+by=c\) имеет целые решения тогда и только тогда, когда \(\gcd(a,b)\mid c\). Если найдено одно решение \(x_0,y_0\) уравнения \(ax+by=c\), то все решения имеют вид \(x=x_0+\frac{b}{d}t\), \(y=y_0-\frac{a}{d}t\), где \(d=\gcd(a,b)\) и \(t\in\mathbb Z\). Уравнение вида \(xy+ax+by=c\) часто решается добавлением \(ab\): \((x+b)(y+a)=c+ab\). Уравнение \(x^2-y^2=n\) превращается в \((x-y)(x+y)=n\). У множителей должна быть одинаковая четность. Если правая часть мала, а переменные положительны, используйте оценки: произведение растет быстрее суммы. Если выражение не может иметь нужный остаток по модулю \(m\), решений нет. Когда применять метод В задаче просят найти целые или натуральные решения. В уравнении есть произведение \(xy\), сумма \(x+y\), разность квадратов или дробь вида \(\frac{1}{x}+\frac{1}{y}\). Нужно доказать, что решений нет, и видны четность или остатки квадратов. Количество возможных значений можно резко ограничить неравенством. После преобразования одна сторона становится произведением двух целых чисел с известным значением. Как распознать метод Если есть \(xy+ax+by\), попробуйте добавить \(ab\). Если есть \(x^2-y^2\), сразу разложите на \((x-y)(x+y)\). Если есть \(\frac{1}{x}+\frac{1}{y}=\frac{1}{n}\), умножьте на \(nxy\) и дополните до \((x-n)(y-n)=n^2\). Если уравнение кажется слишком свободным, проверьте остатки по малым модулям \(2,3,4,8\). Если переменные положительны, упорядочьте их, например \(x\le y\), и получите верхнюю границу. Типичные ошибки Делят линейное уравнение на число, не проверив, что делится вся правая часть. После факторизации \(AB=n\) забывают отрицательные множители или условие положительности. В уравнении \(x^2-y^2=n\) берут любые множители \(n\), не проверяя одинаковую четность \(x-y\) и \(x+y\). При дополнении до произведения добавляют член к одной части, но не добавляют к другой. В задачах с натуральными решениями находят целые параметры, но не отбирают положительные значения. Мини-чеклист Какие решения нужны: целые, натуральные или неотрицательные? Можно ли получить произведение двух целых множителей? Есть ли условие четности для множителей? Можно ли сначала доказать отсутствие решений по модулю? Если решений много, можно ли записать их параметрически? Если решений конечное число, какая оценка ограничивает перебор?

Пример 1. Линейное уравнение в целых числах Первый навык - проверить НОД и записать все решения через параметр. Задача. Решите в целых числах уравнение \(6x+10y=14\). Решение. Так как \(\gcd(6,10)=2\) и \(2\mid14\), решения существуют. Разделим уравнение на \(2\): \(3x+5y=7\). Одно решение: \(x=-1\), \(y=2\), потому что \(3(-1)+5\cdot2=7\). Все решения получаются так: \(x=-1+5t\), \(y=2-3t\), где \(t\in\mathbb Z\). Комментарий. Коэффициенты \(5\) и \(3\) в параметрах появляются из взаимно простых коэффициентов \(3\) и \(5\). Пример 2. Положительные решения линейного уравнения После общего метода нужно уметь отбирать только натуральные решения. Задача. Найдите все положительные целые решения \(3x+5y=41\). Решение. Рассмотрим уравнение по модулю \(3\): \(5y\equiv 41\pmod3\), то есть \(2y\equiv2\pmod3\). Значит, \(y\equiv1\pmod3\). Так как \(y>0\) и \(5y<41\), получаем \(y\in\{1,4,7\}\). Тогда \(x=\frac{41-5y}{3}\), и решения: \((12,1)\), \((7,4)\), \((2,7)\). Комментарий. Сравнение по модулю одного коэффициента быстро убирает лишний перебор. Пример 3. Дополнение до произведения Выражение \(xy+x+y\) почти равно произведению \((x+1)(y+1)\). Задача. Найдите все положительные целые \(x,y\), для которых \(xy+x+y=35\). Решение. Добавим \(1\) к обеим частям: \(xy+x+y+1=36\), значит, \((x+1)(y+1)=36\). Теперь \(x+1\) и \(y+1\) - положительные делители \(36\), причем оба не меньше \(2\). Поэтому получаем пары \((x,y)\): \((1,17)\), \((2,11)\), \((3,8)\), \((5,5)\), \((8,3)\), \((11,2)\), \((17,1)\). Комментарий. В таких задачах основная идея - увидеть недостающую единицу. Пример 4. Разность квадратов Факторизация \(x^2-y^2\) требует еще и проверки четности множителей. Задача. Найдите все положительные целые решения \(x^2-y^2=45\). Решение. Имеем \((x-y)(x+y)=45\). Оба множителя положительны и имеют одинаковую четность, потому что их сумма равна \(2x\). Так как \(45\) нечетно, оба множителя должны быть нечетными. Берем пары делителей \(45\): \((1,45)\), \((3,15)\), \((5,9)\). Получаем соответственно \((x,y)=(23,22)\), \((9,6)\), \((7,2)\). Комментарий. Пара \((x-y,x+y)\) определяет \(x\) и \(y\) однозначно. Пример 5. Уравнение с обратными величинами Дробное уравнение часто превращается в произведение после умножения на общий знаменатель. Задача. Найдите все положительные целые \(x,y\), такие что \(\frac{1}{x}+\frac{1}{y}=\frac{1}{6}\). Решение. Умножим на \(6xy\): \(6x+6y=xy\). Перенесем и дополним до произведения: \(xy-6x-6y=0\), поэтому \((x-6)(y-6)=36\). Если \(d\) - положительный делитель \(36\), то \(x=6+d\), \(y=6+\frac{36}{d}\). Это дает все решения. Комментарий. Такой прием часто называют дополнением до прямоугольника. Пример 6. Неочевидное произведение Коэффициенты при \(x\) и \(y\) подсказывают, что именно надо добавить. Задача. Найдите все положительные целые решения \(xy=3x+4y\). Решение. Перепишем: \(xy-3x-4y=0\). Добавим \(12\): \((x-4)(y-3)=12\). Пусть \(d\mid12\), \(d>0\). Тогда \(x=4+d\), \(y=3+\frac{12}{d}\). При \(d=1,2,3,4,6,12\) получаем все положительные решения. Комментарий. Не надо угадывать \(x\) и \(y\); после факторизации остается только перебор делителей. Пример 7. Запрет по модулю Иногда лучше сначала доказать, что решений быть не может. Задача. Докажите, что уравнение \(x^2+y^2=8z+6\) не имеет целых решений. Решение. Квадрат целого числа по модулю \(8\) может давать только остатки \(0,1,4\). Поэтому сумма двух квадратов по модулю \(8\) может давать только \(0,1,2,4,5\). Правая часть \(8z+6\) имеет остаток \(6\) по модулю \(8\), что невозможно для суммы двух квадратов. Значит, целых решений нет. Комментарий. Модуль \(8\) особенно полезен для квадратов и четности. Пример 8. Оценка вместо длинного перебора Если произведение делит небольшую сумму, положительность переменных резко ограничивает варианты. Задача. Найдите все положительные целые \(x,y\), для которых \(xy\mid x+y+1\). Решение. Условие симметрично, поэтому можно считать \(x\le y\). Тогда \(xy\le x+y+1\). Если \(x\ge3\), то \(xy\ge3y\), а \(x+y+1\le2y+1\), что невозможно при \(y\ge3\). Значит, \(x=1\) или \(x=2\). При \(x=1\) условие дает \(y\mid y+2\), то есть \(y\mid2\), поэтому \(y=1,2\). При \(x=2\): \(2y\mid y+3\), откуда \(y\le3\); проверка \(y=2,3\) дает только \(y=3\). С учетом симметрии получаем \((1,1)\), \((1,2)\), \((2,1)\), \((2,3)\), \((3,2)\). Комментарий. Оценка показывает, какие маленькие случаи вообще надо проверять.

Глава

Бесконечный спуск

Бесконечный спуск, леммы о чётности, минимальные контрпримеры, примитивные решения и противоречие через меньшее решение.

1. Главная идея Бесконечный спуск - это метод доказательства. Мы предполагаем, что существует положительное целочисленное решение, а затем строим меньшее положительное решение того же типа. Повторять это бесконечно невозможно, потому что положительные целые числа не могут бесконечно убывать. Типичная схема: Предположить, что решение существует. Выбрать решение с наименьшей положительной мерой. Доказать, что из него получается меньшее решение. Получить противоречие. 2. Спуск и четность Многие спуски начинаются с четности. Если \(x^2\) четно, то \(x\) четно. Это может заставить обе переменные делиться на \(2\), после чего деление дает меньшее решение. 3. Пример: \(x^2=2y^2\) Пусть уравнение \(x^2=2y^2\) имеет ненулевое целое решение. Тогда \(x^2\) четно, значит \(x=2k\). Подставляем: \[ 4k^2=2y^2,\qquad y^2=2k^2. \] Значит, \(y\) тоже четно. Обе переменные четны, и после деления на \(2\) получается меньшее решение. Так можно повторять бесконечно, что невозможно. Поэтому единственное целое решение - \((0,0)\). 4. Минимальный контрпример Часто мы предполагаем, что существует наименьший контрпример. Если из него получается меньший контрпример, исходный не мог существовать. 5. Спуск в олимпиадных задачах Бесконечный спуск часто появляется, когда: уравнение заставляет все переменные иметь общий делитель; минимальное решение можно превратить в меньшее; четность или остатки повторяются после масштабирования; "наименьший" объект порождает еще меньший объект.

Пример 1. Четный квадрат Эта лемма постоянно используется в задачах на спуск. Задача. Докажите: если \(n^2\) четно, то \(n\) четно. Решение. Если \(n\) нечетно, то \(n=2k+1\). Тогда \(n^2=4k^2+4k+1\), что нечетно. Поэтому если \(n^2\) четно, то \(n\) не может быть нечетным, значит \(n\) четно. Пример 2. Первый спуск Это модельное доказательство спуском для всего модуля. Задача. Докажите, что единственное целое решение уравнения \(x^2=2y^2\) - это \((0,0)\). Решение. Пусть существует ненулевое решение. Так как \(x^2=2y^2\), число \(x^2\) четно, значит \(x=2k\). Тогда \(4k^2=2y^2\), откуда \(y^2=2k^2\), значит \(y\) четно. Обе переменные четны, и после деления на \(2\) получаем меньшее ненулевое решение. Бесконечно повторять это невозможно. Значит, подходит только \((0,0)\). Пример 3. Иррациональный корень Явно проговорите, что несократимость означает отсутствие общего делителя. Задача. Используйте бесконечный спуск, чтобы доказать, что \(\sqrt2\) иррационально. Решение. Если \(\sqrt2=a/b\), то \(a^2=2b^2\). По идее предыдущего спуска \(a\) и \(b\) должны быть четными. Это противоречит несократимости дроби. Поэтому \(\sqrt2\) иррационально. Пример 4. Спуск по тройке Используйте это, чтобы обобщить идею спуска с \(2\). Задача. Докажите, что единственное целое решение уравнения \(x^2=3y^2\) - это \((0,0)\). Решение. Если \(x^2=3y^2\), то \(3\mid x^2\), значит \(3\mid x\). Пусть \(x=3k\). Тогда \(9k^2=3y^2\), откуда \(y^2=3k^2\), значит \(3\mid y\). Деление обеих переменных на \(3\) дает меньшее ненулевое решение, что невозможно по спуску. Поэтому подходит только \((0,0)\). Пример 5. Нет суммы квадратов Это первый спуск с тремя переменными в курсе. Задача. Докажите, что единственное целое решение уравнения \(x^2+y^2=3z^2\) - это \((0,0,0)\). Решение. По модулю \(3\) правая часть равна \(0\). Так как квадраты дают только \(0\) и \(1\), равенство \(x^2+y^2\equiv0\pmod3\) возможно только при \(x^2\equiv y^2\equiv0\pmod3\). Значит, \(3\mid x\) и \(3\mid y\). Тогда из уравнения следует и \(3\mid z\). Делим все переменные на \(3\) и получаем меньшее ненулевое решение, что невозможно. Значит, только \((0,0,0)\). Пример 6. Минимальный контрпример Это логическая основа метода. Задача. Объясните, почему не может существовать непустое множество положительных целых чисел без наименьшего элемента. Решение. Положительные целые числа вполне упорядочены: любое непустое множество положительных целых чисел имеет наименьший элемент. Бесконечный спуск использует эту идею: если из каждого предполагаемого элемента получается меньший положительный элемент, такого множества не существует. Пример 7. Цепочка спуска Эта абстрактная задача помогает ученикам увидеть скелет доказательства. Задача. Пусть положительное целое число \(n\) обладает свойством \(P\), и из любого положительного числа со свойством \(P\) получается меньшее положительное число со свойством \(P\). Докажите, что ни одно положительное число не обладает свойством \(P\). Решение. Если такие числа существуют, выберем наименьшее, скажем \(n\). По условию из \(n\) получается меньшее положительное число со свойством \(P\), что противоречит минимальности \(n\). Поэтому таких положительных чисел нет. Пример 8. Делимость на все степени Это обосновывает фразу делится на сколь угодно большие степени. Задача. Докажите: если целое число \(n\) делится на \(2^k\) для любого положительного целого \(k\), то \(n=0\). Решение. Если \(n\ne0\), выберем \(k\) так, что \(2^k>|n|\). Ненулевое кратное \(2^k\) по модулю не меньше \(2^k\), что невозможно при \(|n|<2^k\). Значит, \(n=0\).

Глава

Бесконечный спуск I

Модуль вводит бесконечный спуск: минимальный контрпример, спуск по четности и простому делителю, иррациональность квадратных корней, модульные запреты, примитивные решения и первый preview Vieta-descent.

Ключевая идея Бесконечный спуск доказывает невозможность так: предполагаем, что положительное целочисленное решение существует, выбираем самое маленькое по некоторому параметру, а затем строим из него еще меньшее положительное решение. Это противоречит тому, что среди положительных целых чисел нельзя бесконечно убывать. В первом модуле спуска главные источники уменьшения - четность, делимость простым числом, общий множитель и переход от решения к “примитивному” решению. Основные факты Если \(a^2\) четно, то \(a\) четно. Если простое \(p\mid a^2\), то \(p\mid a\). Если из решения \((x,y)\) следует, что \(x\) и \(y\) имеют общий делитель \(d>1\), то часто можно разделить на \(d\) и получить меньшее решение. Чтобы доказать иррациональность \(\sqrt{n}\), удобно предположить \(\sqrt{n}=\frac{a}{b}\) в несократимой дроби и получить общий делитель \(a\) и \(b\). Для уравнений с суммой квадратов полезны остатки квадратов по модулю \(3,5,7,8\). В спуске важно явно указать, какая величина уменьшается: \(x+y\), \(z\), \(\max(x,y)\) или знаменатель дроби. Когда применять метод Нужно доказать, что целых или положительных решений нет. Из уравнения следует, что все переменные делятся на одно и то же простое число. Условие выглядит устойчивым при делении переменных на общий множитель. Обычная проверка по модулю показывает не прямое противоречие, а необходимость общей делимости. Задача про иррациональность квадратного корня или невозможность квадратного уравнения в целых числах. Как распознать метод Если после рассмотрения по модулю \(p\) получается \(p\mid x\), \(p\mid y\), \(p\mid z\), спросите: можно ли разделить все переменные на \(p\) и получить такое же уравнение? Если да, это почти готовый спуск. Если в задаче есть фраза “докажите, что решений нет”, а простая проверка остатков не закрывает задачу полностью, попробуйте выбрать решение с минимальной суммой переменных и построить меньшее. Типичные ошибки Говорят “получим бесконечный спуск”, но не показывают, какое именно меньшее решение построено. Делят на общий множитель, не проверив, что новое решение остается целым и положительным. В доказательстве иррациональности забывают сначала взять дробь в несократимом виде. Из \(p\mid a^2\) делают вывод \(p^2\mid a^2\) без объяснения через \(p\mid a\). Используют “минимальное решение”, но не называют параметр минимальности. Мини-чеклист Что предполагается существующим: положительное решение, ненулевое решение или рациональная дробь? По какому параметру выбираем минимальный объект? Какая модульная проверка заставляет переменные делиться на одно простое число? После деления получается точно то же уравнение? Новое решение строго меньше старого? Где именно возникает противоречие с минимальностью?

Пример 1. Четный квадрат Самый маленький кирпичик спуска - умение переходить от делимости квадрата к делимости числа. Задача. Докажите: если \(a^2\) четно, то \(a\) четно. Решение. Докажем от противного. Если \(a\) нечетно, то \(a=2k+1\). Тогда \(a^2=4k^2+4k+1=2(2k^2+2k)+1\), то есть \(a^2\) нечетно. Противоречие. Значит, \(a\) четно. Комментарий. Именно этот шаг запускает классическое доказательство иррациональности \(\sqrt{2}\). Пример 2. Уравнение \(x^2=2y^2\) Здесь видно, как из одного положительного решения получается меньшее. Задача. Докажите, что уравнение \(x^2=2y^2\) не имеет положительных целых решений. Решение. Предположим, что решение есть. Тогда \(x^2\) четно, значит, \(x\) четно: \(x=2u\). Подставим: \(4u^2=2y^2\), то есть \(y^2=2u^2\). Тогда \(y^2\) четно, значит, \(y\) четно: \(y=2v\). Получили новое решение \(u^2=2v^2\), причем \(u=\frac{x}{2} Комментарий. Можно также выбрать решение с минимальным \(x+y\) и сразу получить противоречие. Пример 3. Иррациональность \(\sqrt{2}\) Доказательство через несократимую дробь - та же идея спуска, но в языке рациональных чисел. Задача. Докажите, что \(\sqrt{2}\) иррационально. Решение. Пусть \(\sqrt{2}=\frac{a}{b}\), где \(a,b\) - положительные целые и дробь несократима. Тогда \(a^2=2b^2\). По предыдущему рассуждению \(a\) четно, значит, \(a=2c\). Тогда \(4c^2=2b^2\), откуда \(b^2=2c^2\), и \(b\) тоже четно. Получили, что \(a\) и \(b\) имеют общий делитель \(2\), что противоречит несократимости дроби. Значит, \(\sqrt{2}\) иррационально. Комментарий. Ключевой момент - заранее взять дробь в несократимом виде. Пример 4. Простое число делит квадрат Для спуска по простому делителю нужен общий факт о квадратах. Задача. Пусть \(p\) - простое число. Докажите, что если \(p\mid a^2\), то \(p\mid a\). Решение. Если \(p\nmid a\), то \(\gcd(p,a)=1\). Тогда \(p\) не делит ни один множитель произведения \(a\cdot a\), что невозможно при \(p\mid a^2\) для простого \(p\). Следовательно, \(p\mid a\). Комментарий. Это прямое применение леммы Евклида. Пример 5. Спуск в сумме квадратов Иногда модуль не дает противоречие сразу, а заставляет все переменные делиться на одно число. Задача. Докажите, что уравнение \(x^2+y^2=3z^2\) не имеет положительных целых решений. Решение. По модулю \(3\) квадрат равен \(0\) или \(1\). Если \(x^2+y^2\equiv0\pmod3\), то оба квадрата должны быть \(0\) по модулю \(3\). Значит, \(3\mid x\) и \(3\mid y\). Пусть \(x=3x_1\), \(y=3y_1\). Тогда \(9x_1^2+9y_1^2=3z^2\), откуда \(3x_1^2+3y_1^2=z^2\). Значит, \(3\mid z^2\), и \(3\mid z\). Делим все переменные на \(3\) и получаем меньшее положительное решение того же уравнения. Бесконечный спуск невозможен. Комментарий. Здесь уменьшается, например, сумма \(x+y+z\). Пример 6. Сведение к уже запрещенному уравнению Некоторые уравнения не требуют нового спуска: они сводятся к базовому случаю. Задача. Докажите, что \(x^2=8y^2\) не имеет положительных целых решений. Решение. Если \(x^2=8y^2\), то \(x^2\) четно, значит, \(x=2u\). Тогда \(4u^2=8y^2\), то есть \(u^2=2y^2\). Но уравнение \(u^2=2y^2\) не имеет положительных целых решений. Противоречие. Комментарий. Сильный ход часто состоит в том, чтобы увидеть знакомый запрещенный вид. Пример 7. Минимальный контрпример Спуск удобно формулировать через минимальное решение. Задача. Покажите, как доказать невозможность \(x^2=2y^2\), выбирая решение с минимальным \(x+y\). Решение. Предположим, что положительные решения существуют, и выберем среди них решение \((x,y)\) с минимальной суммой \(x+y\). Как в примере 2, из \(x^2=2y^2\) следует, что \(x\) и \(y\) четны. Тогда \(\left(\frac{x}{2},\frac{y}{2}\right)\) - новое положительное решение. Но его сумма равна \(\frac{x+y}{2}\), что меньше \(x+y\). Это противоречит минимальности выбранного решения. Комментарий. Такой формат особенно удобен в сложных задачах. Пример 8. Первый Vieta-descent preview Иногда меньшее решение получается не делением, а заменой одного корня квадратного уравнения. Задача. Докажите, что уравнение \(x^2+y^2=3xy\) не имеет положительных целых решений. Решение. Предположим, что решение есть, и выберем его с минимальной суммой \(x+y\). Пусть \(x>y\); случай \(x=y\) невозможен. Рассмотрим уравнение как квадратное относительно \(x\): \(x^2-3yx+y^2=0\). Второй корень равен \(x'=3y-x\). По формулам Виета \(xx'=y^2\), значит, \(x'>0\). Так как \(x>y\), имеем \(x'=\frac{y^2}{x} Комментарий. Это только предварительный взгляд; полноценный Vieta jumping будет в следующей книге.

Глава

Ферма и Эйлер

Малая теорема Ферма, функция Эйлера, теорема Эйлера, обратные элементы и вычисления больших степеней по модулю.

1. Малая теорема Ферма Если \(p\) - простое число и \(p\nmid a\), то \[ a^{p-1}\equiv1\pmod p. \] Равносильная форма: для любого целого \(a\) \[ a^p\equiv a\pmod p. \] Эта теорема позволяет быстро упрощать большие степени по простому модулю. 2. Обратные элементы Если \(\gcd(a,m)=1\), то у \(a\) есть обратный элемент по модулю \(m\). Это значит, что существует целое \(b\), такое что \[ ab\equiv1\pmod m. \] Малая теорема Ферма дает удобный обратный элемент по простому модулю: \[ a^{-1}\equiv a^{p-2}\pmod p. \] 3. Функция Эйлера Функция Эйлера \(\varphi(n)\) считает положительные числа от \(1\) до \(n\), взаимно простые с \(n\). Например, \[ \varphi(10)=4, \] потому что \(1,3,7,9\) взаимно просты с \(10\). Если \[ n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}, \] то \[ \varphi(n)=n\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\cdots\left(1-\frac1{p_k}\right). \] 4. Теорема Эйлера Если \(\gcd(a,n)=1\), то \[ a^{\varphi(n)}\equiv1\pmod n. \] Малая теорема Ферма - это частный случай, когда \(n\) простое. 5. Стратегия для больших степеней Чтобы найти \(a^k\pmod n\): Проверьте, что \(\gcd(a,n)=1\). Если да, уменьшите показатель по модулю \(\varphi(n)\) или найдите более короткий цикл. Если нет, используйте разложение, простые степени или другой модуль.

Пример 1. Ферма по модулю пять Это самый простой первый расчет по малой теореме Ферма. Задача. Найдите \(3^{2026}\pmod5\). Решение. По малой теореме Ферма \(3^4\equiv1\pmod5\). Так как \(2026\equiv2\pmod4\), получаем \(3^{2026}\equiv3^2=9\equiv4\pmod5\). Пример 2. Быстрая степень по модулю семь Короткие циклы иногда удобнее теоремы. Задача. Найдите \(2^{100}\pmod7\). Решение. Так как \(2^3=8\equiv1\pmod7\), уменьшаем показатель по модулю \(3\). Так как \(100\equiv1\pmod3\), получаем \(2^{100}\equiv2\pmod7\). Пример 3. Функция Эйлера списком Список перед формулой сохраняет смысл функции. Задача. Найдите \(\varphi(12)\), выписав положительные числа от \(1\) до \(12\), взаимно простые с \(12\). Решение. Это числа \(1,5,7,11\). Поэтому \(\varphi(12)=4\). Пример 4. Формула функции Эйлера Требуйте разложение на простые множители перед применением формулы. Задача. Найдите \(\varphi(45)\). Решение. \(\varphi(45)=45\left(1-\frac13\right)\left(1-\frac15\right)=45\cdot\frac23\cdot\frac45=24\). Пример 5. Эйлер по модулю десять Свяжите теорему Эйлера с привычными задачами на последнюю цифру. Задача. Найдите последнюю цифру числа \(7^{100}\). Решение. По теореме Эйлера \(7^4\equiv1\pmod{10}\). Так как \(100\equiv0\pmod4\), получаем \(7^{100}\equiv1\pmod{10}\). Последняя цифра равна \(1\). Пример 6. Обратный элемент по модулю одиннадцать Сначала решайте подбором, до формулы Ферма для обратного. Задача. Найдите обратный элемент к \(3\) по модулю \(11\). Решение. \(3\cdot4=12\equiv1\pmod{11}\), значит обратный элемент равен \(4\). Пример 7. Обратный через Ферма Это концептуально важно для решения сравнений. Задача. Используйте малую теорему Ферма, чтобы объяснить, почему \(a^{p-2}\) является обратным к \(a\pmod p\), если \(p\) простое и \(p\nmid 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}\) является обратным к \(a\pmod p\). Пример 8. Степень через Эйлера И снова короткие циклы часто эффективнее полной теоремы Эйлера. Задача. Найдите \(5^{123}\pmod8\). Решение. Так как \(5^2=25\equiv1\pmod8\), нечетные степени \(5\) сравнимы с \(5\pmod8\). Поэтому \(5^{123}\equiv5\pmod8\).

Глава

Ферма, Эйлер и циклы степеней

Модуль учит работать с большими степенями по модулю: короткие циклы, малая теорема Ферма, теорема Эйлера, порядок элемента, обратные элементы и первые ограничения на простые делители степенных выражений.

Ключевая идея Степени по модулю не растут бесконечно: остатки начинают повторяться. Олимпиадная задача обычно состоит не в том, чтобы “посчитать большую степень”, а в том, чтобы выбрать правильный период: короткий цикл, малую теорему Ферма, теорему Эйлера или порядок элемента. Сначала ищите короткий цикл. Если модуль простой, проверьте Ферма. Если модуль составной и основание взаимно просто с модулем, применяйте Эйлера или разбивайте модуль на части. Основные факты Если \(p\) - простое и \(p\nmid a\), то \(a^{p-1}\equiv1\pmod p\). Для любого простого \(p\): \(a^p\equiv a\pmod p\). Если \(\gcd(a,m)=1\), то \(a^{\varphi(m)}\equiv1\pmod m\). Порядок \(\operatorname{ord}_m(a)\) - наименьшее положительное \(t\), для которого \(a^t\equiv1\pmod m\). Если \(a^n\equiv1\pmod m\), то \(\operatorname{ord}_m(a)\mid n\). Для последних двух цифр работаем по модулю \(100\); для последней цифры - по модулю \(10\). Когда применять метод Нужно найти остаток большой степени. Нужно доказать делимость вида \(m\mid a^n-1\) или \(m\mid a^n-a\). В задаче фигурирует простой делитель выражения со степенью. Нужно найти обратный элемент \(a^{-1}\pmod p\). Модуль составной, но основание взаимно просто с ним. Как распознать метод Если показатель огромный, уменьшайте его по периоду. Если модуль простой \(p\), часто период делит \(p-1\). Если модуль составной, сначала проверьте \(\gcd(a,m)=1\); без этого теорему Эйлера применять нельзя. Если в условии простое \(p\mid a^k-1\), переходите к порядку \(a\) по модулю \(p\). Порядок одновременно делит \(k\) и \(p-1\), что часто дает сильное ограничение на \(p\). Типичные ошибки Применяют Ферма к составному модулю. Применяют Эйлера, когда основание не взаимно просто с модулем. Уменьшают показатель по неверному периоду: например, по \(\varphi(m)\), хотя найден более короткий цикл. В задачах на последние две цифры работают только по модулю \(10\). Пишут \(a^{p-1}\equiv1\pmod p\), не проверив \(p\nmid a\). Мини-чеклист Какой модуль нужен: \(10\), \(100\), простой \(p\), составной \(m\)? Взаимно ли просто основание с модулем? Есть ли короткий цикл, который лучше Эйлера? Какой остаток дает показатель по периоду? Если речь о простом делителе, какой порядок возникает? Нужно ли разбить модуль с помощью CRT?

Пример 1. Короткий цикл Иногда период виден быстрее, чем любая большая теорема. Задача. Найдите остаток \(3^{20}\) при делении на \(7\). Решение. Имеем \(3^1\equiv3\), \(3^2\equiv2\), \(3^3\equiv6\), \(3^6\equiv1\pmod7\). Так как \(20\equiv2\pmod6\), получаем \(3^{20}\equiv3^2\equiv2\pmod7\). Комментарий. Период равен \(6\), но достаточно было найти возвращение к \(1\). Пример 2. Последняя цифра Последняя цифра - это остаток по модулю \(10\). Задача. Найдите последнюю цифру числа \(7^{2026}\). Решение. Последние цифры степеней \(7\): \(7,9,3,1\), затем цикл повторяется. Период равен \(4\). Так как \(2026\equiv2\pmod4\), последняя цифра равна второй цифре цикла, то есть \(9\). Комментарий. Не нужно вычислять степень; нужен только показатель по модулю периода. Пример 3. Малая теорема Ферма Для простого модуля показатель \(p-1\) часто обнуляет задачу. Задача. Докажите, что \(11\mid 2^{10}-1\). Решение. Так как \(11\) - простое число и \(11\nmid2\), по малой теореме Ферма \(2^{10}\equiv1\pmod{11}\). Следовательно, \(11\mid2^{10}-1\). Комментарий. Важно явно проверить, что основание не делится на \(11\). Пример 4. Уменьшение показателя Ферма позволяет заменить большой показатель его остатком по \(p-1\). Задача. Найдите остаток \(5^{100}\) по модулю \(13\). Решение. По Ферма \(5^{12}\equiv1\pmod{13}\). Так как \(100\equiv4\pmod{12}\), имеем \(5^{100}\equiv5^4\pmod{13}\). \(5^2=25\equiv-1\pmod{13}\), значит, \(5^4\equiv1\pmod{13}\). Комментарий. Иногда после Ферма остается еще маленький удобный квадрат. Пример 5. Последние две цифры Для последних двух цифр работаем по модулю \(100\), а не только по модулю \(10\). Задача. Найдите последние две цифры числа \(7^{100}\). Решение. Поскольку \(\gcd(7,100)=1\), можно искать цикл. Заметим, что \(7^2=49\), а \(7^4\equiv49^2=2401\equiv1\pmod{100}\). Тогда \(7^{100}=(7^4)^{25}\equiv1\pmod{100}\). Последние две цифры: \(01\). Комментарий. Короткий цикл здесь лучше, чем теорема Эйлера. Пример 6. Когда Эйлер работает Для составного модуля нужно проверить взаимную простоту. Задача. Найдите остаток \(3^{100}\) по модулю \(35\). Решение. \(\gcd(3,35)=1\), поэтому применима теорема Эйлера. \(\varphi(35)=\varphi(5)\varphi(7)=4\cdot6=24\). Так как \(100\equiv4\pmod{24}\), получаем \(3^{100}\equiv3^4=81\equiv11\pmod{35}\). Комментарий. Если основание и модуль не взаимно просты, этот ход был бы незаконным. Пример 7. Порядок элемента Порядок - это настоящий период степеней, начинающихся с \(1\). Задача. Найдите порядок \(2\) по модулю \(9\). Решение. Считаем: \(2^1\equiv2\), \(2^2\equiv4\), \(2^3\equiv8\), \(2^4\equiv7\), \(2^5\equiv5\), \(2^6\equiv1\pmod9\). Раньше \(1\) не появлялась, значит, \(\operatorname{ord}_9(2)=6\). Комментарий. После этого \(2^n\equiv1\pmod9\) тогда и только тогда, когда \(6\mid n\). Пример 8. Обратный элемент через Ферма Ферма дает обратный элемент по простому модулю. Задача. Найдите число, обратное к \(4\) по модулю \(17\). Решение. По Ферма \(4^{16}\equiv1\pmod{17}\), значит, \(4^{15}\) является обратным к \(4\). Но проще заметить: \(4\cdot13=52\equiv1\pmod{17}\). Следовательно, обратный элемент равен \(13\). Комментарий. Теорема объясняет существование обратного, но короткий счет часто быстрее.

Глава

Китайская теорема об остатках

Модуль развивает CRT как метод решения систем сравнений и как инструмент олимпиадного построения: совместимость, не взаимно простые модули, сдвиги, блоки составных чисел и конструкции по заданным делителям.

Ключевая идея Китайская теорема об остатках позволяет строить число с несколькими заданными остатками одновременно. Для олимпиад это не только способ решить систему сравнений, но и метод построения чисел с заранее заданной делимостью. Если модули попарно взаимно просты, система имеет единственное решение по модулю произведения модулей. Если модули не взаимно просты, сначала надо проверить совместимость остатков по общим делителям. Основные факты Если \(\gcd(m,n)=1\), то система \(x\equiv a\pmod m\), \(x\equiv b\pmod n\) имеет единственное решение по модулю \(mn\). Для нескольких попарно взаимно простых модулей решение единственно по модулю их произведения. Система \(x\equiv a\pmod m\), \(x\equiv b\pmod n\) совместна тогда и только тогда, когда \(a\equiv b\pmod{\gcd(m,n)}\). Если найдено одно решение \(x_0\), то все решения имеют вид \(x=x_0+k\operatorname{lcm}(m_1,\ldots,m_s)\). Условия вида \(d\mid n+r\) удобно переписывать как \(n\equiv-r\pmod d\). Когда применять метод Нужно найти число с несколькими заданными остатками. Нужно доказать существование числа с заданными делимостями \(n+a_i\). Модуль большой, но распадается на взаимно простые части. Нужно построить контрпример или бесконечную серию чисел. Нужно доказать, что система сравнений невозможна из-за конфликта по общему делителю. Как распознать метод Если в задаче одновременно встречаются условия “при делении на \(3\)”, “при делении на \(5\)”, “делится на \(7\)”, почти всегда надо перевести их в систему сравнений. Если числа \(n+1,n+2,\ldots\) должны иметь разные делители, запишите отдельное сравнение для каждого сдвига. Перед решением системы проверьте модули. Попарная взаимная простота дает прямой CRT; общие делители требуют проверки совместимости. Типичные ошибки Сразу перемножают модули, хотя они не взаимно просты. Забывают, что ответ задается по модулю НОК, а не обязательно по произведению модулей. Для условия \(d\mid n+r\) записывают \(n\equiv r\pmod d\) вместо \(n\equiv-r\pmod d\). Находят одно решение, но не указывают все решения. В конструкциях забывают проверить, что полученные числа действительно больше своих нетривиальных делителей. Мини-чеклист Все условия уже записаны как сравнения? Модули попарно взаимно просты? Если нет, согласованы ли остатки по НОД? Какой общий модуль ответа: произведение или НОК? Нужно найти наименьшее положительное решение или описать все? Если это конструкция, почему она дает бесконечно много чисел?

Пример 1. Два взаимно простых модуля Базовый CRT: подставляем одно сравнение в другое. Задача. Решите систему \(x\equiv2\pmod3\), \(x\equiv3\pmod5\). Решение. Пусть \(x=3k+2\). Тогда \(3k+2\equiv3\pmod5\), то есть \(3k\equiv1\pmod5\). Умножая на обратный к \(3\) элемент \(2\), получаем \(k\equiv2\pmod5\). Тогда \(x=3(5t+2)+2=15t+8\). Ответ: \(x\equiv8\pmod{15}\). Комментарий. Модули \(3\) и \(5\) взаимно просты, поэтому ответ единственен по модулю \(15\). Пример 2. Совместные не взаимно простые модули Если модули имеют общий делитель, сначала проверяем остатки. Задача. Решите \(x\equiv4\pmod6\), \(x\equiv1\pmod9\). Решение. Общий делитель \(6\) и \(9\) равен \(3\). Остатки \(4\) и \(1\) сравнимы по модулю \(3\), значит, система совместна. Пусть \(x=6k+4\). Тогда \(6k+4\equiv1\pmod9\), то есть \(6k\equiv6\pmod9\). Делим на \(3\): \(2k\equiv2\pmod3\), откуда \(k\equiv1\pmod3\). Следовательно, \(x\equiv10\pmod{18}\). Комментарий. Ответ идет по модулю \(\operatorname{lcm}(6,9)=18\). Пример 3. Несовместимость Иногда CRT нужен, чтобы быстро доказать отсутствие решений. Задача. Докажите, что система \(x\equiv2\pmod6\), \(x\equiv4\pmod9\) не имеет решений. Решение. Из первого сравнения \(x\equiv2\pmod3\). Из второго \(x\equiv1\pmod3\). Одно число не может иметь два разных остатка по модулю \(3\). Значит, решений нет. Комментарий. Это ровно проверка совместимости по НОД. Пример 4. Построение числа CRT строит число с заданными остатками без перебора большого диапазона. Задача. Найдите наименьшее положительное \(n\), для которого \(n\equiv1\pmod2\), \(n\equiv2\pmod3\), \(n\equiv3\pmod5\). Решение. Проверяем числа \(n\equiv3\pmod5\): \(3,8,13,18,23,\ldots\). Среди них условие \(n\equiv2\pmod3\) выполняют \(8,23,\ldots\). Из них нечетное первое число \(23\). Ответ: \(23\). Все решения: \(n\equiv23\pmod{30}\). Комментарий. Для малых модулей допустим аккуратный ручной поиск. Пример 5. Бесконечно много решений Найдя одно решение, мы автоматически получаем бесконечную серию. Задача. Докажите, что существует бесконечно много \(n\), для которых \(n\equiv1\pmod2\), \(n\equiv2\pmod3\), \(n\equiv3\pmod5\). Решение. Из предыдущего примера одно решение \(n=23\). Так как модули \(2,3,5\) попарно взаимно просты, все решения имеют вид \(n=23+30t\), где \(t\in\mathbb Z\). При \(t=0,1,2,\ldots\) получаем бесконечно много положительных решений. Комментарий. CRT часто дает не одно число, а целую арифметическую прогрессию. Пример 6. Делимость сдвигов Условия на \(n+r\) переводятся в остатки для \(n\). Задача. Найдите наименьшее положительное \(n\), для которого \(5\mid n+1\), \(7\mid n+2\), \(11\mid n+3\). Решение. Перепишем: \(n\equiv-1\pmod5\), \(n\equiv-2\pmod7\), \(n\equiv-3\pmod{11}\). То есть \(n\equiv4\pmod5\), \(n\equiv5\pmod7\), \(n\equiv8\pmod{11}\). Проверка дает \(n=19\): \(20\) делится на \(5\), \(21\) на \(7\), \(22\) на \(11\). Все решения: \(n\equiv19\pmod{385}\). Комментарий. Это типичный язык конструкций в CRT. Пример 7. Блок составных чисел CRT и факториал строят длинные блоки чисел с заранее заданными делителями. Задача. Докажите, что существуют \(5\) последовательных составных натуральных чисел. Решение. Возьмем \(N=6!\). Тогда числа \(N+2,N+3,N+4,N+5,N+6\) делятся соответственно на \(2,3,4,5,6\). Каждое из них больше соответствующего делителя, значит, все они составные. Это \(5\) последовательных чисел. Комментарий. Факториал - частный, очень быстрый вариант CRT-конструкции. Пример 8. Невозможная конструкция Не всякая система остатков существует. Задача. Есть ли число \(x\), для которого \(x\equiv4\pmod6\) и \(x\equiv9\pmod{10}\)? Решение. Первое сравнение дает \(x\equiv0\pmod2\), второе дает \(x\equiv1\pmod2\). Противоречие. Поэтому такого числа нет. Комментарий. Самый быстрый тест - сравнить остатки по общему делителю \(2\).

Глава

Подсчёт делителей и специальные числа

Подсчёт делителей через разложение на простые множители, свободные от квадратов делители, произведение делителей, показатели в факториалах и специальные числовые структуры.

1. Подсчёт делителейЕсли \(n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\), то каждый делитель получается выбором показателей \(0\le e_i\le a_i\). Поэтому \(d(n)=(a_1+1)\cdots(a_k+1)\).2. Делители без квадратовУ делителя, свободного от квадратов, каждый показатель простого равен \(0\) или \(1\).3. Произведения и факториалыДелители удобно разбивать на пары \(d\) и \(n/d\). В факториалах показатели простых считаются через целые части.

Пример 1. Подсчёт делителей числа 3600 Это базовая модель подсчёта делителей. Задача. Сколько положительных делителей имеет число \(3600\)? Решение. Так как \(3600=2^4\cdot3^2\cdot5^2\), число делителей равно \(5\cdot3\cdot3=45\). Пример 2. Делители без квадратов Это переформулированная задача на делители без квадратов. Задача. Сколько делителей числа \(2^3\cdot3^2\cdot5\cdot7\) не делятся ни на какой квадрат больше \(1\)? Решение. Есть четыре простых множителя, каждый можно выбрать или не выбрать. Ответ: \(2^4=16\). Пример 3. Семь делителей и квадрат числа Задача проверяет, как число делителей задаёт показатели. Задача. Натуральное число \(n\) имеет ровно \(7\) положительных делителей. Сколько положительных делителей имеет \(n^2\)? Решение. Если \(n=p^6\), то \(n^2=p^{12}\), поэтому \(d(n^2)=13\). Пример 4. Степень пятёрки в факториале Это стандартный подсчёт показателя простого в факториале. Задача. Найдите наибольший показатель \(e\), для которого \(5^e\mid100!\). Решение. Показатель равен \(\lfloor100/5\rfloor+\lfloor100/25\rfloor=20+4=24\).

Глава

Подсчет делителей

Модуль развивает формулу количества делителей, нечетные делители, критерий квадрата, обратные задачи по \( au(n)\), произведение делителей и минимальные числа с заданным количеством делителей.

Ключевая идея Подсчет делителей превращает число в набор показателей простых множителей. Если \(n=p_1^{a_1}\cdots p_s^{a_s}\), то каждый делитель получается независимым выбором показателей \(0,1,\ldots,a_i\). Олимпиадная сила метода появляется тогда, когда нужно не просто посчитать, а восстановить форму числа по количеству делителей или найти наименьшее число с заданным количеством делителей. Основные факты Если \(n=p_1^{a_1}\cdots p_s^{a_s}\), то \(\tau(n)=(a_1+1)\cdots(a_s+1)\). Число \(\tau(n)\) нечетно тогда и только тогда, когда \(n\) является квадратом. Количество нечетных делителей равно количеству делителей нечетной части числа. Если \(n\) не квадрат, его делители разбиваются на пары \(d\) и \(\frac{n}{d}\). Если \(n\) квадрат, один делитель \(\sqrt{n}\) остается без пары. Чтобы минимизировать число при заданных показателях, большие показатели ставят у меньших простых: \(2^{a_1}3^{a_2}5^{a_3}\cdots\) при \(a_1\ge a_2\ge a_3\ge\cdots\). Когда применять метод В задаче спрашивают количество делителей, нечетных делителей или пар делителей. Дано \(\tau(n)\), и нужно описать возможный вид \(n\). Нужно найти наименьшее число с заданным количеством делителей. Нужно понять, когда количество делителей нечетно. В задаче есть произведение делителей или разбиение делителей на пары. Как распознать метод Если условие говорит “ровно \(k\) делителей”, сразу разложите \(k\) на множители вида \(a_i+1\). Если требуется наименьшее число, перебирайте не сами числа, а возможные наборы показателей. Если нужны нечетные делители, отбросьте степень двойки. Если нужно доказать нечетность \(\tau(n)\), используйте парность делителей вокруг \(\sqrt{n}\). Типичные ошибки Забывают вариант нулевого показателя простого множителя. Считают делители списком и легко пропускают один из них. При поиске минимального числа ставят большой показатель на большой простой. Путают число делителей \(n\) и число делителей \(n^2\). Считают, что \(\tau(n)\) нечетно для “почти квадратов”; на самом деле нужен точный квадрат. Мини-чеклист Разложено ли число на простые степени? Для каждого простого учтен показатель \(0\)? Если задано \(\tau(n)\), какие разложения этого числа на множители возможны? Если ищется минимум, расположены ли показатели по убыванию при простых \(2,3,5,\ldots\)? Нужно считать все делители или только нечетные? Является ли \(n\) квадратом?

Пример 1. Формула для \( au(n)\) Главное - перейти от числа к показателям простых множителей. Задача. Найдите число положительных делителей \(360\). Решение. \(360=2^3\cdot3^2\cdot5\). Делитель имеет вид \(2^a3^b5^c\), где \(a=0,1,2,3\), \(b=0,1,2\), \(c=0,1\). Поэтому \(\tau(360)=4\cdot3\cdot2=24\). Комментарий. Нулевой показатель означает, что простой множитель не входит в делитель. Пример 2. Нечетные делители Чтобы считать нечетные делители, степень двойки не нужна. Задача. Сколько нечетных положительных делителей у числа \(720\)? Решение. \(720=2^4\cdot3^2\cdot5\). Нечетный делитель не содержит множитель \(2\), поэтому выбираем только показатели при \(3\) и \(5\). Получаем \((2+1)(1+1)=6\) нечетных делителей. Комментарий. Нечетная часть числа равна \(3^2\cdot5\). Пример 3. Когда \( au(n)\) нечетно Делители обычно идут парами; квадрат дает один непарный делитель. Задача. Докажите, что \(\tau(n)\) нечетно тогда и только тогда, когда \(n\) - квадрат. Решение. Если \(d\mid n\), то \(\frac{n}{d}\mid n\). Обычно делители разбиваются на пары \(d\) и \(\frac{n}{d}\). Непарный делитель возможен только когда \(d=\frac{n}{d}\), то есть \(d^2=n\). Значит, число делителей нечетно ровно для квадратов. Комментарий. Это доказательство не требует формулы для \(\tau(n)\), но хорошо ее объясняет. Пример 4. Наименьшее число с \(12\) делителями Минимизация идет по наборам показателей, а не перебором чисел. Задача. Найдите наименьшее натуральное число, имеющее ровно \(12\) положительных делителей. Решение. Нужно разложить \(12\) как произведение чисел \(a_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\). Комментарий. Большие показатели ставим на меньшие простые. Пример 5. Сумма делителей Хотя модуль про \( au\), полезно увидеть соседнюю функцию \(\sigma\). Задача. Найдите сумму положительных делителей \(72\). Решение. \(72=2^3\cdot3^2\). Сумма делителей равна \((1+2+2^2+2^3)(1+3+3^2)=15\cdot13=195\). Комментарий. Эта идея вернется в поздних модулях об арифметических функциях. Пример 6. Делители квадрата числа У \(n^2\) все показатели удваиваются. Задача. Если \(n=2^3\cdot3^2\cdot5\), найдите \(\tau(n^2)\). Решение. Тогда \(n^2=2^6\cdot3^4\cdot5^2\). Поэтому \(\tau(n^2)=(6+1)(4+1)(2+1)=7\cdot5\cdot3=105\). Комментарий. Не надо сначала вычислять само число \(n^2\). Пример 7. Числа с четырьмя делителями Заданное количество делителей ограничивает форму числа. Задача. Опишите все натуральные \(n\), у которых ровно \(4\) положительных делителя. Решение. Нужно \((a_1+1)\cdots(a_s+1)=4\). Возможности: \(4\) или \(2\cdot2\). Поэтому \(n=p^3\) для простого \(p\), либо \(n=pq\), где \(p\) и \(q\) - различные простые. Комментарий. Это первый шаг к обратным задачам на \(\tau(n)\). Пример 8. Произведение делителей Парность делителей помогает находить их произведение. Задача. Докажите, что произведение всех положительных делителей \(n\) равно \(n^{\tau(n)/2}\). Решение. Каждому делителю \(d\) соответствует делитель \(\frac{n}{d}\), и произведение пары равно \(n\). Поэтому произведение всех делителей равно \(n\), умноженному по одной раз за каждую пару. Число пар равно \(\frac{\tau(n)}{2}\). Если \(n\) квадрат, средний делитель \(\sqrt{n}\) учитывается дважды в записи \(n^{\tau(n)/2}\), и формула все равно верна. Комментарий. Для квадрата показатель может быть полуцелым, но значение остается целым.

Глава

Системы счисления

Перевод между системами счисления, арифметика в недесятичных базах, двоичная запись, подсчёт цифр и конечные нули в других базах.

1. Позиционная записьВ системе с основанием \(b\) запись \(a_ka_{k-1}\cdots a_0\) означает \(a_kb^k+a_{k-1}b^{k-1}+\cdots+a_0\).2. Перевод и арифметикаПоследовательное деление на основание даёт цифры справа налево. Арифметика работает как обычно, но перенос происходит по основанию системы.3. Конечные нулиКоличество конечных нулей в системе с основанием \(b\) определяется разложением \(b\) на простые множители.

Пример 1. Из семеричной системы Это базовый перевод через позиционную запись. Задача. Переведите \(345_7\) в десятичную систему. Решение. \(345_7=3\cdot7^2+4\cdot7+5=147+28+5=180\). Пример 2. В пятеричную систему Задача показывает перевод из десятичной системы через степени основания. Задача. Запишите \(2026\) в системе счисления с основанием \(5\). Решение. \(2026=3\cdot625+1\cdot125+1\cdot25+0\cdot5+1\), поэтому \(2026=31101_5\). Пример 3. Сложение в пятеричной системе Это задача на арифметику в недесятичных системах. Задача. Вычислите \(234_5+143_5\) и запишите ответ в системе с основанием \(5\). Решение. \(234_5=69\), \(143_5=48\), сумма равна \(117=432_5\). Пример 4. Конечные нули в двенадцатеричной системе Задача связывает системы счисления с разложением на простые множители. Задача. Сколькими нулями оканчивается запись \(10!\) в системе счисления с основанием \(12\)? Решение. В \(10!\): \(v_2=8\), \(v_3=4\). Каждый множитель \(12\) требует две двойки и одну тройку, значит ответ \(\min(\lfloor8/2\rfloor,4)=4\).

Глава

Цифры, системы счисления и периодичность

Модуль переводит задачи о цифрах в язык сравнений: признаки делимости, последние цифры, запись в основании \(b\), репьюниты, периоды десятичных дробей и первые конструкции чисел с ограниченными цифрами.

Ключевая идея Задачи о цифрах почти всегда являются задачами о сравнениях. Запись числа в десятичной системе означает разложение по степеням \(10\), а запись в системе с основанием \(b\) означает разложение по степеням \(b\). Поэтому признаки делимости, последние цифры и периоды десятичных дробей нужно переводить на язык остатков. Главный переход такой: если \(N=a_k10^k+\cdots+a_1 10+a_0\), то по модулю \(m\) можно заменить \(10\) на его остаток. Например, по модулю \(9\) имеем \(10\equiv1\), по модулю \(11\) имеем \(10\equiv-1\), а последние \(r\) цифр задаются остатком по модулю \(10^r\). Основные факты Если \(N=\overline{a_ka_{k-1}\ldots a_0}\), то \(N\equiv a_0+\cdots+a_k\pmod9\). По модулю \(11\): \(N\equiv a_0-a_1+a_2-\cdots+(-1)^k a_k\pmod{11}\). Последние \(r\) цифр числа — это остаток по модулю \(10^r\). В системе с основанием \(b\): \((a_ka_{k-1}\ldots a_0)_b=a_kb^k+\cdots+a_1b+a_0\). Если \(\gcd(10,m)=1\), то период дроби \(\frac{1}{m}\) равен порядку числа \(10\) по модулю \(m\) или делит его. Репьюнит \(R_n=\underbrace{11\ldots1}_{n}=\frac{10^n-1}{9}\). Когда применять метод В условии фигурируют цифры числа, сумма цифр, перестановка цифр или запись в другой системе счисления. Нужно найти последние одну, две или три цифры степени. Нужно доказать делимость числа, составленного из одинаковых цифр. В задаче есть десятичная дробь и требуется длина периода. Нужно построить число с ограниченным набором цифр, делящееся на заданное \(m\). Как распознать метод Если в задаче говорится о сумме цифр, почти всегда стоит попробовать модуль \(9\) или \(3\). Если появляется чередующаяся сумма цифр, симметрия или палиндром с чётным числом цифр, проверьте модуль \(11\). Если нужны последние цифры степени, работайте по модулю \(10^r\) и ищите цикл остатков. Если в условии есть число вида \(111\ldots111\), перепишите его как \(R_n=\frac{10^n-1}{9}\). Тогда делимость часто превращается в условие \(10^n\equiv1\pmod m\). Типичные ошибки Пользуются признаком делимости как правилом, но не указывают модуль, в котором он доказан. Забывают условие \(\gcd(10,m)=1\) при обсуждении периода дроби. Считают, что если \(R_a\mid R_b\), то это «очевидно»; на самом деле нужно связать это с \(a\mid b\). Для последних двух цифр работают только по модулю \(25\), забывая совместить с модулем \(4\). В задачах о системе счисления забывают ограничение на цифры: каждая цифра должна быть меньше основания. Мини-чеклист Какая база используется: \(10\) или \(b\)? Какой модуль естественен: \(9\), \(11\), \(10^r\), \(b-1\), \(b+1\)? Нужно ли искать цикл степеней? Можно ли заменить число из единиц на \(R_n=\frac{10^n-1}{9}\)? Проверено ли условие взаимной простоты для периода? Если строится число с цифрами \(0\) и \(1\), можно ли применить принцип Дирихле к остаткам?

Пример 1. Сумма цифр как сравнение Базовый пример: признак делимости на \(9\) доказывается, а не запоминается. Задача. Докажите, что число \(N\) и сумма его десятичных цифр дают одинаковые остатки при делении на \(9\). Решение. Пусть \(N=a_k10^k+\cdots+a_1 10+a_0\). Так как \(10\equiv1\pmod9\), то \(10^i\equiv1\pmod9\) для всех \(i\). Поэтому \(N\equiv a_k+\cdots+a_1+a_0\pmod9\). Комментарий. Именно поэтому делимость на \(9\) проверяется по сумме цифр. Пример 2. Чередующаяся сумма Модуль \(11\) появляется из равенства \(10\equiv-1\pmod{11}\). Задача. Проверьте делимость числа \(583946\) на \(11\). Решение. Вычислим чередующуюся сумму справа налево: \(6-4+9-3+8-5=11\). Она делится на \(11\), значит и число \(583946\) делится на \(11\). Комментарий. Важно брать знаки последовательно; направление не влияет на делимость, но влияет на знак суммы. Пример 3. Последние две цифры Последние две цифры — это остаток по модулю \(100\). Задача. Найдите последние две цифры числа \(7^{50}\). Решение. Так как \(7^4=2401\equiv1\pmod{100}\), то \(7^{50}=7^{4\cdot12+2}\equiv7^2\equiv49\pmod{100}\). Последние две цифры: \(49\). Комментарий. Цикл часто короче, чем даёт теорема Эйлера. Пример 4. Запись в системе счисления Перевод в выражение через основание убирает неоднозначность. Задача. Найдите все основания \(b>6\), при которых число \((253)_b\) делится на \(7\). Решение. Имеем \((253)_b=2b^2+5b+3\). По модулю \(7\): \(2b^2+5b+3\equiv0\). Проверяем остатки \(b\pmod7\): подходит \(b\equiv4\pmod7\). Так как \(b>6\), все основания имеют вид \(b=7t+4\), \(t\ge1\). Комментарий. Не забываем условие \(b>6\), потому что цифра \(6\) не встречается, но цифра \(5\) требует \(b\ge6\), а в условии взято \(b>6\). Пример 5. Период дроби Период \(\frac{1}{m}\) связан с порядком \(10\) по модулю \(m\). Задача. Найдите длину периода десятичной дроби \(\frac{1}{7}\). Решение. Ищем наименьшее \(k>0\), для которого \(10^k\equiv1\pmod7\). Остатки: \(10\equiv3\), \(10^2\equiv2\), \(10^3\equiv6\), \(10^4\equiv4\), \(10^5\equiv5\), \(10^6\equiv1\pmod7\). Значит, период равен \(6\). Комментарий. Это не вычисление всей дроби, а поиск цикла остатков. Пример 6. Число из единиц Репьюнит переводит задачу в сравнение для степени \(10\). Задача. Докажите, что число \(111111\) делится на \(7\), \(11\) и \(13\). Решение. Имеем \(111111=R_6=\frac{10^6-1}{9}\). Также \(1001=7\cdot11\cdot13\), а \(111111=111\cdot1001\). Следовательно, число делится на \(7\), \(11\) и \(13\). Комментарий. Иногда проще разложить число на блоки, чем работать напрямую с длинной записью. Пример 7. Все длины репьюнитов Условие \(R_n\mid R_m\) связано с делимостью индексов. Задача. Докажите, что если \(a\mid b\), то \(R_a\mid R_b\). Решение. Пусть \(b=qa\). Тогда \(R_b=1+10+\cdots+10^{b-1}\). Разобьём сумму на блоки длины \(a\): \(R_b=R_a(1+10^a+10^{2a}+\cdots+10^{(q-1)a})\). Значит, \(R_a\mid R_b\). Комментарий. Обратное утверждение требует дополнительной работы и обычно доказывается через порядок \(10\). Пример 8. Число из цифр \(0\) и \(1\) Это первый важный пример, где появляется принцип Дирихле. Задача. Докажите, что для любого \(m\), взаимно простого с \(10\), существует число, состоящее только из единиц, которое делится на \(m\). Решение. Рассмотрим \(m\) чисел \(R_1,R_2,\ldots,R_m\). Если какое-то из них делится на \(m\), всё доказано. Иначе два из них имеют одинаковый остаток: \(R_i\equiv R_j\pmod m\), \(i Комментарий. Этот ход часто строит кратное число без явного вычисления.

Глава

Дроби, десятичная запись и периодичность

Конечные десятичные дроби, периодические дроби, длина периода и структура десятичной записи дробей.

1. Конечные десятичные дробиНесократимая дробь \(a/b\) имеет конечную десятичную запись тогда и только тогда, когда простые делители \(b\) — только \(2\) и \(5\).2. Количество знаков после запятойЕсли \(b=2^r5^s\), то для записи \(a/b\) достаточно \(\max(r,s)\) знаков после запятой.3. Периодические дробиЕсли в знаменателе есть другой простой делитель, при делении в столбик остаток рано или поздно повторится.

Пример 1. Критерий конечной записи Это основной критерий конечной десятичной записи. Задача. Объясните, почему несократимая дробь со знаменателем \(2^a5^b\) имеет конечную десятичную запись. Решение. Если \(m=\max(a,b)\), то \(2^a5^b\mid10^m\). Значит, дробь можно записать со знаменателем \(10^m\). Пример 2. Сколько знаков после запятой Это быстрый вычислительный вариант критерия. Задача. Сколько знаков после запятой нужно для записи \(\frac{7}{2^3\cdot5^5}\)? Решение. Знаменатель делит \(10^5\), но не меньшую степень \(10\). Нужно \(5\) знаков после запятой. Пример 3. Перевести периодическую дробь Это стандартный алгебраический перевод периодической дроби. Задача. Запишите \(0.\overline{27}\) в виде несократимой дроби. Решение. Если \(x=0.\overline{27}\), то \(100x=27.\overline{27}\). Поэтому \(99x=27\), значит \(x=3/11\). Пример 4. Пятидесятая цифра дроби одна седьмая Это задача на номер цифры в периоде. Задача. Найдите \(50\)-ю цифру после запятой в записи \(\frac17=0.\overline{142857}\). Решение. Так как \(50\equiv2\pmod6\), нужна вторая цифра периода \(142857\), то есть \(4\).

Глава

Смешанные задачи I

Модуль тренирует выбор метода без заранее объявленной темы: делимость, НОД, сравнения, факторизация, диофантовы уравнения, периоды, CRT, спуск и конструкции.

Ключевая идея В смешанных задачах метод не указан заранее. Цель модуля — научиться распознавать, что именно мешает прямому решению: большой параметр, скрытый НОД, невозможный остаток, выражение, которое надо разложить, или конструкция, которую нужно построить. Хорошая олимпиадная работа начинается не с вычислений, а с выбора языка: делимость, сравнения, НОД, факторизация, спуск, порядок или CRT. Один и тот же пример часто можно начать несколькими способами, но только один из них быстро убирает лишнюю сложность. Основные факты Если нужно доказать делимость на составное число, разбивайте его на взаимно простые множители. Если есть \(\gcd(f(n),g(n))\), применяйте алгоритм Евклида: вычитайте кратные выражения. Если уравнение выглядит невозможным, проверьте квадраты по модулям \(3,4,5,8\). Если есть произведение и сумма, пробуйте довести до формы \((x+a)(y+b)=c\). Если нужно построить число с несколькими остатками, переводите условия в систему сравнений. Если задача о бесконечности решений или невозможности, ищите минимальный контрпример или спуск. Когда применять метод После прочтения задачи непонятно, к какому модулю или формуле она относится. В условии смешаны степени, делимость, цифры, НОД или уравнения. Обычная проверка случаев быстро становится длинной. Нужно не просто найти ответ, а объяснить, почему других вариантов нет. Как распознать метод Сначала спросите: что будет, если заменить переменную остатком? Если выражение резко упрощается — это модульная задача. Если два выражения имеют общий делитель, попробуйте заменить одно на разность. Если есть произведение \(xy\) и линейные члены, ищите факторизацию с добавлением константы. Если задача просит доказать существование, подумайте о CRT или принципе Дирихле. Если задача просит доказать невозможность для натуральных чисел, проверьте остатки и возможность бесконечного спуска. Типичные ошибки Сразу перебирают большие значения вместо выбора модуля. Забывают проверить, что найденные делители положительны и дают натуральные решения. Путают доказательство «существует» с нахождением одного маленького примера. Делят сравнение на число, не проверив взаимную простоту. В задачах на спуск не показывают, что новое решение действительно меньше. Мини-чеклист Есть ли естественный модуль? Можно ли заменить НОД более простым НОД? Можно ли разложить выражение или дополнить до произведения? Нужно ли строить число, а не вычислять его? Если найден кандидат, проверены ли все условия? Если доказывается невозможность, где именно возникает противоречие?

Пример 1. Делимость без перебора Тренируем выбор взаимно простых множителей. Задача. Докажите, что \(n^3-n\) делится на \(6\) при любом целом \(n\). Решение. Имеем \(n^3-n=n(n-1)(n+1)\), произведение трёх последовательных целых чисел. Среди них есть чётное число, значит произведение делится на \(2\). Также среди трёх последовательных чисел есть число, делящееся на \(3\). Так как \(2\) и \(3\) взаимно просты, произведение делится на \(6\). Комментарий. Метод выбран по составному делителю \(6=2\cdot3\). Пример 2. НОД через вычитание Сложный вид НОД часто скрывает маленький делитель. Задача. Найдите \(\gcd(n^2+1,n+1)\). Решение. Вычтем: \(n^2+1-(n-1)(n+1)=2\). Значит общий делитель делит \(2\). Если \(n\) нечётно, то \(n+1\) чётно и \(n^2+1\) чётно, НОД равен \(2\). Если \(n\) чётно, оба числа не могут быть чётными, НОД равен \(1\). Комментарий. Ответ: \(2\) при нечётном \(n\), \(1\) при чётном \(n\). Пример 3. Невозможность по модулю Иногда весь перебор заменяется таблицей квадратов. Задача. Докажите, что уравнение \(x^2+y^2=8z+7\) не имеет целых решений. Решение. Квадрат по модулю \(8\) может давать только \(0,1,4\). Сумма двух таких остатков не может быть равна \(7\) по модулю \(8\): возможны \(0,1,2,4,5\). Но правая часть сравнима с \(7\) по модулю \(8\). Противоречие. Комментарий. Ключ — выбрать модуль \(8\), а не решать уравнение. Пример 4. Делитель линейного вида Скрытый ход — умножить на \(4\), чтобы появился квадрат делителя. Задача. Найдите все натуральные \(n\), для которых \(2n+1\mid n^2+n+3\). Решение. Если \(2n+1\mid n^2+n+3\), то \(2n+1\mid4(n^2+n+3)\). Но \(4(n^2+n+3)=(2n+1)^2+11\). Значит \(2n+1\mid11\). Так как \(n\ge1\), \(2n+1\ge3\), поэтому \(2n+1=11\), откуда \(n=5\). Проверка: \(11\mid33\). Комментарий. Это типичная олимпиадная замена: сделать выражение кратным делителю. Пример 5. Дополнение до произведения Уравнение с \(xy\) и линейными членами часто факторизуется. Задача. Решите в натуральных числах \(xy+x+y=35\). Решение. Добавим \(1\): \((x+1)(y+1)=36\). Теперь перебираем пары делителей \(36\), большие \(1\). Получаем \((x,y)=(1,17),(2,11),(3,8),(5,5),(8,3),(11,2),(17,1)\). Комментарий. Факторизация превратила бесконечный поиск в конечный список делителей. Пример 6. Репьюнит и порядок Длинное число из единиц лучше заменить сравнением для \(10^n\). Задача. Найдите все \(n\), при которых число \(R_n\) делится на \(13\). Решение. Так как \(13\) взаимно просто с \(9\), условие \(13\mid R_n\) эквивалентно \(10^n\equiv1\pmod{13}\). Ранее находим порядок \(10\) по модулю \(13\): он равен \(6\). Поэтому \(13\mid R_n\) тогда и только тогда, когда \(6\mid n\). Комментарий. Метод выбирается по форме \(111\ldots111\). Пример 7. Спуск вместо перебора Если положительное решение порождает меньшее положительное решение, решений нет. Задача. Докажите, что \(x^2+y^2=3xy\) не имеет натуральных решений. Решение. Пусть решение есть, и выберем его с минимальной суммой \(x+y\). Пусть \(x\ge y\). Тогда \(x<3y\), иначе левая часть была бы слишком большой. Уравнение как квадратное относительно \(x\) имеет второй корень \(x'=3y-x\). Он положителен, целый и также даёт решение. Кроме того, из \(x(3y-x)=y^2\) следует \(x>2y\), значит \(0 Комментарий. Это первый вкус виетова спуска без тяжёлой техники. Пример 8. Конструкция блока Существование часто доказывается построением, а не поиском маленького примера. Задача. Докажите, что существуют \(5\) последовательных составных чисел. Решение. Возьмём число \(N=6!\). Тогда числа \(N+2,N+3,N+4,N+5,N+6\) делятся соответственно на \(2,3,4,5,6\) и больше этих делителей. Значит каждое из них составное. Комментарий. Это конструкция через факториал; позднее её можно заменить CRT-конструкциями.

Глава

Правила делимости

Признаки делимости, доказательства правил через сравнения, задачи на неизвестные цифры и рассуждения по последним цифрам.

1. Сумма цифрТак как \(10\equiv1\pmod9\), любое десятичное число имеет тот же остаток по модулю \(9\), что и сумма его цифр.2. Последние цифрыПо модулям \(2,4,5,8,10\) важны только последние несколько цифр.3. Признак делимости на 11Так как \(10\equiv-1\pmod{11}\), делимость на \(11\) определяется знакопеременной суммой цифр.

Пример 1. Почему работает признак делимости на 9 Это главное доказательство признаков через сумму цифр. Задача. Докажите, что десятичное число имеет тот же остаток по модулю \(9\), что и сумма его цифр. Решение. Если \(n=a_k10^k+\cdots+a_0\), то \(10^j\equiv1\pmod9\). Поэтому \(n\equiv a_k+\cdots+a_0\pmod9\). Пример 2. Неизвестная цифра Задача совмещает два признака делимости. Задача. Найдите все цифры \(A\), при которых число \(52A8\) делится и на \(3\), и на \(4\). Решение. Для делимости на \(4\): \(10A+8\equiv2A\pmod4\), значит \(A\) чётна. Для делимости на \(3\): \(15+A\) делится на \(3\), значит \(A\in\{0,3,6,9\}\). Поэтому \(A=0\) или \(6\). Пример 3. Цифры для делимости на 11 и 5 Это задача на неизвестные цифры с признаком делимости на 11. Задача. Найдите все цифры \(A,B\), при которых число \(3A5B\) делится и на \(11\), и на \(5\). Решение. Для делимости на \(11\) число \(8-A-B\) должно делиться на \(11\). Если \(B=0\), то \(A=8\). Если \(B=5\), то \(A=3\). Получаем \(3850\) и \(3355\). Пример 4. Делимость на 72 Это компактная задача на совмещение нескольких признаков. Задача. Найдите все пары цифр \(A,B\), при которых число \(72A4B\) делится на \(72\). Решение. Нужна делимость на \(8\) и \(9\). Проверяя последние три цифры \(A4B\) и сумму \(13+A+B\), получаем пары \((1,4)\) и \((6,8)\). Подходят \(72144\) и \(72648\).

Глава

Пробные олимпиады I

Финальный модуль первой книги по теории чисел: тренировочные задачи без подсказанного метода, имитирующие короткие олимпиадные варианты и закрепляющие выбор стратегии.

Ключевая идея Пробный тур отличается от тематического листка: в условии не написано, какой метод применять. Поэтому главная цель — научиться быстро классифицировать задачу, выбрать первый осмысленный ход и не застрять в длинном переборе. В этом модуле задачи устроены как тренировочные варианты: от коротких технических вопросов к задачам, где нужно соединить две идеи. После решения важно не только получить ответ, но и сформулировать, почему выбранный метод был естественным. Основные факты Сначала ищите маленький модуль: \(2,3,4,5,7,8,9,11\). В задачах на делимость выражения \(f(n)\) делителем вида \(an+b\) полезно выразить \(f(n)\) через этот делитель. Диофантовы уравнения первого уровня часто решаются разложением на множители. Задачи на длинные числа из одинаковых цифр переводятся в репьюниты \(R_n=\frac{10^n-1}{9}\). Существование чисел с заданными делимостями часто доказывается CRT, факториалом или принципом Дирихле. Когда применять метод Когда вы решаете набор задач без указания темы. Когда первая идея даёт слишком много случаев. Когда задача похожа на школьную, но требует доказать отсутствие других вариантов. Когда нужно распределить время между задачами разной сложности. Как распознать метод Если задача просит “докажите делимость”, разложите делитель и проверьте остатки. Если есть “найдите все \(n\)”, попробуйте получить малый делитель из выражения. Если есть “существуют ли”, подумайте о конструкции, а не о поиске маленького примера. Для mock-тура полезно сначала пометить задачи: техника, стандартный метод, одна скрытая идея, сильная задача. Это помогает не тратить всё время на одну середину варианта. Типичные ошибки Решают задачи строго по порядку, хотя более поздняя задача может быть короче. Пишут вычисления без объяснения выбора модуля. В задачах “найдите все” забывают обратную проверку. В конструкциях находят один пример, хотя нужно доказать существование для любого параметра. После получения противоречия не указывают, какое предположение опровергнуто. Мини-чеклист Что требуется: доказать, найти все, построить, опровергнуть? Есть ли естественный малый модуль? Можно ли заменить выражение по модулю делителя? Есть ли факторизация после добавления константы? Если задача конструктивная, какой инструмент строит объект? В конце проверены ли все найденные ответы?

Пример 1. Быстрая классификация Задача выглядит как степень, но решается разложением делителя. Задача. Докажите, что \(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\). Пример 2. Все решения без перебора Факторизация превращает уравнение в список делителей. Задача. Решите \(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)\). Комментарий. После решения обязательно проверяем положительность. Пример 3. Делитель вида \(an+b\) Скрытая техника — выразить многочлен через делитель. Задача. Найдите все натуральные \(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\). Пример 4. Период вместо длинной степени Последние цифры — это задача о цикле остатков. Задача. Найдите последние две цифры \(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\). Пример 5. Конструкция через факториал Когда нужно доказать существование блока, явное маленькое число не обязательно. Задача. Докажите, что существуют \(8\) последовательных составных чисел. Решение. Возьмём \(N=9!\). Тогда \(N+2,N+3,\ldots,N+9\) делятся соответственно на \(2,3,\ldots,9\) и больше этих делителей. Поэтому все они составные. Комментарий. Такая конструкция работает для любого числа последовательных составных чисел. Пример 6. Проверка ложного утверждения В mock-туре иногда нужно вовремя увидеть контрпример. Задача. Верно ли, что каждое число вида \(n^2+n+41\) простое? Решение. Нет. При \(n=41\) получаем \(41^2+41+41=41(41+1+1)=41\cdot43\), составное число. Комментарий. Слова “каждое” и “для всех” всегда требуют проверки крайних или специальных значений.