D1 Делимость, признаки делимости

Почему метод важен

По таблице ВсОШ 9 D1 (Делимость и признаки) — 11 задач как основной. С учётом подкатегории D1b (разбор по малым модулям) — ещё 8 задач. Итого делимость встречается в каждом году с 2011 по 2025, на всех этапах.

Главное, что даёт D1:

• быстрые признаки делимости на 2, 3, 4, 5, 8, 9, 11;
• умение использовать НОД и НОК;
• работа с простыми делителями;
• алгоритм Евклида и связь чисел через линейные комбинации;
• мост к D3 (сравнения), D12 (целочисленные уравнения), C5a (целочисленные корни).

Реальные ориентиры из таблицы

Предупреждение: часть задач — OCR-фрагменты; полные доказательства в семействах ниже приведены только для учебных задач, реальные сюжеты сопровождаются только первым ходом.

• Определение делимости. $a \mid b \Leftrightarrow \exists k \in \mathbb{Z}: b = ak$. Транзитивность: $a \mid b, b \mid c \Rightarrow a \mid c$. Линейность: если $a \mid b$ и $a \mid c$, то $a \mid (\alpha b + \beta c)$ для любых $\alpha, \beta \in \mathbb{Z}$.

• Арифметика по модулю. $a \equiv b \pmod{m}$ сохраняется при сложении, вычитании и умножении: $(a_1 + a_2) \equiv (b_1 + b_2)$, $a_1 a_2 \equiv b_1 b_2 \pmod{m}$. Условие: операции целые; деление — осторожно (нельзя делить на числа, не взаимно простые с $m$$). *$Когда использовать*: любая задача на делимость.

• Малая теорема Ферма. Если $p$ — простое и $\gcd(a, p) = 1$, то $a^{p-1} \equiv 1 \pmod{p}$. Условие: $p$ простое, $p \nmid a$. Когда использовать: вычислить $a^n \pmod{p}$ при большом $n$.

• Разложение $a^n - b^n$. $a^n - b^n = (a-b)(a^{n-1} + a^{n-2}b + \ldots + b^{n-1})$. В частности, $(a-b) \mid (a^n - b^n)$ всегда. Когда использовать: нужна делимость степеней.

• Работа по модулю. Заменяй числа их остатками по нужному модулю, проводи все вычисления с остатками.
• Факторизация выражения. Раскладывай $n^k - c$ или $n^k + c$ на множители и анализируй каждый.
• Разбор случаев по остатку. Разбери $n$ по остаткам $0, 1, \ldots, m-1$ и в каждом случае проверяй делимость.
• Индукция по $n$. Для утверждений вида «$n^k + c$ делится на $d$ при всех $n$» — база + шаг через разность $a_{n+1} - a_n$.
• Использование свойства транзитивности. Если найден промежуточный делитель — цепочка $a \mid b, b \mid c \Rightarrow a \mid c$.
• Возведение в степень по модулю. Используй малую теорему Ферма или периодичность степеней по модулю.

Поверхностные признаки (что буквально написано):
- «Докажите, что $n^k + c$ делится на $d$».
- «Найдите все натуральные $n$, при которых выражение является целым».
- «Является ли число $N$ делителем $M$?»

Структурные признаки (форма выражения, объекты):
- Выражение вида $n^k \pm n^{k-1} \pm \ldots \pm c$ для произвольного $n \in \mathbb{N}$.
- Произведение нескольких последовательных натуральных чисел.
- Задача содержит одновременно «целые числа» и требование «делится на».

Цель задачи (что от тебя хотят):
- Доказать делимость выражения при всех допустимых $n$.
- Найти все $n$, при которых делимость выполняется.
- Найти остаток от деления конкретного числа на заданный делитель.

7 семейств D1

Семейство 1. Признаки делимости

Сигнал: нужно проверить, делится ли число на 2, 3, 4, 5, 8, 9, 11.

Главный ход: применить соответствующий признак.

Задача 1.1

Делится ли \(2025\) на 9?

Скелет решения: сумма цифр \(2+0+2+5=9\), делится на 9. Значит число тоже делится.

Ответ:

\[ \text{да} \]

Задача 1.2

Найдите цифру \(x\), при которой число \(\overline{1x21}\) делится на 11.

Скелет решения: знакопеременная сумма \(1-x+2-1=2-x\). Делится на 11, если \(2-x\equiv 0\pmod{11}\), т.е. \(x=2\) (или \(x=-9\), не подходит).

