Теория курса
Теория чисел. Книга 2
Book 2. Olympiad Number Theory Methods
- 1. Продвинутые задачи на НОД
- 2. Квадратичные остатки и модульные препятствия
- 3. Мультипликативный порядок
- 4. Теоремы Вильсона, Ферма и Эйлера в задачах
- 5. p-адические показатели
- 6. LTE: поднятие показателя
- 7. Диофантовы уравнения I: факторизация и оценки
- 8. Диофантовы уравнения II: спуск и прыжок Виета
- 9. Китайская теорема об остатках и построения
- 10. Арифметические функции
- 11. Цифры, системы счисления и десятичные периоды
- 12. Многочлены, последовательности и теория чисел
Глава
Продвинутые задачи на НОД
Ключевая идея
Сильные задачи на НОД редко сводятся к вычислению. Главная техника - заменить пару чисел на более простую пару с тем же НОД: вычитать кратные, брать линейные комбинации, использовать остатки многочлена при делении и переводить степень в показатель.
Основные факты
Используем свойства \( \gcd(a,b)=\gcd(a,b-ka) \), \( \gcd(a,b)=\gcd(a, b \bmod a) \), а также факт: если \(d\) делит два числа, то \(d\) делит любую их целую линейную комбинацию. Если \( \gcd(a,b)=1 \) и \(a\mid bc\), то \(a\mid c\). Для степеней особенно важна формула \( \gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1 \).
Когда применять метод
Метод НОД применяют, когда в задаче есть делимость двух выражений, условие вида \( \gcd(f(n),g(n))>1 \), степени \(a^m-1\), соседние значения последовательности или требование найти все параметры, при которых общий делитель не равен единице.
Как распознать метод
Ищите возможность подставить остаток: если делитель содержит \(n+c\), замените \(n\) на \(-c\) в другом выражении. Если есть степени с разными показателями, применяйте алгоритм Евклида к показателям. Если числа взаимно просты, проверяйте, не вынуждает ли общий простой делитель делить оба исходных числа.
Типичные ошибки
Нельзя делить сравнение на число, не проверив взаимную простоту. Нельзя из \(d\mid ab\) сразу делать вывод \(d\mid a\) или \(d\mid b\). В задачах со степенями часто забывают доказать обе стороны: что найденное число действительно делит оба выражения и что большего общего делителя быть не может.
Мини-чеклист
1. Какие два выражения имеют общий делитель? 2. Можно ли заменить одно выражение линейной комбинацией? 3. Можно ли уменьшить степень или показатель? 4. Что происходит с простым делителем? 5. Есть ли условие взаимной простоты? 6. Проверены ли все возможные остатки или параметры?
Пример 1. Остаток вместо длинного деления
Учит заменять многочлен его остатком по модулю линейного выражения.
Задача. Найдите все возможные значения \( \gcd(n+5,n^2+3n+9) \) при натуральном \(n\).
Пусть \(d=\gcd(n+5,n^2+3n+9)\). Так как \(n\equiv -5 \pmod{n+5}\), получаем \(n^2+3n+9\equiv 25-15+9=19\pmod{n+5}\). Поэтому \(d=\gcd(n+5,19)\). Возможны только \(1\) и \(19\). Оба значения достигаются: например, если \(n+5\) не делится на \(19\), получаем \(1\), а при \(n=14\) получаем \(19\).
Комментарий. Линейный множитель превращает многочлен в постоянный остаток.
Пример 2. НОД выражения и соседнего линейного множителя
Показывает, как доказывать, что общий делитель ограничен маленьким числом.
Задача. Докажите, что \( \gcd(n^2+n+1,n-1) \) делит \(3\).
Если \(d\mid n-1\), то \(n\equiv1\pmod d\). Тогда \(n^2+n+1\equiv 1+1+1=3\pmod d\). Значит, если \(d\) делит также \(n^2+n+1\), то \(d\mid3\). Следовательно, \( \gcd(n^2+n+1,n-1)\mid3\).
Комментарий. Мы не обязаны сразу находить НОД; часто достаточно ограничить его.
Пример 3. НОД чисел вида \(a^m-1\)
Стандартный олимпийский шаблон: алгоритм Евклида переносится на показатели.
Задача. Докажите, что \( \gcd(2^m-1,2^n-1)=2^{\gcd(m,n)}-1 \).
Обозначим \(g=\gcd(m,n)\). Число \(2^g-1\) делит оба числа, потому что \(g\mid m\) и \(g\mid n\). Осталось доказать, что большего общего делителя нет. Если \(m>n\), то \(2^m-1-(2^{m-n})(2^n-1)=2^{m-n}-1\). Значит, общий делитель \(2^m-1\) и \(2^n-1\) делит также \(2^{m-n}-1\). Повторяя шаги алгоритма Евклида для показателей, приходим к \(2^g-1\).
Комментарий. Важно делать Евклидов алгоритм не с самими огромными числами, а с показателями.
Пример 4. Общий делитель и взаимная простота
Учит исключать простой делитель через противоречие с \( \gcd(a,b)=1 \).
Задача. Пусть \( \gcd(a,b)=1 \). Докажите, что \( \gcd(a+b,a^2+b^2) \) делит \(2\).
Пусть простой \(p\) делит \(a+b\) и \(a^2+b^2\). Из \(a+b\equiv0\pmod p\) имеем \(b\equiv -a\pmod p\). Тогда \(a^2+b^2\equiv2a^2\pmod p\). Если \(p\ne2\), то \(p\mid a\), а значит \(p\mid b\), что невозможно. Следовательно, единственный возможный простой делитель - \(2\), и весь НОД делит \(2\).
Комментарий. Не надо раскладывать \(a^2+b^2\); достаточно посмотреть на простой делитель.
Пример 5. Когда общий делитель задаёт сравнение
Показывает, как условие \( \gcd>1 \) превращается в сравнение.
Задача. Найдите все натуральные \(n\), для которых \( \gcd(n^2+2,n^3+3)>1 \).
Пусть \(d\) - общий делитель. Тогда \(d\mid n(n^2+2)-(n^3+3)=2n-3\). Умножим первое выражение на \(4\): \(4(n^2+2)=4n^2+8\). Из \(2n\equiv3\pmod d\) следует \(4n^2\equiv9\pmod d\), поэтому \(d\mid17\). Значит, возможен только общий простой делитель \(17\). Он действительно появляется, когда \(2n\equiv3\pmod{17}\), то есть \(n\equiv10\pmod{17}\). Ответ: \(n\equiv10\pmod{17}\).
Комментарий. Сначала общий делитель резко ограничивается, затем проверяется достижимость.
Пример 6. Степени с двумя основаниями
Готовит к задачам, где надо перейти к обратному элементу.
Задача. Пусть \(a>b>0\) и \( \gcd(a,b)=1 \). Докажите, что \( \gcd(a^m-b^m,a^n-b^n)=a^{\gcd(m,n)}-b^{\gcd(m,n)} \).
Пусть \(g=\gcd(m,n)\). Правая часть делит оба выражения. Для обратного включения возьмём общий делитель \(d\). Так как \( \gcd(b,d)=1 \), число \(b\) обратимо по модулю \(d\). Из \(a^m\equiv b^m\) и \(a^n\equiv b^n\) получаем \((ab^{-1})^m\equiv1\) и \((ab^{-1})^n\equiv1\pmod d\). Тогда \((ab^{-1})^g\equiv1\pmod d\), значит \(a^g\equiv b^g\pmod d\), то есть \(d\mid a^g-b^g\).
Комментарий. Скрытый ход - делить на \(b\) можно только после проверки взаимной простоты.
Пример 7. НОД соседних факториалов
Показывает, как линейная комбинация даёт маленькое число.
Задача. Докажите, что \( \gcd(n!+1,(n+1)!+1)=1 \).
Пусть \(d\) делит оба числа. Тогда \(d\mid (n+1)!+1-(n+1)(n!+1)=-n\). Значит, \(d\mid n\). Но из \(d\mid n!+1\) и \(d\mid n\) следует, что \(d\mid n!\), а значит \(d\mid1\). Следовательно, \(d=1\).
Комментарий. Комбинация выбрана так, чтобы уничтожить факториал.
Пример 8. Сильная задача на простой делитель
Олимпиадный пример: вместо вычисления НОД анализируем возможный простой делитель.
Задача. Пусть \( \gcd(a,b)=1 \). Найдите \( \gcd(a^2+b^2,a^3+b^3) \).
Рассмотрим нечётный простой \(p\), делящий оба числа. Так как \(p\nmid b\), можно положить \(t\equiv ab^{-1}\pmod p\). Тогда \(t^2\equiv-1\) и \(t^3\equiv-1\pmod p\). Делим второе сравнение на первое: получаем \(t\equiv1\pmod p\), но тогда \(1\equiv-1\pmod p\), что невозможно для нечётного \(p\). Значит, нечётных простых делителей нет. Осталось проверить \(2\): если \(a,b\) оба нечётны, оба выражения чётны, но \(a^2+b^2\equiv2\pmod4\), поэтому НОД равен \(2\). Если один из \(a,b\) чётен, оба выражения нечётны, и НОД равен \(1\).
Комментарий. Такой разбор тренирует работу с простым делителем и обратным элементом.
Глава
Квадратичные остатки и модульные препятствия
Ключевая идея
Квадратичные остатки помогают доказывать невозможность. Вместо перебора всех целых чисел мы смотрим, какими могут быть квадраты по малому модулю, и выбираем модуль, где правая и левая части попадают в разные множества остатков.
Основные факты
Квадраты по модулю \(4\) дают только \(0,1\); по модулю \(8\) - только \(0,1,4\); по модулю \(3\) - только \(0,1\); по модулю \(5\) - только \(0,1,4\). Если нечётный простой \(p\) делит \(a^2+1\), то \(p=2\) или \(p\equiv1\pmod4\). Если \(p\equiv3\pmod4\) и \(p\mid x^2+y^2\), то \(p\mid x\) и \(p\mid y\).
Когда применять метод
Метод нужен, когда уравнение содержит квадраты, сумму квадратов, выражения \(a^2+1\), \(a^2+b^2\), \(a^2+ab+b^2\), или когда нужно доказать, что решений нет. Он особенно полезен перед тяжёлыми диофантовыми задачами.
Как распознать метод
Если правая часть имеет вид \(4k+3\), пробуйте модуль \(4\). Если появляется \(8k+7\), пробуйте модуль \(8\). Если есть \(a^2+1\), думайте о \(-1\) как о квадрате. Если есть \(a^2+ab+b^2\), умножение на обратный элемент часто приводит к элементу порядка \(3\).
Типичные ошибки
Нельзя делать вывод по одному модулю, если множество остатков ещё не проверено полностью. Нельзя делить на \(b\) по модулю \(p\), пока не доказано \(p\nmid b\). В descent-задачах нужно показать, что новый меньший тройной набор действительно целый.
Мини-чеклист
1. Какие остатки принимают квадраты? 2. Какой модуль видит противоречие? 3. Можно ли рассмотреть простой делитель? 4. Разрешено ли делить на переменную по модулю? 5. Если общий делитель вынуждает делимость всех переменных, даёт ли это бесконечный спуск?
Пример 1. Квадраты по модулю \(8\)
Базовая техника: составить таблицу остатков квадратов.
Задача. Докажите, что квадрат целого числа по модулю \(8\) равен \(0\), \(1\) или \(4\).
Достаточно проверить остатки \(0,1,\ldots,7\). Квадраты дают \(0,1,4,1,0,1,4,1\). Значит, множество квадратов по модулю \(8\) равно \(\{0,1,4\}\).
Комментарий. Эта таблица будет использоваться в задачах на суммы квадратов.
Пример 2. Невозможность по модулю \(4\)
Показывает самый частый запрет для суммы двух квадратов.
Задача. Докажите, что уравнение \(x^2+y^2=4z+3\) не имеет целых решений.
Квадрат по модулю \(4\) равен \(0\) или \(1\). Поэтому сумма двух квадратов по модулю \(4\) может быть только \(0,1,2\). Правая часть равна \(3\pmod4\), что невозможно.
Комментарий. Модуль \(4\) выбран потому, что правая часть явно имеет остаток \(3\).
Пример 3. Квадратичное сравнение с параметром
Учит решать простое сравнение через таблицу.
Задача. Найдите все \(n\), для которых \(7\mid n^2+n+1\).
Проверим остатки \(n\pmod7\): значения \(n^2+n+1\) равны \(1,3,0,6,0,3,1\). Поэтому \(n\equiv2\) или \(n\equiv4\pmod7\).
Комментарий. Таблица допустима, когда модуль мал.
Пример 4. Почему \(-1\) не всегда квадрат
Связывает квадратичные остатки с простыми делителями.
Задача. Пусть нечётный простой \(p\mid a^2+1\). Докажите, что \(p\equiv1\pmod4\).
Если \(p\mid a\), то \(p\mid1\), невозможно. Значит, \(a\not\equiv0\pmod p\). Из \(a^2\equiv-1\pmod p\) следует \(a^4\equiv1\), но \(a^2\not\equiv1\). Поэтому порядок \(a\) по модулю \(p\) равен \(4\). Порядок делит \(p-1\), значит \(4\mid p-1\).
Комментарий. Это первый взгляд на связь остатков и порядка по модулю.
Пример 5. Сумма трёх квадратов
Показывает, как сумма допустимых остатков тоже имеет ограничения.
Задача. Докажите, что \(x^2+y^2+z^2=8t+7\) не имеет целых решений.
По модулю \(8\) каждый квадрат равен \(0,1\) или \(4\). Сумма трёх таких остатков не может дать \(7\): возможные суммы проверяются из \(\{0,1,4\}\), и максимум с остатком \(7\) не появляется. Правая часть равна \(7\pmod8\), противоречие.
Комментарий. Это не полная теорема о трёх квадратах, а нужный для олимпиад частный запрет.
Пример 6. Простые \(3\pmod4\)
Ключевая техника для сумм двух квадратов.
Задача. Пусть \(p\equiv3\pmod4\) - простой и \(p\mid x^2+y^2\). Докажите, что \(p\mid x\) и \(p\mid y\).
Если \(p\nmid y\), то \(xy^{-1}\) существует по модулю \(p\), и из \(x^2+y^2\equiv0\) получаем \((xy^{-1})^2\equiv-1\pmod p\). Тогда \(-1\) является квадратом по модулю \(p\), что возможно только при \(p\equiv1\pmod4\), противоречие. Значит, \(p\mid y\), а затем из исходной делимости следует \(p\mid x\).
Комментарий. Важный шаблон: сначала доказываем, что делить можно, иначе уже получили часть вывода.
Пример 7. Форма \(a^2+ab+b^2\)
Показывает аналог порядка \(3\).
Задача. Пусть \(p\ne3\) - простой, \( \gcd(a,b)=1 \), и \(p\mid a^2+ab+b^2\). Докажите, что \(p\equiv1\pmod3\).
Так как \(p\nmid b\), положим \(t\equiv ab^{-1}\pmod p\). Тогда \(t^2+t+1\equiv0\). Умножая на \(t-1\), получаем \(t^3-1\equiv0\). При этом \(t\not\equiv1\), иначе \(3\equiv0\pmod p\), что невозможно при \(p\ne3\). Значит, порядок \(t\) равен \(3\), поэтому \(3\mid p-1\).
Комментарий. Это важный мост к кубическим остаткам и порядкам.
Пример 8. Бесконечный спуск
Олимпиадный вывод из модульного запрета.
Задача. Докажите, что уравнение \(x^2+y^2=3z^2\) имеет только решение \(x=y=z=0\) в целых числах.
По модулю \(3\) квадраты равны \(0\) или \(1\). Если \(x^2+y^2\) делится на \(3\), то оба квадрата должны делиться на \(3\), значит \(3\mid x\) и \(3\mid y\). Тогда \(9\mid x^2+y^2=3z^2\), поэтому \(3\mid z\). Делим \(x,y,z\) на \(3\) и получаем меньшее решение. Для ненулевого решения это даёт бесконечный спуск, невозможный в натуральных размерах. Значит, ненулевых решений нет.
Комментарий. Важно показать делимость всех трёх переменных, а не только двух.
Глава
Мультипликативный порядок
Ключевая идея
Порядок числа \(a\) по модулю \(m\) - это длина цикла степеней \(a,a^2,a^3,\ldots\) до первого появления \(1\). Если \( \gcd(a,m)=1 \), то порядок помогает заменить огромные степени маленькими остатками и даёт ограничения на простые делители.
Основные факты
Если \(d=\operatorname{ord}_m(a)\), то \(a^k\equiv1\pmod m\) тогда и только тогда, когда \(d\mid k\). Для простого \(p\) порядок любого ненулевого остатка по модулю \(p\) делит \(p-1\). Если \(p\mid a^n-1\), то \( \operatorname{ord}_p(a)\mid n \). Если \(p\mid a^n+1\), то порядок делит \(2n\), но не делит \(n\).
Когда применять метод
Используйте порядок, когда в задаче есть большие степени, делимость вида \(p\mid a^n\pm1\), поиск последних цифр, циклы остатков или ограничения на вид простого делителя.
Как распознать метод
Фразы \(a^n\equiv1\), \(a^n\equiv-1\), \(p\mid a^n-1\), \(p\mid a^n+1\) почти всегда указывают на порядок. Если показатель огромный, сначала найдите длину цикла, а потом берите показатель по модулю этой длины.
Типичные ошибки
Порядок определён только когда \( \gcd(a,m)=1 \). Нельзя утверждать, что порядок равен \(p-1\), если доказано только, что он делит \(p-1\). В задачах с \(a^n+1\) важно отдельно доказать, что порядок не делит \(n\).
Мини-чеклист
1. Взаимно ли просты основание и модуль? 2. Какой минимальный показатель даёт \(1\)? 3. Делит ли порядок нужный показатель? 4. Если есть простой \(p\), какой вывод даёт \(d\mid p-1\)? 5. Проверен ли случай \(p=2\) отдельно?
Пример 1. Первый порядок
Показывает определение на маленьком модуле.
Задача. Найдите \( \operatorname{ord}_7(2) \).
Считаем степени: \(2^1\equiv2\), \(2^2\equiv4\), \(2^3\equiv8\equiv1\pmod7\). Раньше \(1\) не появлялась, значит порядок равен \(3\).
Комментарий. Порядок - это именно первый показатель, а не любой показатель, дающий \(1\).
Пример 2. Большая степень через цикл
Учит уменьшать показатель по модулю порядка.
Задача. Найдите остаток \(2^{100}\) при делении на \(7\).
Из предыдущего примера \(2^3\equiv1\pmod7\). Так как \(100\equiv1\pmod3\), получаем \(2^{100}\equiv2^1\equiv2\pmod7\).
Комментарий. После нахождения порядка большие степени становятся короткими.
Пример 3. Порядок по простому модулю
Показывает, что порядок делит \(p-1\).
Задача. Найдите \( \operatorname{ord}_{11}(3) \).
Имеем \(3^1\equiv3\), \(3^2\equiv9\), \(3^3\equiv27\equiv5\), \(3^4\equiv15\equiv4\), \(3^5\equiv12\equiv1\pmod{11}\). Значит, порядок \(5\), и он действительно делит \(10\).
Комментарий. Это пример к факту \(d\mid p-1\).
Пример 4. Делитель числа \(a^n-1\)
Показывает, как порядок ограничивает простой делитель.
Задача. Пусть простой \(p\mid 2^m-1\). Докажите, что \( \operatorname{ord}_p(2)\mid m \) и \( \operatorname{ord}_p(2)\mid p-1 \).
Из \(p\mid2^m-1\) получаем \(2^m\equiv1\pmod p\), поэтому порядок \(2\) по модулю \(p\) делит \(m\). Так как \(p\) простое и \(2\not\equiv0\pmod p\), порядок также делит \(p-1\).
Комментарий. Отсюда часто получают ограничения на \(p\).
Пример 5. Делитель числа \(a^n+1\)
Учит не забывать условие «не делит \(n\)».
Задача. Пусть \(p\) - нечётный простой делитель \(a^n+1\) и \(p\nmid a\). Что можно сказать о порядке \(a\) по модулю \(p\)?
Имеем \(a^n\equiv-1\pmod p\). Тогда \(a^{2n}\equiv1\), значит порядок делит \(2n\). Но порядок не делит \(n\), иначе было бы \(a^n\equiv1\), противоречие с \(a^n\equiv-1\) при нечётном \(p\).
Комментарий. Это один из главных шаблонов для задач на \(a^n+1\).
Пример 6. Простые делители ферматова типа
Готовит к сильным задачам.
Задача. Пусть простой \(q\mid 2^{16}+1\). Докажите, что \(q\equiv1\pmod{32}\).
Если \(q=2\), то \(2^{16}+1\) нечётно, значит \(q\ne2\). Из \(2^{16}\equiv-1\pmod q\) следует \(2^{32}\equiv1\), но \(2^{16}\not\equiv1\). Порядок числа \(2\) по модулю \(q\) равен \(32\), поэтому \(32\mid q-1\).
Комментарий. Степень \(16=2^4\) заставляет порядок быть ровно \(32\).
Пример 7. Все простые из одного условия
Показывает, как Fermat сокращает задачу.
Задача. Найдите все простые \(p\), для которых \(p\mid2^p+1\).
При \(p=2\) имеем \(2^2+1=5\), не делится на \(2\). Для нечётного \(p\) по малой теореме Ферма \(2^p\equiv2\pmod p\). Тогда условие даёт \(2^p+1\equiv3\equiv0\pmod p\), значит \(p=3\). Проверка: \(2^3+1=9\) делится на \(3\).
Комментарий. Здесь порядок не обязателен, но идея цикла степеней та же.
Пример 8. Ферматовы числа попарно взаимно просты
Олимпиадный пример на порядок и знак \(-1\).
Задача. Докажите, что числа \(F_n=2^{2^n}+1\) попарно взаимно просты.
Пусть \(m
Комментарий. Важно, что один и тот же остаток не может быть одновременно \(1\) и \(-1\) по нечётному модулю.
Глава
Теоремы Вильсона, Ферма и Эйлера в задачах
Ключевая идея
Теоремы Ферма, Эйлера и Вильсона - это не отдельные факты для запоминания, а способы быстро превращать большие степени и факториалы в маленькие остатки. В олимпиадных задачах важно понять, какую теорему можно применить и почему условия выполнены.
Основные факты
Малая теорема Ферма: если \(p\) - простой и \(p\nmid a\), то \(a^{p-1}\equiv1\pmod p\). В форме \(a^p\equiv a\pmod p\) она верна для всех целых \(a\). Теорема Эйлера: если \(\gcd(a,n)=1\), то \(a^{\varphi(n)}\equiv1\pmod n\). Теорема Вильсона: \(p\) простое тогда и только тогда, когда \((p-1)!\equiv-1\pmod p\).
Когда применять метод
Ферма применяют для степеней по простому модулю. Эйлер - для степеней по составному модулю при взаимной простоте. Вильсон - для факториалов по простому модулю, особенно когда в задаче есть \((p-1)!\), \((p-2)!\) или произведение всех ненулевых остатков.
Как распознать метод
Если показатель похож на \(p-1\), \(p\) или кратен \(p-1\), пробуйте Ферма. Если модуль составной и основание взаимно просто с ним, ищите \(\varphi(n)\). Если встречается факториал почти до простого \(p\), пробуйте Вильсона.
Типичные ошибки
Нельзя применять теорему Эйлера без проверки \(\gcd(a,n)=1\). Нельзя заменять \(\varphi(n)\) на \(n-1\), если \(n\) не простое. В теореме Вильсона важно отдельно учитывать простоту модуля: для составных \(n\) сравнение обычно неверно.
Мини-чеклист
1. Модуль простой или составной? 2. Взаимно ли просто основание с модулем? 3. Какой показатель можно уменьшить: \(p-1\) или \(\varphi(n)\)? 4. Можно ли заменить факториал через Вильсона? 5. Проверен ли малый особый случай \(p=2\)?
Пример 1. Ферма в одну строку
Учит уменьшать показатель по модулю \(p-1\).
Задача. Найдите \(2^{2026}\pmod{11}\).
Так как \(11\) простое и \(2^{10}\equiv1\pmod{11}\), уменьшаем показатель: \(2026\equiv6\pmod{10}\). Поэтому \(2^{2026}\equiv2^6=64\equiv9\pmod{11}\).
Комментарий. Проверка взаимной простоты здесь очевидна: \(11\nmid2\).
Пример 2. Эйлер вместо Ферма
Показывает работу с составным модулем.
Задача. Найдите \(2^{100}\pmod9\).
Имеем \(\varphi(9)=6\) и \(\gcd(2,9)=1\). Значит, \(2^6\equiv1\pmod9\). Так как \(100\equiv4\pmod6\), получаем \(2^{100}\equiv2^4=16\equiv7\pmod9\).
Комментарий. Эйлер требует взаимной простоты основания и модуля.
Пример 3. Обратный элемент через Ферма
Показывает, как найти обратный остаток.
Задача. Найдите число, обратное к \(5\) по модулю \(17\).
По Ферма \(5^{16}\equiv1\pmod{17}\), значит \(5^{15}\) является обратным к \(5\). Но проще проверить: \(5\cdot7=35\equiv1\pmod{17}\). Ответ: \(7\).
Комментарий. Теорема даёт существование и общий способ, но малый модуль можно досчитать напрямую.
Пример 4. Вильсон для полного факториала
Первое применение теоремы Вильсона.
Задача. Найдите остаток \(10!\) по модулю \(11\).
Так как \(11\) простое, по теореме Вильсона \(10!\equiv-1\equiv10\pmod{11}\).
Комментарий. Факториал почти до простого сразу указывает на Вильсона.
Пример 5. Неполный факториал
Учит убирать последние множители из Вильсона.
Задача. Найдите \(8!\pmod{11}\).
По Вильсону \(10!\equiv-1\pmod{11}\). Но \(10!=10\cdot9\cdot8!\equiv(-1)(-2)8!\equiv2\cdot8!\pmod{11}\). Значит, \(2\cdot8!\equiv-1\equiv10\), откуда \(8!\equiv5\pmod{11}\).
Комментарий. Неполные факториалы часто восстанавливаются из полного.
Пример 6. Форма \(a^p-a\)
Показывает универсальную форму Ферма.
Задача. Докажите, что \(p\mid a^p-a\) для любого простого \(p\) и любого целого \(a\).
Если \(p\mid a\), утверждение очевидно. Если \(p\nmid a\), то по Ферма \(a^{p-1}\equiv1\pmod p\). Умножая на \(a\), получаем \(a^p\equiv a\pmod p\).
Комментарий. Эта форма удобна, когда \(a\) может делиться на \(p\).
Пример 7. Вильсон и простота
Показывает, как теорема Вильсона распознаёт простые числа.
Задача. Проверьте сравнение \(6!\equiv-1\pmod7\).
Так как \(7\) простое, Вильсон даёт \(6!\equiv-1\pmod7\). Действительно, \(720=7\cdot102+6\), то есть \(6\equiv-1\pmod7\).
Комментарий. Для составного модуля такой вывод делать нельзя.
Пример 8. Смешанная задача
Соединяет Эйлера и остатки.
Задача. Найдите последние две цифры \(3^{80}\).
Работаем по модулю \(100\). Так как \(\gcd(3,100)=1\) и \(\varphi(100)=40\), имеем \(3^{40}\equiv1\pmod{100}\). Поэтому \(3^{80}\equiv1\pmod{100}\). Последние две цифры: \(01\).
Комментарий. Если нужен модуль \(100\), Ферма по простому модулю недостаточно.
Глава
p-адические показатели
Ключевая идея
\(v_p(n)\) - это показатель простого \(p\) в разложении числа \(n\). Вместо того чтобы спрашивать «делится ли число», мы спрашиваем «сколько раз оно делится на \(p\)». Это превращает задачи о степенях простых, факториалах и биномиальных коэффициентах в точные вычисления.
Основные факты
Если \(p\) простое, то \(v_p(ab)=v_p(a)+v_p(b)\), \(v_p(a^k)=k v_p(a)\). Для факториала используется формула Лежандра: \(v_p(n!)=\lfloor n/p \rfloor+\lfloor n/p^2 \rfloor+\lfloor n/p^3 \rfloor+\cdots\). Количество нулей \(n!\) в десятичной записи равно \(v_5(n!)\), потому что двоек больше, чем пятёрок.
Когда применять метод
Valuations нужны, когда спрашивают максимальное \(k\), для которого \(p^k\mid N\), когда есть факториалы, произведения подряд идущих чисел, биномиальные коэффициенты, последние нули или делимость на составное число вида \(2^a3^b5^c\).
Как распознать метод
Слова «наибольшая степень», «сколько нулей», «делится на \(m^k\)», «найдите показатель простого» почти всегда указывают на \(v_p\). Если число составное, разложите его на простые и возьмите минимум по ограничениям.
Типичные ошибки
Нельзя считать только множители, кратные \(p\): множители, кратные \(p^2\), дают дополнительный вклад. В десятичных нулях ограничивает число пятёрок, а не двоек. Для \(m^k\mid N\), где \(m\) составное, нужно учитывать все простые делители \(m\).
Мини-чеклист
1. Какое простое \(p\) важно? 2. Нужно ли разложить модуль на простые? 3. Для факториала применена ли формула Лежандра со всеми степенями \(p\)? 4. Для составного основания взят ли минимум? 5. Проверено ли, что найденная степень действительно максимальна?
Пример 1. Первое вычисление \(v_p\)
Учит читать разложение числа.
Задача. Найдите \(v_2(72)\) и \(v_3(72)\).
Имеем \(72=2^3\cdot3^2\). Поэтому \(v_2(72)=3\), а \(v_3(72)=2\).
Комментарий. Это не количество делителей, а показатель конкретного простого.
Пример 2. Формула Лежандра
Показывает, как считать показатель простого в факториале.
Задача. Найдите \(v_3(100!)\).
По формуле Лежандра \(v_3(100!)=\lfloor100/3\rfloor+\lfloor100/9\rfloor+\lfloor100/27\rfloor+\lfloor100/81\rfloor=33+11+3+1=48\).
Комментарий. Множители, кратные \(9\) и \(27\), дают дополнительные тройки.
Пример 3. Десятичные нули
Связывает valuations с записью числа.
Задача. Сколько нулей в конце числа \(100!\)?
Количество нулей равно числу множителей \(10=2\cdot5\). В факториале двоек больше, поэтому считаем пятёрки: \(v_5(100!)=20+4=24\). Ответ: \(24\).
Комментарий. Для десятичной записи почти всегда ограничивают пятёрки.
Пример 4. Делимость на составную степень
Учит брать минимум по простым делителям.
Задача. Найдите наибольшее \(k\), для которого \(12^k\mid100!\).
Так как \(12=2^2\cdot3\), нужно \(2k\le v_2(100!)\) и \(k\le v_3(100!)\). Имеем \(v_2(100!)=50+25+12+6+3+1=97\), \(v_3(100!)=48\). Поэтому \(k\le48\) по двойкам и \(k\le48\) по тройкам. Ответ: \(48\).
Комментарий. Составное основание всегда раскладываем.
Пример 5. Биномиальный коэффициент
Показывает valuation для дроби с факториалами.
Задача. Найдите \(v_2\left(\binom{16}{6}\right)\).
Используем \(\binom{16}{6}=16!/(6!10!)\). Тогда \(v_2(16!)=8+4+2+1=15\), \(v_2(6!)=3+1=4\), \(v_2(10!)=5+2+1=8\). Значит, \(v_2\left(\binom{16}{6}\right)=15-4-8=3\).
Комментарий. Для биномиальных коэффициентов показатели вычитаются.
Пример 6. Нули в другой базе
Показывает, что база может быть не десятичной.
Задача. Сколько нулей в конце \(100!\) в системе счисления с основанием \(12\)?
Основание \(12=2^2\cdot3\). Нужно найти максимум \(k\), для которого \(12^k\mid100!\). Из примера: \(v_2(100!)=97\), \(v_3(100!)=48\). Значит, \(k=\min(\lfloor97/2\rfloor,48)=48\).
Комментарий. Задача та же, что и про \(12^k\mid100!\), но в другой оболочке.
Пример 7. Почему \(2^n\nmid n!\)
Готовит к доказательным задачам.
Задача. Докажите, что для любого \(n\ge1\) число \(n!\) не делится на \(2^n\).
По формуле Лежандра \(v_2(n!)=\lfloor n/2\rfloor+\lfloor n/4\rfloor+\cdots\). Каждое слагаемое строго меньше соответствующего члена геометрической суммы \(n/2+n/4+\cdots=n\). Поэтому \(v_2(n!)
Комментарий. Оценка суммы floors часто проще точного значения.
Пример 8. Произведение подряд идущих чисел
Олимпиадная идея: доказать делимость через \(v_p\).
Задача. Докажите, что произведение любых \(n\) последовательных целых чисел делится на \(n!\).
Пусть произведение равно \(A=(m+1)(m+2)\cdots(m+n)\). Для любого простого \(p\) нужно доказать \(v_p(A)\ge v_p(n!)\). Среди \(n\) последовательных чисел как минимум \(\lfloor n/p\rfloor\) делятся на \(p\), как минимум \(\lfloor n/p^2\rfloor\) делятся на \(p^2\), и так далее. Поэтому \(v_p(A)\ge\sum_i\lfloor n/p^i\rfloor=v_p(n!)\). Это верно для всех простых \(p\), значит \(n!\mid A\).
Комментарий. Это доказательство эквивалентно целочисленности биномиального коэффициента.
Глава
LTE: поднятие показателя
Ключевая идея
LTE, lifting the exponent, позволяет точно находить показатель простого \(p\) в разности степеней. Метод особенно силён, когда \(p\mid a-b\) или \(p\mid a+b\), а выражение имеет вид \(a^n-b^n\).
Основные факты
Базовая форма: если \(p\) - нечётный простой, \(p\mid a-b\), \(p\nmid ab\), то \(v_p(a^n-b^n)=v_p(a-b)+v_p(n)\). Если \(p\) нечётный, \(p\mid a+b\), \(n\) чётно и \(p\nmid ab\), то \(v_p(a^n-b^n)=v_p(a+b)+v_p(n)\). Для \(p=2\): если \(a,b\) нечётны и \(n\) чётно, то \(v_2(a^n-b^n)=v_2(a-b)+v_2(a+b)+v_2(n)-1\).
Когда применять метод
Применяйте LTE, когда есть \(a^n-b^n\), \(a^n+ b^n\) после преобразования, большие показатели, условия вида \(p^k\mid a^n-b^n\), или нужно найти все \(n\), для которых степень простого достаточно велика.
Как распознать метод
Проверьте, делит ли простой \(p\) число \(a-b\) или \(a+b\). Если да, обычное разложение на множители часто даёт только первый шаг, а LTE сразу даёт точный показатель.
Типичные ошибки
Нельзя применять нечётную формулу к \(p=2\). В случае \(p\mid a+b\) для разности \(a^n-b^n\) нужен чётный \(n\). Также нужно проверять \(p\nmid a\) и \(p\nmid b\), иначе формула может не работать.
Мини-чеклист
1. Какой простой \(p\) считаем? 2. Делит ли он \(a-b\) или \(a+b\)? 3. Чётен ли показатель, если используется \(a+b\)? 4. Не делит ли \(p\) основания? 5. Переведено ли условие \(p^k\mid\) в неравенство для \(v_p\)?
Пример 1. Классическая разность
Первое прямое применение LTE.
Задача. Найдите \(v_3(10^{2025}-1)\).
Так как \(3\mid10-1\), применяем LTE: \(v_3(10^{2025}-1)=v_3(9)+v_3(2025)=2+4=6\).
Комментарий. Без LTE разложение было бы очень длинным.
Пример 2. Делитель \(a+1\)
Показывает случай \(p\mid a+b\).
Задача. Найдите \(v_3(2^{100}-1)\).
Здесь \(3\mid2+1\), показатель \(100\) чётен. Поэтому \(v_3(2^{100}-1)=v_3(2+1)+v_3(100)=1+0=1\).
Комментарий. Важно, что показатель чётен.
Пример 3. Случай \(p=2\)
Отдельная формула для двоек.
Задача. Найдите \(v_2(3^{100}-1)\).
Для нечётных \(3\) и \(1\), при чётном \(100\): \(v_2(3^{100}-1)=v_2(3-1)+v_2(3+1)+v_2(100)-1=1+2+2-1=4\).
Комментарий. Формула для \(2\) отличается от нечётного случая.
Пример 4. Условие на \(n\)
Показывает, как LTE решает делимость.
Задача. Найдите все \(n\), для которых \(7^3\mid8^n-1\).
Так как \(7\mid8-1\), имеем \(v_7(8^n-1)=v_7(7)+v_7(n)=1+v_7(n)\). Нужно \(1+v_7(n)\ge3\), то есть \(v_7(n)\ge2\). Ответ: \(49\mid n\).
Комментарий. Условие на степень простого стало условием на \(n\).
Пример 5. Составная степень
Показывает переход от \(p^k\) к \(v_p\).
Задача. Найдите наибольшее \(k\), для которого \(9^k\mid10^{2025}-1\).
Из примера 1 \(v_3(10^{2025}-1)=6\). Так как \(9^k=3^{2k}\), нужно \(2k\le6\). Ответ: \(k=3\).
Комментарий. Сначала считаем простой показатель, потом учитываем составное основание.
Пример 6. Формула с параметром
Готовит к задачам с ответом через \(v_p(n)\).
Задача. Найдите \(v_5(11^n-1)\).
Так как \(5\mid11-1\), по LTE \(v_5(11^n-1)=v_5(10)+v_5(n)=1+v_5(n)\).
Комментарий. Ответ зависит от показателя \(n\).
Пример 7. Решение неравенства
Учит находить все \(n\).
Задача. Найдите все \(n\), для которых \(7^n\mid8^n-1\).
По LTE \(v_7(8^n-1)=1+v_7(n)\). Требуется \(1+v_7(n)\ge n\). При \(n=1\) условие верно. При \(n\ge2\) имеем \(v_7(n)\le \log_7 n
Комментарий. Последний шаг - сравнить рост \(n\) и \(v_7(n)\).
Пример 8. Степени двойки в \(3^{2^m}-1\)
Олимпиадный шаблон для \(p=2\).
Задача. Докажите, что при \(m\ge1\) выполнено \(v_2(3^{2^m}-1)=m+2\).
Применяем формулу для \(2\): \(v_2(3^{2^m}-1)=v_2(3-1)+v_2(3+1)+v_2(2^m)-1=1+2+m-1=m+2\).
Комментарий. Очень частая подзадача в сильных примерах.
Глава
Диофантовы уравнения I: факторизация и оценки
Ключевая идея
В первых диофантовых задачах важно не угадывать решения, а превращать уравнение в конечный перебор. Обычно это делается через разложение на множители, оценку размеров переменных или условие делимости, которое резко ограничивает возможные значения.
Типичный ход: собрать выражение в произведение, например \(xy+ax+by=c\), затем дописать \(ab\) и получить \((x+b)(y+a)=c+ab\). После этого остаётся разобрать делители фиксированного числа.
Основные факты
1. Если \(uv=N\), где \(u,v\) — положительные целые числа, то вариантов конечное число: достаточно перебрать делители \(N\).
2. Разность квадратов: \(x^2-y^2=(x-y)(x+y)\). У множителей \(x-y\) и \(x+y\) одинаковая чётность.
3. Для уравнений с дробями часто помогает умножить на общий знаменатель и дописать квадрат или произведение: из \(\frac{1}{x}+\frac{1}{y}=\frac{1}{n}\) получается \((x-n)(y-n)=n^2\).
4. Если \(a\mid f(n)\), где \(a\) само зависит от \(n\), полезно заменить \(n\) по модулю \(a\) или вычесть подходящее кратное.
5. Оценки дают начало перебору: если \(x\le y\le z\), то \(\frac{3}{x}\ge \frac{1}{x}+\frac{1}{y}+\frac{1}{z}\).
Когда применять метод
Метод особенно полезен, если в задаче есть произведение \(xy\), разность квадратов, дроби вида \(\frac{1}{x}\), условие делимости или требование найти все целые решения. Он также хорошо работает, когда переменные положительны: тогда можно использовать порядок \(x\le y\le z\) и получать верхние границы.
Как распознать метод
Ищите выражения, которые почти являются произведением: \(xy+ax+by\), \(x^2-y^2\), \(xy-nx-ny\), \(x^2+2x-y^2\). Если после переноса членов появляется “почти факторизация”, попробуйте добавить и вычесть одну константу.
Если прямой факторизации не видно, попробуйте сделать одну переменную главной: выразить \(y\), получить делимость или рассмотреть квадратный трёхчлен с целым дискриминантом.
Типичные ошибки
Не забывайте условия положительности и чётности множителей. При разности квадратов нельзя независимо выбирать любые делители: числа \(x-y\) и \(x+y\) должны иметь одинаковую чётность.
В задачах с дробями нельзя делить на переменную, не отметив, что она не равна нулю. В задачах “найдите все” важно проверить все найденные кандидаты в исходном условии.
Мини-чеклист
1. Перенесены ли все члены так, чтобы увидеть произведение?
2. Можно ли дописать константу и получить \((x+a)(y+b)\)?
3. Есть ли ограничения чётности, порядка или положительности?
4. Если есть делимость, можно ли уменьшить выражение по модулю делителя?
5. После перебора делителей проверены ли все кандидаты?
Пример 1. Дополнение до произведения
Этот пример показывает самый базовый приём: из смешанных членов сделать произведение двух скобок.
Задача. Найдите все положительные целые решения уравнения \(xy+3x+2y=29\).
Добавим \(6\) к обеим частям:
\[xy+3x+2y+6=35,\quad (x+2)(y+3)=35.\]
Так как \(x,y>0\), имеем \(x+2\ge 3\), \(y+3\ge 4\). Разложения \(35\) на два положительных множителя дают пары \((5,7)\) и \((7,5)\). Отсюда получаем \((x,y)=(3,4)\) и \((5,2)\).
Комментарий. Константа \(6\) появилась как произведение коэффициентов при \(x\) и \(y\).
Пример 2. Дроби превращаются в делители
Задачи с \(\frac{1}{x}\) часто становятся задачами о делителях после умножения на общий знаменатель.
Задача. Найдите все положительные целые пары \((x,y)\), для которых \(\frac{1}{x}+\frac{1}{y}=\frac{1}{7}\).
Умножим на \(7xy\): \(7x+7y=xy\). Тогда
\[xy-7x-7y=0,\quad (x-7)(y-7)=49.\]
Значит \(x=7+d\), \(y=7+\frac{49}{d}\), где \(d\mid 49\). Получаем упорядоченные пары \((8,56)\), \((14,14)\), \((56,8)\).
Пример 3. Разность квадратов
Здесь важно не забыть, что множители \(x-y\) и \(x+y\) должны иметь одинаковую чётность.
Задача. Найдите все положительные \(x>y\), для которых \(x^2-y^2=56\).
Пишем \((x-y)(x+y)=56\). Оба множителя одной чётности, значит оба чётные. Подходящие пары множителей: \((2,28)\) и \((4,14)\). Они дают \(x=15,y=13\) и \(x=9,y=5\).
Пример 4. Делимость с переменным делителем
Если делитель содержит \(n\), полезно заменить \(n\) на удобный остаток по этому делителю.
Задача. Найдите все положительные \(n\), такие что \(n+4\mid n^2+5\).
По модулю \(n+4\) имеем \(n\equiv -4\), значит \(n^2+5\equiv 16+5=21\). Поэтому \(n+4\mid 21\). Так как \(n+4>4\), возможны \(n+4=7\) или \(21\). Получаем \(n=3\) и \(n=17\), и оба значения подходят.
Пример 5. Скрытое произведение после умножения
Иногда факторизация появляется не сразу, а после умножения на произведение переменных.
Задача. Найдите все положительные \(x,y\), если \(\frac{1}{x}+\frac{1}{y}+\frac{2}{xy}=\frac{1}{5}\).
Умножаем на \(5xy\): \(5x+5y+10=xy\). Тогда
\[xy-5x-5y=10,\quad (x-5)(y-5)=35.\]
Перебирая делители \(35\), получаем \((x,y)=(6,40),(10,12),(12,10),(40,6)\).
Пример 6. Оценка перед перебором
Перед факторизацией часто надо понять, какие значения вообще возможны.
Задача. Найдите все \(x\le y\le z\), если \(\frac{1}{x}+\frac{1}{y}+\frac{1}{z}=1\).
Так как \(x\le y\le z\), то \(\frac{3}{x}\ge 1\), поэтому \(x\le 3\). Значения \(x=1\) и \(x=2\) быстро проверяются: при \(x=1\) остальные дроби должны суммироваться в \(0\), а при \(x=2\) получаем \(\frac{1}{y}+\frac{1}{z}=\frac{1}{2}\), откуда \((y-2)(z-2)=4\), то есть \((y,z)=(3,6),(4,4)\). При \(x=3\) получаем \(\frac{1}{y}+\frac{1}{z}=\frac{2}{3}\), и с учётом \(y\ge 3\) единственно \(y=z=3\). Ответ: \((2,3,6),(2,4,4),(3,3,3)\).
Пример 7. Геометрическая формула как диофантово уравнение
Даже задача про пифагоровы тройки может решаться простой факторизацией, если дана сумма сторон.
Задача. Найдите прямоугольные треугольники с целыми сторонами и периметром \(40\).
Пусть катеты \(x,y\), гипотенуза \(40-x-y\). Тогда
\[x^2+y^2=(40-x-y)^2.\]
После сокращения получаем \(xy-40x-40y+800=0\), то есть \((x-40)(y-40)=800\). Так как \(x,y<40\), положим \(a=40-x\), \(b=40-y\). Тогда \(ab=800\) и гипотенуза равна \(a+b-40\). Подходят \(a=32,b=25\) и перестановка, откуда стороны \(8,15,17\).
Пример 8. Конструкция через интервалы
В сильных задачах факторизация может сочетаться с идеей “закрыть” все простые числа подходящим отрезком последовательных чисел.
Задача. Для чётного \(m>2\) постройте \(m\) последовательных чисел, произведение которых делится на каждое простое \(p\le 2m+1\).
Если \(m+1\) составное, берём числа \(m+2,m+3,\ldots,2m+1\). Простые \(p\le m\) делят произведение любых \(m\) последовательных чисел, а простые от \(m+2\) до \(2m+1\) входят в произведение как сами числа. Число \(m+1\) не надо покрывать как простое.
Если \(m+1\) простое, берём \(m+3,m+4,\ldots,2m+2\). Простые \(p\le m\) снова покрыты блоком длины \(m\); простое \(m+1\) делит \(2m+2\); число \(m+2\) чётно и больше \(2\), поэтому не является простым.
Глава
Диофантовы уравнения II: спуск и прыжок Виета
Ключевая идея
Бесконечный спуск доказывает невозможность так: если существует решение, то существует меньшее решение того же типа. Повторяя шаг, мы получили бы бесконечно убывающую последовательность положительных целых чисел, что невозможно.
Прыжок Виета — это спуск для квадратного уравнения. Если уравнение симметрично по \(x,y\), фиксируем \(x\) и смотрим на него как на квадратное относительно \(y\). Второй корень часто оказывается положительным целым числом меньше исходного.
Основные факты
1. Если в минимальном решении все переменные делятся на \(d>1\), то после деления получается меньшее решение; это противоречие.
2. Если \(y\) — корень квадратного уравнения \(Y^2-mxY+x^2+c=0\), то второй корень равен \(mx-y\), а произведение корней равно \(x^2+c\).
3. Чтобы прыжок Виета был законным, надо проверить три вещи: второй корень целый, положительный и действительно меньше.
4. В задачах с \(x^2+y^2\) часто используются простые \(p\equiv 3\pmod 4\): если \(p\mid x^2+y^2\), то обычно \(p\mid x\) и \(p\mid y\).
Когда применять метод
Спуск стоит пробовать, когда из сравнения по модулю следует, что все переменные имеют общий делитель. Прыжок Виета стоит пробовать, когда уравнение похоже на \(x^2+y^2+c=mxy\) или на симметричное квадратное уравнение по одной переменной.
Как распознать метод
Признаки спуска: фраза “докажите, что решений нет”, однородное уравнение, степени, простое \(p\equiv 3\pmod 4\), или ситуация, где из решения можно вынести общий множитель.
Признаки прыжка Виета: уравнение симметрично, имеет квадратные члены, и после фиксации одной переменной второй корень выражается простой формулой.
Типичные ошибки
Нельзя просто сказать “получим меньшее решение”: надо указать, какая положительная величина уменьшается. В прыжке Виета часто забывают доказать положительность второго корня.
Ещё одна ошибка — применять спуск к неоднородному уравнению после деления без проверки, что уравнение сохраняет тот же вид.
Мини-чеклист
1. Что именно минимизируем: сумму, максимум или одну переменную?
2. Почему из решения получается новое целое решение?
3. Почему новое решение положительное?
4. Почему оно меньше?
5. Какие базовые случаи останавливают спуск?
Пример 1. Классический спуск
Идея: из решения построить меньшее решение того же уравнения.
Задача. Докажите, что \(x^2=2y^2\) не имеет решений в положительных целых числах.
Предположим, что решение есть, и выберем его с наименьшим \(x+y\). Из \(x^2=2y^2\) следует, что \(x\) чётно: \(x=2u\). Тогда \(4u^2=2y^2\), то есть \(y^2=2u^2\), значит \(y\) тоже чётно: \(y=2v\). Получаем \(u^2=2v^2\), то есть новое положительное решение \((u,v)\) с меньшей суммой. Противоречие.
Пример 2. Спуск через модуль \(3\)
Квадраты по модулю \(3\) равны \(0\) или \(1\).
Задача. Докажите, что \(x^2+y^2=3z^2\) не имеет ненулевых целых решений.
По модулю \(3\) имеем \(x^2+y^2\equiv 0\). Это возможно только если \(x\equiv y\equiv 0\pmod 3\). Тогда левая часть делится на \(9\), значит \(3z^2\) делится на \(9\), то есть \(z\) делится на \(3\). Делим все переменные на \(3\) и получаем меньшее решение. Бесконечный спуск невозможен.
Пример 3. Второй корень
Прыжок Виета начинается с того, что один корень уже известен.
Задача. Пусть \(x,y\) — положительные целые числа и \(x^2+y^2+1=4xy\). Докажите, что это невозможно.
Выберем решение с минимальной суммой и пусть \(x\le y\). Рассмотрим уравнение как квадратное относительно \(y\): \(Y^2-4xY+x^2+1=0\). Второй корень равен \(y'=4x-y\), а произведение корней равно \(x^2+1\), значит \(y'=\frac{x^2+1}{y}>0\) и целое. Так как \(y\ge x\), имеем \(y'\le x+\frac{1}{x}\), значит \(y'\le x\). Равенство \(y'=x\) невозможно, иначе \(y=3x\) и уравнение даёт \(2x^2=1\). Поэтому \(0
Пример 4. Уравнение с настоящими решениями
Прыжок Виета не всегда доказывает невозможность; иногда он описывает все решения.
Задача. Опишите решения \(x^2+y^2+1=3xy\).
Пусть \(x\le y\). Второй корень относительно \(y\) равен \(y'=3x-y=\frac{x^2+1}{y}\). Если \(x>1\), то \(0
Пример 5. Прыжок в уравнении Маркова
Для трёх переменных прыжок делается по наибольшей переменной.
Задача. Если \(x^2+y^2+z^2=3xyz\), покажите, что замена \(z\) на \(z'=3xy-z\) снова даёт решение.
Считаем уравнение квадратным относительно \(z\): \(Z^2-3xyZ+x^2+y^2=0\). Сумма корней равна \(3xy\), поэтому второй корень \(z'=3xy-z\). По формулам Виета он целый и удовлетворяет тому же уравнению вместе с \(x,y\).
Пример 6. Простые \(3 \pmod 4\)
Такой простой не может делить сумму двух квадратов “наполовину”.
Задача. Пусть \(p\equiv 3\pmod 4\) — простое и \(p\mid x^2+y^2\). Докажите, что \(p\mid x\) и \(p\mid y\).
Если, например, \(p\nmid y\), то существует обратный элемент к \(y\) по модулю \(p\), и \((xy^{-1})^2\equiv -1\pmod p\). Возведём в степень \(\frac{p-1}{2}\). Слева получим \(1\), а справа \((-1)^{(p-1)/2}=-1\), потому что \(p\equiv 3\pmod 4\). Противоречие. Значит \(p\mid y\), и тогда из делимости следует \(p\mid x\).
Пример 7. Степени и спуск
Если уравнение однородное, деление на общий множитель сохраняет форму.
Задача. Докажите, что \(x^4+y^4=3z^4\) не имеет ненулевых целых решений.
Четвёртая степень по модулю \(3\) равна \(0\) или \(1\). Из \(x^4+y^4\equiv 0\pmod 3\) следует, что \(x\) и \(y\) делятся на \(3\). Тогда левая часть делится на \(81\), значит \(3z^4\) делится на \(81\), и \(z\) делится на \(3\). Делим \(x,y,z\) на \(3\) и получаем меньшее решение того же уравнения. Это невозможно.
Пример 8. Базовые случаи
В спуске важно не потерять начальные решения.
Задача. Опишите положительные решения \(x^2+y^2+3=4xy\).
При \(x=1\) получаем \((y-2)^2=0\), то есть базовое решение \((1,2)\). Для \(x\le y\) и \(x\ge 4\) второй корень \(y'=4x-y=\frac{x^2+3}{y}\) положителен и меньше \(x\). Случаи \(x=2,3\) проверяются отдельно: \(x=2\) даёт \(y=1\) или \(7\), а \(x=3\) не даёт целых \(y\). Поэтому все решения строятся из \((1,2)\) обратным ходом: последовательность \(1,2,7,26,\ldots\), где \(a_{n+1}=4a_n-a_{n-1}\), даёт все соседние пары.
Глава
Китайская теорема об остатках и построения
Ключевая идея
Китайская теорема об остатках превращает несколько локальных условий в одно число. В олимпиадных задачах это не только способ “решить систему”, но и язык построений: мы заранее назначаем остатки так, чтобы нужные делимости стали автоматическими.
Главный принцип: если модули попарно взаимно просты, то систему \(x\equiv r_i\pmod {m_i}\) можно решить, и решение единственно по модулю \(M=m_1m_2\cdots m_k\).
Основные факты
1. Если \(\gcd(m,n)=1\), то система \(x\equiv a\pmod m\), \(x\equiv b\pmod n\) имеет единственное решение по модулю \(mn\).
2. Если модули не взаимно просты, система \(x\equiv a\pmod m\), \(x\equiv b\pmod n\) совместна тогда и только тогда, когда \(\gcd(m,n)\mid a-b\).
3. При попарно взаимно простых модулях количество решений сравнения можно перемножать: например, число решений \(x^2\equiv 1\pmod {mn}\) равно произведению чисел решений по модулям \(m\) и \(n\).
4. Для построений часто выбирают простые \(p_i\) и задают \(N+i\equiv 0\pmod {p_i}\). Тогда каждое \(N+i\) получает заранее назначенный делитель.
Когда применять метод
CRT стоит применять, когда в задаче нужно построить число с несколькими остатками, доказать существование бесконечно многих чисел, найти совместимость условий или организовать делимость нескольких выражений \(N+a_i\).
Как распознать метод
Сигналы метода: “найдите число, которое даёт остатки...”, “постройте \(n\), чтобы \(n+i\) делилось на...”, “докажите существование бесконечно многих”, “система сравнений”, “одновременно по нескольким модулям”.
Типичные ошибки
Нельзя применять стандартную форму CRT, не проверив взаимную простоту модулей. Если модули имеют общий делитель, нужно проверить согласованность остатков.
В задачах на составность недостаточно получить \(p_i\mid N+i\): надо ещё убедиться, что \(N+i>p_i\), иначе число может оказаться равным своему делителю.
Мини-чеклист
1. Какие модули участвуют и попарно ли они взаимно просты?
2. Если модули не взаимно просты, согласованы ли остатки?
3. По какому модулю единственно решение?
4. Если строится составное число, больше ли оно назначенного делителя?
5. Нужно одно число или бесконечно много? Если бесконечно много, добавьте период \(M\).
Пример 1. Два взаимно простых модуля
Базовый расчёт CRT лучше делать вручную, чтобы видеть период.
Задача. Найдите все \(x\), для которых \(x\equiv 2\pmod 5\) и \(x\equiv 3\pmod 7\).
Пусть \(x=5t+2\). Тогда \(5t+2\equiv 3\pmod 7\), то есть \(5t\equiv 1\pmod 7\). Так как \(5^{-1}\equiv 3\pmod 7\), получаем \(t\equiv 3\pmod 7\). Значит \(x=5(7s+3)+2=35s+17\). Ответ: \(x\equiv 17\pmod {35}\).
Пример 2. Несовместимые остатки
Если модули не взаимно просты, сначала проверяется общий делитель.
Задача. Имеет ли решения система \(x\equiv 2\pmod 6\), \(x\equiv 5\pmod 9\)?
Общий делитель модулей равен \(3\). Разность остатков \(5-2=3\) делится на \(3\), значит система совместна. Пусть \(x=6t+2\). Тогда \(6t+2\equiv 5\pmod 9\), то есть \(6t\equiv 3\pmod 9\), или \(2t\equiv 1\pmod 3\). Значит \(t\equiv 2\pmod 3\), и \(x\equiv 14\pmod {18}\).
Пример 3. Назначенные делители
CRT удобно строит числа с заранее заданными делителями.
Задача. Постройте \(N\), для которого \(N+1\) делится на \(3\), \(N+2\) делится на \(5\), \(N+3\) делится на \(7\).
Нужно \(N\equiv -1\pmod 3\), \(N\equiv -2\pmod 5\), \(N\equiv -3\pmod 7\), то есть \(N\equiv 2\pmod 3\), \(N\equiv 3\pmod 5\), \(N\equiv 4\pmod 7\). Решая последовательно, получаем \(N\equiv 53\pmod {105}\). Например, \(N=53\).
Пример 4. Блок составных чисел
Чтобы число было составным, назначенный делитель должен быть меньше самого числа.
Задача. Докажите, что существуют \(6\) последовательных составных чисел.
Возьмём \(N=7!-1\). Тогда \(N+2,N+3,\ldots,N+7\) делятся соответственно на \(2,3,\ldots,7\). При этом все эти числа больше своих делителей, значит они составные. Получен блок из \(6\) последовательных составных чисел.
Пример 5. Подсчёт через CRT
Когда модули взаимно просты, решения по разным модулям можно комбинировать независимо.
Задача. Сколько решений имеет \(x^2\equiv 1\pmod {105}\)?
Так как \(105=3\cdot 5\cdot 7\), нужно решить \(x^2\equiv 1\) по модулям \(3,5,7\). По каждому нечётному простому модулю есть два решения: \(x\equiv \pm 1\). Поэтому всего \(2\cdot 2\cdot 2=8\) решений по модулю \(105\).
Пример 6. Линейное выражение
Иногда сначала надо перевести условие на выражение в условие на \(n\).
Задача. Найдите все \(n\), для которых \(2n+1\equiv 0\pmod 5\) и \(3n-1\equiv 0\pmod 7\).
Первое сравнение даёт \(2n\equiv -1\equiv 4\pmod 5\), значит \(n\equiv 2\pmod 5\). Второе даёт \(3n\equiv 1\pmod 7\), значит \(n\equiv 5\pmod 7\). Решая систему, получаем \(n\equiv 12\pmod {35}\).
Пример 7. Доказательство совместимости
Теорема для двух не взаимно простых модулей часто спасает от лишнего перебора.
Задача. Докажите, что \(x\equiv a\pmod m\), \(x\equiv b\pmod n\) совместна тогда и только тогда, когда \(\gcd(m,n)\mid a-b\).
Если решение \(x\) есть, то \(x-a\) делится на \(m\), а \(x-b\) делится на \(n\). Значит \(a-b=(x-b)-(x-a)\) делится на \(d=\gcd(m,n)\). Обратно, пусть \(d\mid a-b\). Запишем \(m=dm_1\), \(n=dn_1\), где \(\gcd(m_1,n_1)=1\). Нужно найти \(x=a+mt\), чтобы \(a+mt\equiv b\pmod n\), то есть \(m_1t\equiv \frac{b-a}{d}\pmod {n_1}\). Так как \(m_1\) обратим по модулю \(n_1\), такое \(t\) существует.
Пример 8. Бесконечно много построений
После нахождения одного решения можно добавлять общий период.
Задача. Докажите, что существует бесконечно много \(N\), для которых \(N,N+2,N+6\) составные.
Зададим \(N\equiv 0\pmod 5\), \(N+2\equiv 0\pmod 7\), \(N+6\equiv 0\pmod {11}\). Модули взаимно просты, поэтому есть решение по модулю \(385\), и все числа \(N+385t\) тоже подходят по делимости. При достаточно больших \(t\) каждое из чисел больше назначенного делителя, значит все три составные. Таких \(t\) бесконечно много.
Глава
Арифметические функции
Ключевая идея
Арифметические функции переводят структуру разложения числа на простые множители в вычисляемые величины: количество делителей \(\tau(n)\), сумму делителей \(\sigma(n)\), функцию Эйлера \(\varphi(n)\), число различных простых делителей \(\omega(n)\).
Олимпиадная сила этих функций в том, что они часто превращают задачу о числе \(n\) в задачу о показателях в разложении \(n=p_1^{a_1}\cdots p_r^{a_r}\).
Основные факты
Если \(n=p_1^{a_1}\cdots p_r^{a_r}\), то \(\tau(n)=(a_1+1)\cdots(a_r+1)\).
\[\sigma(n)=\prod_{i=1}^{r}\frac{p_i^{a_i+1}-1}{p_i-1}.\]
\[\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right).\]
Функции \(\tau,\sigma,\varphi\) мультипликативны: если \(\gcd(a,b)=1\), то \(f(ab)=f(a)f(b)\) для каждой из них.
Классическая сумма: \(\sum_{d\mid n}\varphi(d)=n\).
Когда применять метод
Используйте арифметические функции, когда в задаче говорится о количестве делителей, сумме делителей, взаимной простоте с \(n\), совершенных/избыточных числах, или требуется найти все \(n\), удовлетворяющие условию вида \(\varphi(n)=cn\), \(\tau(n)=k\), \(\sigma(n)\) нечётна.
Как распознать метод
Если условие зависит только от делителей числа или от простых множителей, почти всегда надо записать каноническое разложение \(n\). Если встречается \(\varphi(n)/n\), смотрите только на множество простых делителей, а не на показатели.
Типичные ошибки
Не путайте мультипликативность с полной мультипликативностью: обычно \(f(ab)=f(a)f(b)\) верно только при \(\gcd(a,b)=1\).
В задачах на \(\sigma(n)\) важно помнить, что \(\sigma(p^a)=1+p+\cdots+p^a\), а не просто \(p^a+1\). В задачах на \(\varphi(n)\) показатели простых влияют на множитель \(n\), но отношение \(n/\varphi(n)\) зависит только от разных простых.
Мини-чеклист
1. Записано ли \(n\) в виде произведения простых степеней?
2. Нужна ли формула для \(\tau\), \(\sigma\) или \(\varphi\)?
3. Можно ли использовать мультипликативность?
4. Если надо “найти все”, какие простые множители вообще могут входить?
5. Проверены ли малые случаи \(n=1,2\)?
Пример 1. Вычисление по разложению
Сначала надо разложить число на простые степени.
Задача. Найдите \(\tau(360)\), \(\sigma(360)\), \(\varphi(360)\).
\(360=2^3\cdot 3^2\cdot 5\). Тогда \(\tau(360)=4\cdot 3\cdot 2=24\). Далее \(\sigma(360)=(1+2+4+8)(1+3+9)(1+5)=15\cdot 13\cdot 6=1170\). Наконец \(\varphi(360)=360\left(1-\frac12\right)\left(1-\frac13\right)\left(1-\frac15\right)=96\).
Пример 2. Мультипликативность \(\tau\)
Делитель произведения взаимно простых чисел единственным образом распадается на два делителя.
Задача. Докажите, что если \(\gcd(a,b)=1\), то \(\tau(ab)=\tau(a)\tau(b)\).
Каждый делитель \(d\mid ab\) единственным образом записывается как \(d=d_1d_2\), где \(d_1\mid a\), \(d_2\mid b\). Обратно, любая такая пара даёт делитель \(ab\). Поэтому число делителей равно числу пар \((d_1,d_2)\), то есть \(\tau(a)\tau(b)\).
Пример 3. Сумма значений \(\varphi\)
Идентичность \(\sum_{d\mid n}\varphi(d)=n\) лучше понимать через порядок дробей.
Задача. Докажите, что \(\sum_{d\mid n}\varphi(d)=n\).
Разобьём числа \(1,2,\ldots,n\) по значению \(d=\frac{n}{\gcd(k,n)}\). Тогда \(d\mid n\), и после деления на \(\gcd(k,n)\) число \(k\) даёт остаток, взаимно простой с \(d\). Для фиксированного \(d\) таких \(k\) ровно \(\varphi(d)\). Все \(n\) чисел учтены, значит сумма равна \(n\).
Пример 4. Когда \(\varphi(n)=n/2\)
Отношение \(n/\varphi(n)\) зависит только от разных простых делителей.
Задача. Найдите все \(n\), для которых \(\varphi(n)=\frac{n}{2}\).
Условие эквивалентно \(\frac{n}{\varphi(n)}=2\). Но \(\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{p}{p-1}\). Если есть нечётный простой \(p\mid n\), произведение получает множитель с нечётным числителем и чётным знаменателем, и становится больше \(2\) или не равно \(2\). Единственный возможный простой делитель — \(2\). Поэтому \(n=2^a\), \(a\ge 1\), и все такие \(n\) подходят.
Пример 5. Нечётное число делителей
Делители обычно разбиваются на пары \(d\) и \(n/d\).
Задача. Докажите, что \(\tau(n)\) нечётно тогда и только тогда, когда \(n\) — квадрат.
Если \(d\ne n/d\), делители \(d\) и \(n/d\) образуют пару. Непарный делитель возможен только при \(d=n/d\), то есть \(d^2=n\). Значит нечётное число делителей бывает ровно у квадратов.
Пример 6. Все числа с 12 делителями
Задача сводится к разложениям числа \(12\) на множители \(a_i+1\).
Задача. Опишите все \(n\), для которых \(\tau(n)=12\).
Если \(n=\prod p_i^{a_i}\), то \(\prod(a_i+1)=12\). Возможны типы показателей: \(11\); \(5,1\); \(3,2\); \(2,1,1\). Поэтому \(n\) имеет один из видов \(p^{11}\), \(p^5q\), \(p^3q^2\), \(p^2qr\), где \(p,q,r\) — различные простые.
Пример 7. Сумма взаимно простых остатков
Остатки, взаимно простые с \(n\), разбиваются на пары \(a\) и \(n-a\).
Задача. Докажите, что при \(n>1\) сумма положительных чисел \(a\le n\), взаимно простых с \(n\), равна \(\frac{n\varphi(n)}{2}\).
Если \(\gcd(a,n)=1\), то \(\gcd(n-a,n)=1\). Пары \(a\) и \(n-a\) имеют сумму \(n\). Самопарного остатка быть не может: \(a=n-a\) дало бы \(2a=n\), но тогда \(\gcd(a,n)>1\) при \(n>2\), а \(n=2\) проверяется отдельно. Всего остатков \(\varphi(n)\), значит сумма равна \(\frac{n\varphi(n)}{2}\).
Пример 8. Составные числа и \(\sigma\)
Иногда достаточно взять несколько очевидных делителей.
Задача. Докажите, что если \(n\) составное, то \(\sigma(n)>n+\sqrt{n}\).
Пусть \(d\) — наименьший делитель \(n\), больший \(1\). Тогда \(d\le \sqrt{n}\), а \(\frac{n}{d}\ge \sqrt{n}\). Среди делителей есть \(1,n,d,\frac{n}{d}\). Поэтому \(\sigma(n)\ge n+1+d+\frac{n}{d}>n+\sqrt{n}\).
Глава
Цифры, системы счисления и десятичные периоды
Ключевая идея
Цифры числа — это коэффициенты при степенях основания. Если заменить основание подходящим остатком, запись числа превращается в сравнение: для \(b-1\) основание \(b\) равно \(1\), для \(b+1\) оно равно \(-1\), для \(10^k-1\) блок из \(k\) цифр снова ведёт себя как один разряд.
Десятичные периоды устроены так же: если \((n,10)=1\), длина периода дроби с знаменателем \(n\) равна порядку числа \(10\) по модулю \(n\).
Основные факты
- Если \(N=\overline{a_ra_{r-1}\ldots a_0}_b\), то \(N=a_rb^r+\cdots+a_1b+a_0\).
- \(N\equiv a_0+a_1+\cdots+a_r \pmod{b-1}\).
- \(N\equiv a_0-a_1+a_2-\cdots+(-1)^r a_r \pmod{b+1}\).
- Последние \(k\) десятичных цифр определяют число по модулю \(10^k\).
- Если \((n,10)=1\), период дроби \(\frac{a}{n}\) равен наименьшему \(h>0\), для которого \(10^h\equiv1\pmod n\).
- Репьюнит \(R_m=11\ldots1=\frac{10^m-1}{9}\) часто сводит задачу к делимости \(10^m-1\).
Когда применять метод
Метод полезен, когда в задаче есть сумма цифр, последняя цифра, последние несколько цифр, палиндром, повторяющийся блок, запись в основании \(b\), период десятичной дроби или число вида \(111\ldots111\).
Как распознать метод
Сигналы: в условии важна не величина числа, а его запись; число разбито на блоки; требуется доказать делимость числа с повторяющимися цифрами; дробь записана как \(0.\overline{a_1a_2\ldots a_r}\); нужно найти период или построить последние цифры квадрата.
Типичные ошибки
- Путать число \(\overline{abc}\) с произведением \(abc\).
- Забывать, что в блоках могут быть ведущие нули.
- Использовать период дроби, не проверив условие \((n,10)=1\).
- Делить сравнение на \(9\), когда модуль не взаимно прост с \(9\).
- Считать признак по сумме цифр полноценным доказательством, не записав сравнение степеней основания.
Мини-чеклист
- Запишите число как сумму цифр, умноженных на степени основания.
- Выберите модуль: \(b-1\), \(b+1\), \(10^k\), \(10^k-1\) или знаменатель периода.
- Замените основание на удобный остаток.
- Для периода найдите порядок \(10\) по модулю знаменателя.
- Для построений последних цифр используйте китайскую теорему об остатках.
Пример 1. Сумма цифр как сравнение
Базовый приём: не помнить признак делимости, а выводить его из записи числа.
Задача. Пусть \(N=\overline{a_ra_{r-1}\ldots a_0}_{10}\). Докажите, что \(N\equiv a_0+a_1+\cdots+a_r\pmod9\).
Имеем \(N=a_r10^r+\cdots+a_1\cdot10+a_0\). Так как \(10\equiv1\pmod9\), то \(10^i\equiv1\pmod9\) для всех \(i\). Поэтому \(N\equiv a_r+\cdots+a_1+a_0\pmod9\).
Комментарий. В олимпиадных задачах важно именно сравнение \(10\equiv1\), а не готовый школьный признак.
Пример 2. Признак делимости на 11
Здесь основание заменяется на \(-1\).
Задача. Докажите, что число \(N=\overline{a_ra_{r-1}\ldots a_0}_{10}\) делится на \(11\) тогда и только тогда, когда \(a_0-a_1+a_2-\cdots+(-1)^r a_r\) делится на \(11\).
Поскольку \(10\equiv-1\pmod{11}\), получаем \(10^i\equiv(-1)^i\pmod{11}\). Подставляя это в разложение числа по степеням \(10\), получаем нужное сравнение.
Комментарий. Чередующаяся сумма — это не фокус с цифрами, а обычная замена \(10\) на \(-1\).
Пример 3. Делимость репьюнитов
Репьюниты лучше рассматривать как \(\frac{10^n-1}{9}\).
Задача. Докажите, что \(R_m\mid R_n\), где \(R_t=\frac{10^t-1}{9}\), тогда и только тогда, когда \(m\mid n\).
Если \(m\mid n\), то \(10^m-1\mid10^n-1\), значит \(R_m\mid R_n\).
Обратно пусть \(R_m\mid R_n\). Тогда \(10^m-1=9R_m\) делит \(9R_n=10^n-1\). Запишем \(n=qm+r\), \(0\le r
Комментарий. Этот пример часто открывает задачи про числа \(111\ldots111\).
Пример 4. Когда репьюнит может быть простым
Первое скрытое наблюдение: составной показатель даёт факторизацию.
Задача. Пусть число из \(k\) единиц является простым. Докажите, что \(k\) простое.
Если \(k=ab\), где \(a,b>1\), то
\[R_k=1+10+\cdots+10^{ab-1}=R_a\left(1+10^a+10^{2a}+\cdots+10^{a(b-1)}\right).\]
Оба множителя больше \(1\), поэтому \(R_k\) составно. Значит, показатель \(k\) не может быть составным.
Комментарий. Мы не доказываем обратное: из простоты \(k\) не следует простота \(R_k\).
Пример 5. Период дроби как порядок
Стандартный переход от десятичной записи к сравнению.
Задача. Пусть \((n,10)=1\). Докажите, что длина периода дроби \(\frac{a}{n}\) равна наименьшему \(h>0\), для которого \(10^h\equiv1\pmod n\).
При делении в столбик остатки после сдвига запятой умножаются на \(10\) по модулю \(n\). Период длины \(h\) означает, что через \(h\) шагов остаток стал тем же: \(a10^h\equiv a\pmod n\). После сокращения на общий делитель с \(n\) это даёт условие \(10^h\equiv1\pmod n\) для знаменателя в несократимой дроби.
Комментарий. В задачах удобнее говорить не о цифрах периода, а о порядке числа \(10\).
Пример 6. Периоды \(1/7\), \(1/13\), \(1/37\)
Пример показывает, что период ищется через степени \(10\).
Задача. Найдите длины периодов дробей \(\frac17\), \(\frac1{13}\), \(\frac1{37}\).
Для \(7\): \(10\equiv3\), \(10^2\equiv2\), \(10^3\equiv6\), \(10^6\equiv1\pmod7\), меньшей положительной степени нет, период равен \(6\).
Для \(13\): \(10^3\equiv-1\pmod{13}\), значит \(10^6\equiv1\), а меньшей степени \(1\) нет; период равен \(6\).
Для \(37\): \(10^3=1000\equiv1\pmod{37}\), а \(10\not\equiv1\), \(10^2\not\equiv1\), поэтому период равен \(3\).
Комментарий. Период дроби — это не вычисление десятичной записи, а вычисление порядка.
Пример 7. Последние цифры через CRT
Задачи о последних цифрах часто разделяются на модули \(2^k\) и \(5^k\).
Задача. Найдите все остатки \(x\pmod{100}\), для которых \(x^2\equiv x\pmod{100}\).
Условие равносильно \(x(x-1)\equiv0\pmod{100}\). Так как \(100=4\cdot25\), нужно решить систему: \(x\equiv0\) или \(1\pmod4\), и \(x\equiv0\) или \(1\pmod{25}\). Четыре сочетания дают \(0\), \(1\), \(25\), \(76\) по модулю \(100\).
Комментарий. Так появляются числа, квадрат которых заканчивается теми же цифрами.
Пример 8. Блоки по \(k\) цифр
Этот приём нужен в сильных задачах на сумму цифр.
Задача. Пусть число \(M\) кратно \(10^k-1\). Докажите, что сумма его десятичных цифр не меньше \(9k\).
Разобьём \(M\) справа налево на блоки по \(k\) цифр и сложим эти блоки как обычные числа. Полученное число \(T\) сравнимо с \(M\) по модулю \(10^k-1\), потому что \(10^k\equiv1\pmod{10^k-1}\). Кроме того, сумма цифр \(T\) не превосходит суммы цифр \(M\).
Повторяя операцию, получим положительное число меньше \(10^k\), всё ещё кратное \(10^k-1\). Это может быть только \(10^k-1\), сумма цифр которого равна \(9k\). Значит, исходная сумма цифр была не меньше \(9k\).
Комментарий. Это типичный пример: простая идея с блоками превращается в сильную оценку.
Глава
Многочлены, последовательности и теория чисел
Ключевая идея
Многочлен с целыми коэффициентами хорошо ведёт себя по модулю: из \(a\equiv b\pmod m\) следует \(f(a)\equiv f(b)\pmod m\). Поэтому задачи о делимости значений многочлена часто сводятся к значению в одной точке, обычно в \(0\).
Последовательности по модулю имеют конечное число состояний. Для рекуррентной последовательности это означает периодичность или предпериодичность, а для обратимых переходов — чистую периодичность.
Основные факты
- Для \(f\in\mathbb Z[x]\) верно \(a-b\mid f(a)-f(b)\).
- Если \(n\mid f(n)\) для всех \(n\), то обычно нужно проверить \(f(0)\).
- Конечная разность \(\Delta f(n)=f(n+1)-f(n)\) понижает степень многочлена на \(1\).
- Многочлены \(\binom{x}{k}\) принимают целые значения при целых \(x\), хотя коэффициенты могут быть дробными.
- Пара \((u_n,u_{n+1})\) рекуррентной последовательности по модулю \(m\) принимает только конечное число значений.
- Для чисел Фибоначчи удобно использовать \(F_{r+s}=F_{r-1}F_s+F_rF_{s+1}\).
Когда применять метод
Метод нужен, когда в условии есть значения \(f(n)\), делимость для всех \(n\), сравнения \(f(a)-f(b)\), суммы степеней, рекуррентные последовательности, периодичность по модулю или числа Фибоначчи.
Как распознать метод
Смотрите на фразы “для всех целых \(n\)”, “многочлен с целыми коэффициентами”, “последовательность задана рекуррентно”, “доказать, что какой-то член делится на \(m\)”. Часто надо не вычислять значения, а сравнить состояния по модулю.
Типичные ошибки
- Считать, что любой многочлен, принимающий целые значения, имеет целые коэффициенты.
- Проверять делимость только на нескольких \(n\) без объяснения периодичности.
- Путать периодичность самой последовательности и периодичность её остатков.
- Использовать формулы Фибоначчи без указания начальной индексации.
- Забывать, что рекуррентный переход может быть необратимым по модулю.
Мини-чеклист
- Для многочлена сначала проверьте сравнение \(f(a)\equiv f(b)\).
- Если есть условие \(n\mid f(n)\), подставьте сравнение с \(0\).
- Для сумм и степеней попробуйте конечные разности.
- Для рекуррентных последовательностей запишите состояние, например \((u_n,u_{n+1})\).
- Для Фибоначчи применяйте евклидову идею: \(F_{m}\) и \(F_n\) ведут себя как индексы \(m\) и \(n\).
Пример 1. Значения многочлена по модулю
Базовый факт, который заменяет много вычислений.
Задача. Пусть \(f\in\mathbb Z[x]\). Докажите, что \(a-b\mid f(a)-f(b)\).
Достаточно проверить для одночлена: \(a^k-b^k=(a-b)(a^{k-1}+a^{k-2}b+\cdots+b^{k-1})\). Линейная комбинация таких разностей с целыми коэффициентами тоже делится на \(a-b\). Значит, \(a-b\mid f(a)-f(b)\).
Комментарий. Это главный мост между многочленами и теорией чисел.
Пример 2. Делимость \(a^n-b^n\)
Классическая факторизация как частный случай многочленного принципа.
Задача. Докажите, что \(a-b\mid a^n-b^n\) и \(a+b\mid a^{2r+1}+b^{2r+1}\).
Первое следует из разности степеней. Для второго положим \(x=a\), \(y=-b\). Тогда \(a^{2r+1}+b^{2r+1}=a^{2r+1}-(-b)^{2r+1}\), а это делится на \(a-(-b)=a+b\).
Комментарий. Умение менять знак часто превращает вторую формулу в первую.
Пример 3. Условие \(n\mid f(n)\)
Типичная задача на значение \(f(0)\).
Задача. Найдите условие на \(f\in\mathbb Z[x]\), при котором \(n\mid f(n)\) для всех \(n\ge1\).
Так как \(n-0\mid f(n)-f(0)\), имеем \(f(n)\equiv f(0)\pmod n\). Поэтому \(n\mid f(n)\) для всех \(n\) тогда и только тогда, когда \(n\mid f(0)\) для всех \(n\). Это возможно только при \(f(0)=0\). Обратно, если \(f(0)=0\), то \(n\mid f(n)-f(0)=f(n)\).
Комментарий. Многие задачи такого типа решаются одной строкой после правильного сравнения.
Пример 4. Конечные разности
Разности превращают степень \(d\) в степень \(d-1\).
Задача. Пусть \(S_k(n)=1^k+2^k+\cdots+n^k\). Объясните, почему \(S_k(n)\) является многочленом по \(n\) степени \(k+1\).
Из бинома Ньютона \((t+1)^{k+1}-t^{k+1}\) выражается как \((k+1)t^k\) плюс многочлен меньшей степени. Суммируя по \(t=1,\ldots,n\), получаем телескопическую левую часть \((n+1)^{k+1}-1\), а справа стоит \((k+1)S_k(n)\) плюс уже известные суммы меньших степеней. Индукция по \(k\) даёт, что \(S_k(n)\) — многочлен степени \(k+1\).
Комментарий. Идея важнее явной формулы.
Пример 5. Целочисленный, но не целокоэффициентный
Не все целочисленные значения приходят от целых коэффициентов.
Задача. Докажите, что \(P(n)=\frac{n(n-1)}2\) целое при любом целом \(n\), хотя коэффициенты \(P\) не все целые.
Произведение двух соседних целых чисел чётно, поэтому \(\frac{n(n-1)}2\in\mathbb Z\). Но коэффициент при \(n^2\) равен \(\frac12\), значит \(P\notin\mathbb Z[x]\).
Комментарий. Этот пример защищает от опасной автоматической замены “целочисленный” на “с целыми коэффициентами”.
Пример 6. Периодичность Фибоначчи по модулю
Периодичность возникает из конечного числа состояний.
Задача. Докажите, что последовательность Фибоначчи периодична по модулю любого \(m\).
Рассмотрим пары \((F_n,F_{n+1})\) по модулю \(m\). Таких пар не больше \(m^2\). Значит, две пары совпадут. Переход \((x,y)\mapsto(y,x+y)\) обратим: \((x,y)\) восстанавливается из \((y,x+y)\) как \((x+y-y,y)\). Поэтому повторение пары приводит к чистому периоду, начиная с \((0,1)\).
Комментарий. Обратимость перехода важна: она убирает предпериод.
Пример 7. Делимость чисел Фибоначчи
Индексы часто наследуют делимость.
Задача. Докажите, что если \(d\mid n\), то \(F_d\mid F_n\).
Используем тождество \(F_{r+s}=F_{r-1}F_s+F_rF_{s+1}\). Из него следует: если \(F_d\mid F_r\), то \(F_d\mid F_{r+d}\). Действительно, \(F_{r+d}=F_{d-1}F_r+F_dF_{r+1}\). Начиная с \(r=d\), получаем по индукции \(F_d\mid F_{td}\) для всех \(t\).
Комментарий. Это подготовка к формуле \(\gcd(F_m,F_n)=F_{\gcd(m,n)}\).
Пример 8. Бесконечно много составных членов
Иногда достаточно найти один модуль и один класс индексов.
Задача. Докажите, что среди чисел \(2^{2^n}+3\) бесконечно много составных.
Рассмотрим модуль \(19\). Так как \(2^4\equiv16\equiv-3\pmod{19}\), нам нужно \(2^n\equiv4\pmod{18}\), ведь порядок \(2\) по модулю \(19\) делит \(18\). Последовательность \(2^n\pmod{18}\) имеет период \(6\), и \(2^n\equiv4\pmod{18}\) при \(n\equiv2\pmod6\). Поэтому при всех \(n\equiv2\pmod6\) число \(2^{2^n}+3\) делится на \(19\). Для \(n>2\) оно больше \(19\), значит составно.
Комментарий. Это пример “период индекса внутри степени”.