Задачи на делимость
Задачи на делимость решают через признаки делимости, разложение чисел на простые множители, свойства делителей и работу с остатками. Перед изучением темы повторите признаки делимости, наибольший общий делитель и наименьшее общее кратное.
Делители и кратные
Натуральное число \(d\) называется делителем числа \(n\), если \(n\) делится на \(d\) без остатка. В этом случае говорят, что \(n\) кратно \(d\), или \(d\mid n\). Например, \(3\mid 18\), потому что \(18=3\cdot6\). Числа \(1\) и само число \(n\) всегда являются делителями \(n\).
Запись \(a\mid b\) означает: существует целое число \(k\), для которого \(b=ak\). Если такого \(k\) нет, то \(a\) не является делителем \(b\).
Если требуется найти все делители числа, удобно сначала разложить его на простые множители. Делители образуются выбором степеней каждого простого множителя от нулевой до полной.
Если \(n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}\) — разложение на различные простые множители, то количество положительных делителей числа \(n\) равно произведению \((\alpha_1+1)(\alpha_2+1)\cdots(\alpha_r+1)\).
Делители удобно искать парами: если \(d\mid n\), то одновременно \(\frac nd\mid n\). Для квадратного числа средний делитель может совпасть с парой: например, у \(36\) пара \(6\cdot6\) учитывается один раз.
Разложение на простые множители
Факторизация — представление натурального числа в виде произведения простых чисел. Например, \(360=2^3\cdot3^2\cdot5\). Простое число имеет ровно два положительных делителя: \(1\) и само себя.
Каждое натуральное число, большее \(1\), единственным образом представляется в виде произведения простых множителей с точностью до порядка множителей. Поэтому при сравнении, делимости и подсчёте делителей достаточно работать со степенями простых чисел.
Алгоритм факторизации: сначала делите число на \(2\), пока это возможно; затем проверяйте простые делители \(3,5,7,\ldots\). Если после делений осталось число больше \(1\), оно само является простым множителем. Проверять делители достаточно до квадратного корня из текущего числа.
- Разложите каждое число на простые множители.
- Соберите одинаковые простые множители в степени.
- Для делимости сравнивайте показатели степеней.
- Для НОД берите меньшие показатели, для НОК — большие.
После разложения перемножьте найденные множители. Если произведение не равно исходному числу, ошибка возникла на одном из этапов деления.
Свойства делимости и задачи на множители
Основные свойства позволяют заменять сложное условие более простым. Если \(a\mid b\) и \(a\mid c\), то \(a\mid(b+c)\) и \(a\mid(b-c)\). Если \(a\mid b\), то \(a\mid bc\) для любого целого \(c\). Если \(a\mid b\) и \(b\mid c\), то \(a\mid c\).
Если одно и то же число делит каждое из двух слагаемых, оно делит их сумму и разность: \(d\mid a\) и \(d\mid b\Rightarrow d\mid(a+b)\) и \(d\mid(a-b)\). Это особенно полезно при группировке слагаемых и сравнении выражений.
Например, чтобы доказать делимость \(2^{10}-2^4\) на \(12\), вынесем общий множитель: \(2^{10}-2^4=2^4(2^6-1)=16\cdot63\). Но \(16\cdot63\) не делится на \(12\), поэтому утверждение неверно. Проверка факторизацией сразу показывает, что в произведении есть только \(2^4\) и нечётный множитель, а для делимости на \(12=2^2\cdot3\) этого достаточно — здесь делимость, наоборот, верна. Значит, исходный вывод о неверности был ошибочным: \(16\cdot63=1008\), а \(1008:12=84\).
Сколько положительных делителей имеет число \(72=2^3\cdot3^2\)?
При решении уравнений в целых числах полезно использовать ограниченность делителей. Если \(xy=N\), то \(x\) и \(y\) — делители числа \(N\). Если требуется найти пары натуральных чисел, достаточно выписать пары делителей \(N\) и проверить дополнительные условия.
Остатки и алгоритм деления
При делении целого числа \(a\) на натуральное \(m\) существует единственная запись \(a=mq+r\), где \(q\) — частное, а \(r\) — остаток, причём \(0\le r<m\). Страница алгоритм деления с остатком подробно объясняет эту запись.
Если известны остатки, действия с числами можно выполнять с остатками: остаток суммы равен остатку суммы остатков, а остаток произведения — остатку произведения остатков. Для степеней сначала найдите закономерность в последовательности остатков.
Найдём остаток числа \(7^{2024}\) при делении на \(10\).
Ответ: остаток равен \(1\). Такой метод особенно удобен для последних цифр и больших степеней. При этом нужно следить, чтобы остаток был неотрицательным и строго меньше делителя.
Как выбирать метод решения
| Условие задачи | Основной приём |
|---|---|
| Найти все делители числа | Факторизация и пары делителей |
| Найти количество делителей | Формула через показатели степеней |
| Проверить делимость произведения | Сравнение простых множителей |
| Найти НОД или НОК | Разложение на простые множители |
| Найти остаток большой степени | Цикл остатков по модулю |
| Составить число по условию | Признаки делимости и перебор цифр |
Для составления числа применяют составление числа по условию делимости и применение нескольких признаков делимости. Если выражение содержит сумму или разность, используйте делимость суммы и разности. Задачи об общих делителях и кратных связаны с общими делителями чисел и общими кратными чисел.
1. Считать \(1\) простым числом: это неверно. 2. Забывать множитель, оставшийся после деления. 3. В формуле количества делителей складывать показатели вместо умножения \((\alpha_i+1)\). 4. При делении с остатком писать остаток, равный делителю или больший него. 5. Применять признак делимости к произведению, не проверив каждый необходимый простой множитель. 6. В задачах с выражениями нарушать порядок действий.
Для делимости переходите к простым множителям; для остатков — к равенствам по модулю; для поиска делителей — к парам и показателям степеней.
Итоговая проверка
Что нужно запомнить
- Делимость \(a\mid b\) означает представление \(b=ak\) с целым \(k\).
- Основная теорема арифметики даёт единственное разложение числа на простые множители.
- Если \(n=\prod p_i^{\alpha_i}\), то число его делителей равно \(\prod(\alpha_i+1)\).
- Для задач на остатки используйте запись \(a=mq+r\) и циклы степеней по модулю.
- Свойства суммы и разности помогают преобразовывать условия делимости.