Ответ:

\[ 2 \]

Задача 1.3

Найдите все 3-значные числа, у которых произведение цифр делится на 25.

Скелет решения: произведение трёх цифр (каждая от 0 до 9) делится на 25 тогда и только тогда, когда среди цифр есть две пятёрки. Перебираем: расстановки двух 5 на трёх позициях — \(\binom{3}{2}=3\), и третья цифра от 0 до 9. Но первая цифра не 0. Перебор даёт конкретный список.

Аккуратно: позиции 5: (1,2): \(55x\), \(x\in 0..9\) — 10 чисел. (1,3): \(5x5\) — 10. (2,3): \(x55\), \(x\in 1..9\) — 9 чисел. Если третья цифра тоже 5: число \(555\) встретилось 3 раза, отнимем 2. Всего \(10+10+9-2=27\).

Ответ:

\[ 27\ \text{чисел} \]

Задача 1.4

Реальный сюжет (2019, школьный, №1). 4-значное число называется «восхитительным», если оно делится на 25, сумма цифр делится на 25 и произведение цифр делится на 25. Найдите все восхитительные числа.

Скелет решения: реальный сюжет 2019 школьного. Число делится на 25 — последние две цифры 00, 25, 50, 75. Сумма цифр 4-значного делится на 25 — сумма от \(1\) до \(36\), значит сумма равна 25. Произведение цифр делится на 25 — среди цифр есть две пятёрки или одна 5 и одна 0 (но \(5\cdot 0=0\), а 0 делится на 25; кстати, любое произведение, содержащее 0, делится на 25 — это \(0\)). То есть либо две пятёрки в записи, либо ноль среди цифр. Случай 1: последние две цифры 00. Сумма цифр первых двух = 25. Цифры от 0 до 9, две цифры с суммой 25 — невозможно. Случай 2: последние две 25. Тогда сумма первых двух = \(25-2-5=18\), цифры \(9+9=18\). Число \(9925\). Произведение: \(9\cdot 9\cdot 2\cdot 5=810\) — делится на 25? \(810/25=32.4\) — нет. Не подходит. Случай 3: последние 50. Сумма первых двух = \(25-5-0=20\), цифры: пар нет (макс \(9+9=18\)). Не подходит. Случай 4: последние 75. Сумма первых двух = \(25-7-5=13\). Пары: \((4,9),(5,8),(6,7)\). Числа: \(4975,9475,5875,8575,6775,7675\). Проверка произведения: \(4\cdot 9\cdot 7\cdot 5=1260\), \(1260/25=50.4\) — не делится. Нужно две пятёрки или ноль. Среди пар, дающих 13, нет дополнительной 5 кроме предъявленной в последней 7-5. Значит произведение содержит ровно одну 5. \(\Rightarrow\) не делится на 25. Получаем 0 решений.

Уточнение для курса: реальный текст ВсОШ говорит про \(N\), не обязательно 4-значное, или допускает другие сочетания. Без полного исходного текста (OCR-фрагмент) полный ответ не выводим.

Ответ для курса:

\[ \text{первый ход — перебор последних двух цифр (00, 25, 50, 75) и условий на сумму/произведение.} \]

Семейство 2. Линейные комбинации и НОД

Сигнал: даны два условия «\(p\mid A\)» и «\(p\mid B\)», нужно вывести «\(p\mid C\)».

Главный ход: построить \(C\) как линейную комбинацию \(A\) и \(B\).

Задача 2.1

Пусть \(p\mid (2a+3b)\) и \(p\mid (a+b)\), где \(p\) — простое. Докажите, что \(p\mid a\) и \(p\mid b\).

Скелет решения: \(p\mid (2a+3b)-2(a+b)=b\). Значит \(p\mid b\). Из \(p\mid (a+b)\) и \(p\mid b\) получаем \(p\mid a\).

Ответ:

\[ p\mid a,\ p\mid b \]

Задача 2.2

Найдите \(\gcd(126, 84)\).

Скелет решения: \(126=1\cdot 84+42\). \(84=2\cdot 42+0\). НОД равен 42.

Ответ:

\[ 42 \]

Задача 2.3

Реальный сюжет (2024, школьный, №8). Простое \(p\) таково, что для любых целых \(a, b\) числа \(10a+3b\) и \(a+8b\) одновременно делятся на \(p\) или одновременно не делятся. Найдите все возможные \(p\).

Скелет решения: реальный сюжет 2024 школьного. Условие означает, что \(p\mid (10a+3b)\Leftrightarrow p\mid (a+8b)\). Это эквивалентно тому, что вектор \((10,3)\) и \((1,8)\) задают одну и ту же «подсетку» по модулю \(p\). По линейной алгебре над \(\mathbb{F}_p\), это значит, что определитель \(10\cdot 8-3\cdot 1=80-3=77\) делится на \(p\), а сами векторы не нулевые. \(77=7\cdot 11\). Значит \(p\in\{7,11\}\). Проверка: для \(p=7\): \(10a+3b\equiv 3a+3b=3(a+b)\), \(a+8b\equiv a+b\). Делится на 7 одновременно — да. Для \(p=11\): \(10a+3b\equiv -a+3b\), \(a+8b\equiv a-3b\). Они различаются знаком, делятся на 11 одновременно — да. Значит \(p\in\{7,11\}\).

Ответ:

\[ 7,\ 11 \]

Задача 2.4

Реальный сюжет (2022, муниципальный, №3). Натуральные \(a, b\) таковы, что \(a\) делится на \(b+1\), и \(43\) делится на \(a+b\). (а) Укажите любое возможное \(a\). (б) Чему может быть равно \(b\)?

Скелет решения: реальный сюжет 2022 муниципального. \(a+b\) делит 43 (простое), значит \(a+b\in\{1, 43\}\). \(a, b\ge 1\), значит \(a+b=43\). Тогда \(a=43-b\). Условие \(b+1\mid a=43-b\): \(b+1\mid 43-b\). Заметим: \(43-b=44-(b+1)\), значит \(b+1\mid 44\). Делители 44: \(\{1,2,4,11,22,44\}\). \(b+1\in\{1,2,4,11,22,44\}\), \(b\in\{0,1,3,10,21,43\}\). Натуральное \(b\ge 1\): \(\{1,3,10,21,43\}\). Но \(b\le 42\) (так как \(a=43-b\ge 1\)): \(\{1,3,10,21\}\). Соответствующие \(a\): \(\{42,40,33,22\}\).

(а) Например, \(a=42\). (б) \(b\in\{1,3,10,21\}\).

Ответ:

\[ a=42\ \text{подходит},\ b\in\{1,3,10,21\} \]

Семейство 3. Простые делители и разложение

Сигнал: в условии говорят про делители числа, простые сомножители, степени.

Главный ход: рассмотреть разложение \(n=p_1^{a_1}\cdots p_k^{a_k}\).

Задача 3.1

Сколько натуральных делителей у числа 360?

Скелет решения: \(360=2^3\cdot 3^2\cdot 5\). Число делителей \((3+1)(2+1)(1+1)=24\).

Ответ:

\[ 24 \]

Задача 3.2

Найдите наименьшее натуральное \(n\), у которого ровно 6 натуральных делителей.

Скелет решения: число делителей = 6 = \(6=6\cdot 1=3\cdot 2\). Варианты: \(p^5\) или \(p^2 q\). Минимум: \(2^5=32\), \(2^2\cdot 3=12\). Минимум \(12\).

Ответ:

\[ 12 \]

Задача 3.3

Реальный сюжет (2014, заключительный, №5). К натуральному числу \(N\) прибавили его наибольший делитель, меньший \(N\), и получили степень 10. Найдите все такие \(N\).

Скелет решения: реальный сюжет 2014 заключительного. Наибольший делитель \(

Для \(p=3\): \(N=10^k\cdot 3/4\) — натуральное при \(4\mid 10^k\), то есть \(k\ge 2\). \(N=3\cdot 10^k/4=3\cdot 25\cdot 10^{k-2}=75\cdot 10^{k-2}\). Проверим, что наименьший простой делитель \(N\) равен 3. \(75=3\cdot 25\), значит для \(k=2\) \(N=75=3\cdot 5^2\), наименьший простой 3 — ок. Для \(k=3\) \(N=750=2\cdot 3\cdot 5^3\) — наименьший простой 2, не 3, противоречие. Значит \(k=2\), \(N=75\).

Для \(p=7\): \(N=10^k\cdot 7/8\) — натуральное при \(8\mid 10^k\), невозможно (степени 10 имеют ровно \(k\) двоек).

Для \(p=19\): \(N=10^k\cdot 19/20=10^{k-1}\cdot 19/2\) — натуральное при \(k\ge 1\) и \(2\mid 19\) — нет. Не подходит.

Проверка \(N=75\): наибольший делитель \(<75\) — это \(75/3=25\). \(75+25=100=10^2\). Подходит.

Ответ:

\[ 75 \]

Задача 3.4

Реальный сюжет (2022, заключительный, №1). Назовём «главными» делителями составного числа \(n\) два наибольших его натуральных делителя, отличных от \(n\). Составные \(a, b\) таковы, что главные делители \(a\) и \(b\) связаны определённым образом. Какой ход?

Скелет решения: реальный сюжет 2022 заключительного. Два наибольших делителя \(

Ответ для курса:

\[ \text{ход — выписать главные делители как }n/p,\ n/q,\text{ где }p

Семейство 4. Делимость произведений

Сигнал: в задаче есть произведение последовательных чисел, факториал, многочлен от \(n\).

Главные факты:

• произведение \(k\) последовательных чисел делится на \(k!\);
• \(\binom{n}{k}\) — всегда целое;
• многочлены вида \(n(n+1)\), \(n(n+1)(n+2)\) дают делимость на 2, 6, 24, ...

Задача 4.1

Докажите, что \(n(n+1)\) всегда чётно.

Скелет решения: из двух последовательных одно чётно.

Ответ:

\[ \text{да} \]

Задача 4.2

Докажите, что \(n(n+1)(n+2)\) всегда делится на 6.

Скелет решения: среди трёх последовательных одно делится на 3, среди двух — на 2. Поэтому произведение делится на \(2\cdot 3=6\).

Ответ:

\[ \text{да} \]

Задача 4.3

Реальный сюжет (2011, региональный, №5). Найдите все числа \(a\) такие, что для любого натурального \(n\) число \(an(n+2)(n+4)\) — целое.

Скелет решения: реальный сюжет 2011 регионального. Подставим \(n=1\): \(a\cdot 1\cdot 3\cdot 5=15a\) целое, значит \(a=k/15\). Подставим \(n=2\): \(a\cdot 2\cdot 4\cdot 6=48a\) целое, значит \(a=m/48\). Подставим \(n=3\): \(a\cdot 3\cdot 5\cdot 7=105a=15\cdot 7\cdot a\), значит \(a=l/105\). \(a\) должно быть рациональным с знаменателем, делящим НОД всех таких выражений. Точнее: \(a\) такое, что для всех \(n\) выражение \(n(n+2)(n+4)\) даёт целое после умножения на \(a\). Произведение \(n(n+2)(n+4)\): три числа одной чётности (если \(n\) чётное, все три чётные) или все три нечётные. Минимальное значение по модулю — НОД \(\gcd_n n(n+2)(n+4)\). Для \(n=1\): \(15\). Для \(n=3\): \(105=3\cdot 5\cdot 7\). НОД(15,105)=15. Для \(n=5\): \(5\cdot 7\cdot 9=315\). НОД(15,315)=15. Для \(n=2\): \(48=16\cdot 3\). НОД(15,48)=3. Для \(n=4\): \(4\cdot 6\cdot 8=192\). НОД(3,192)=3. Получаем, что \(a\) должно делать \(3a\) целым. Значит \(a=k/3\). Проверка: \(a=1/3\): для \(n=1\): \(1/3\cdot 15=5\) — целое. Для \(n=2\): \(48/3=16\) — целое. Для всех \(n\) выражение \(n(n+2)(n+4)/3\) — нужно показать целочисленность. Среди \(n, n+2, n+4\) одно делится на 3 (так как их остатки по модулю 3 — это арифметическая прогрессия с разностью 2 и тремя членами, покрывающими все остатки). Значит \(3\mid n(n+2)(n+4)\), и \(a/3\) для целочисленности — нужно \(a\cdot\text{const}\) целое, то есть \(a\in\frac13\mathbb{Z}\).

Ответ:

\[ a=k/3,\ k\in\mathbb{Z} \]

Задача 4.4

Докажите, что \(\binom{2n}{n}\) делится на \(n+1\) (это число Каталана умноженное на \(n+1\)).

Скелет решения: \(C_n=\binom{2n}{n}/(n+1)\) — число Каталана, целое (известный факт). Можно доказать через тождество \(\binom{2n}{n}-\binom{2n}{n+1}=C_n\) и индукцию.

Ответ:

\[ \text{да} \]

Семейство 5. Цифровые суммы и остатки

Сигнал: задача про сумму цифр, цифры числа, делимость на 9 или 11.

Главный ход: связать число с его суммой цифр по модулю 9.

Задача 5.1

Чему равен остаток от деления числа \(\overline{abcd}\) на 9, если сумма цифр равна 17?

Скелет решения: остаток равен сумме цифр по модулю 9. \(17\bmod 9=8\).

Ответ:

\[ 8 \]

Задача 5.2

Может ли число \(2024^{2024}\) оканчиваться на 5?

Скелет решения: чтобы число оканчивалось на 5, оно должно быть нечётным. \(2024^{2024}\) чётно. Не может.

Ответ:

\[ \text{нет} \]

Задача 5.3

Реальный сюжет (2015, школьный, №3). Сколько существует трёхзначных чисел, в 5 раз больших произведения своих цифр?

Скелет решения: реальный сюжет 2015 школьного (повтор 2014). Уравнение \(100a+10b+c=5abc\). Делимость: правая часть кратна 5, значит \(c=0\) или \(c=5\). При \(c=0\): \(5abc=0\), но левая часть \(\ge 100\) — нет. При \(c=5\): \(100a+10b+5=25ab\), значит \(5\mid 100a+10b\) — да. Делим на 5: \(20a+2b+1=5ab\). Из этого \(5ab-2b=20a+1\), \(b(5a-2)=20a+1\), \(b=\dfrac{20a+1}{5a-2}\). Длинное деление: \(20a+1=4(5a-2)+9\), значит \(b=4+\dfrac{9}{5a-2}\). Значит \(5a-2\mid 9\), и \(5a-2\in\{1,3,9,-1,-3,-9\}\). \(a\) натуральное от 1 до 9: \(5a-2\in\{3,8,13,18,\ldots\}\). \(5a-2=3\Rightarrow a=1\), \(b=4+3=7\). \(5a-2=9\Rightarrow a=11/5\), не целое. Единственный ответ: \(a=1, b=7, c=5\), число 175. Проверка: \(5\cdot 1\cdot 7\cdot 5=175\).

Ответ:

\[ 1\ \text{(число 175)} \]

Задача 5.4

Реальный сюжет (2025, школьный, №4). Числа 3, 7, 10, 16, 23, 31 разбили на три группы по два числа так, что в первой только простые числа, во второй сумма пары делится на ..., и т.д.

Скелет решения: реальный сюжет 2025 школьного. Простые из шести: 3, 7, 23, 31 (10 и 16 — составные). В одну группу — две простых. Остальные две группы по два — содержат хотя бы одно из 10 или 16. Из условий на суммы получаем уравнения. Текст OCR-фрагментарный.

Ответ для курса:

\[ \text{первый ход — выделить простые }\{3,7,23,31\}\text{ и анализировать суммы пар.} \]

Семейство 6. Сравнения по модулю в задачах на делимость

Сигнал: «найдите остаток», «делится ли», «существует ли число с свойством».

Главный ход: работа в \(\mathbb{Z}/n\mathbb{Z}\).

Задача 6.1

Найдите остаток от деления \(2^{100}\) на 3.

Скелет решения: \(2\equiv -1\pmod 3\), значит \(2^{100}\equiv 1\pmod 3\).

Ответ:

\[ 1 \]

Задача 6.2

Докажите, что \(n^3-n\) делится на 6 при любом натуральном \(n\).

Скелет решения: \(n^3-n=n(n-1)(n+1)\) — произведение трёх последовательных. Делится на \(2\cdot 3=6\).

Ответ:

\[ \text{да} \]

Задача 6.3

Реальный сюжет (2018, заключительный, №1). Дана возрастающая последовательность натуральных \(a_1, a_2, \ldots\) и последовательность простых \(p_1, p_2, \ldots\). Какой ход?

Скелет решения: реальный сюжет 2018 заключительного. Главный приём — связать рост \(a_n\) с распределением простых чисел. Через теорему о бесконечности простых и оценку \(\sum 1/p_n\) получаем ограничения. Без полного текста не идём.

Ответ для курса:

\[ \text{ход — связать }a_n\text{ и }p_n\text{ через оценки сумм или произведений.} \]

Задача 6.4

Реальный сюжет (2012, заключительный, №7). На доске 10 последовательных натуральных чисел. Разрешается заменить пару \((a, b)\) на пару \((a+b, ab)\) или \(\ldots\). Какой инвариант?

Скелет решения: реальный сюжет 2012 заключительного. Инварианты — степени малых простых в наибольшем числе на доске, или НОД всех чисел. Это типичная задача про инварианты и делимость. Без полного текста полное решение не приводим.

Ответ для курса:

\[ \text{ход — найти инвариант: НОД, остаток по модулю, или степень простого.} \]

Семейство 7. Делимость в комбинаторных и геометрических задачах

Сигнал: задача про доску, шарики, расстановки — но решается через делимость.

Главный ход: ввести инвариант на основе делимости.

Задача 7.1

На доске написаны числа от 1 до 100. Можно ли так стереть несколько чисел, чтобы сумма оставшихся была равна 99?

Скелет решения: сумма всех \(=\dfrac{100\cdot 101}{2}=5050\). Нужно стереть сумму \(5050-99=4951\). Можно ли набрать 4951 из чисел 1..100? Да, например, числа 1..100 кроме набора с суммой 99. Например, оставить только \(99\) и стереть остальные. Сумма стёртых \(=5050-99=4951\). Проверка: \(99\) есть в \(1..100\), всё ок.

Ответ:

\[ \text{да, оставить только число 99} \]

Задача 7.2

На круге расставлены 100 фишек. Между каждыми двумя соседними фишками вставили ещё одну. Сколько теперь фишек?

Скелет решения: между каждой парой соседних — 1 новая, всего 100 пар (по кругу) — добавили 100, всего \(200\).

Ответ:

\[ 200 \]

Задача 7.3

Реальный сюжет (2023, муниципальный, №3). По кругу лежат \(n\) шариков (\(6\le n\le 100\)). Их перемешали и снова выложили так, что между каждыми двумя бывшими соседями теперь лежат ровно 2 шарика. Какой ход?

Скелет решения: реальный сюжет 2023 муниципального. Перестановка фиксирует расстояние 3 между бывшими соседями. То есть перестановка работает как умножение на 3 по модулю \(n\). Чтобы такая перестановка была корректной, нужно \(\gcd(3, n)=1\), то есть \(n\) не делится на 3. Дополнительные условия на цикловую структуру дают ответ. Текст частично OCR.

Ответ для курса:

\[ \text{ход — рассмотреть перестановку как умножение на 3 mod }n,\text{ нужно }\gcd(3,n)=1. \]

Задача 7.4

Реальный сюжет (2024, муниципальный, №2). Катя написала натуральное число. За ход можно взять две подряд идущие цифры, их произведение является двузначным, и заменить пару одной цифрой. Какой ход?

Скелет решения: реальный сюжет 2024 муниципального. Каждая операция уменьшает длину записи на 1. Инвариант — связан с произведением цифр или его остатками по модулю 9 (так как произведение двух цифр и одной цифры связаны по mod 9). Текст частично OCR.

Ответ для курса:

\[ \text{ход — найти инвариант через произведение цифр по модулю 9.} \]

• Ошибка: делить обе части сравнения $ax \equiv ay \pmod{m}$ на $a$ и получать $x \equiv y \pmod{m}$. Почему неверно: это верно только если $\gcd(a, m) = 1$. Как избежать: при сокращении на $a$ делитель меняется: $x \equiv y \pmod{m/\gcd(a,m)}$.
• Ошибка: считать, что $a \mid bc$ и $a \mid b$ влечёт $a \mid c$. Почему неверно: это неверно вообще. Как избежать: нужно $\gcd(a, b) = 1$ для этого вывода (лемма Евклида).
• Ошибка: при проверке делимости на сложное число $m$ проверять только одну из пар оснований. Почему неверно: нужно покрыть всё разложение $m = p_1^{a_1} \cdots p_k^{a_k}$. Как избежать: раскладывай $m$ на простые множители и проверяй каждый.
• Ошибка: применять малую теорему Ферма, не проверив взаимную простоту $\gcd(a, p) = 1$. Почему неверно: если $p \mid a$, то $a^{p-1} \equiv 0 \neq 1 \pmod{p}$. Как избежать: отдельно разбирай случай $p \mid n$ (там делимость очевидна).
• Ошибка: доказывать делимость «по конкретным примерам». Почему неверно: сколько бы примеров ни было, это не доказательство для всех $n$. Как избежать: используй индукцию, модульную арифметику или факторизацию.