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

Идея метода: НОД (наибольший общий делитель) двух натуральных чисел $a$ и $b$ — наибольшее число, на которое делятся оба. НОК (наименьшее общее кратное) — наименьшее натуральное число, кратное обоим.

Алгоритм Евклида вычисляет НОД очень эффективно: $\gcd(a, b) = \gcd(b, a \bmod b)$. Это работает потому, что любой делитель $a$ и $b$ также делит $a - b$ и $a \bmod b$.

Ключевое теоретическое следствие — тождество Безу: для любых $a, b$ существуют целые $x, y$ такие, что $ax + by = \gcd(a, b)$. Это позволяет не просто вычислить НОД, но и выразить его в виде линейной комбинации.

Связь НОД и НОК: $\gcd(a, b) \cdot \text{lcm}(a, b) = a \cdot b$ — это «бухгалтерское» тождество: разложения $a$ и $b$ на простые множители «поделены» между НОД и НОК без остатка.

Метод активируется, когда задача касается общих делителей, взаимной простоты, линейных уравнений в целых числах (уравнение $ax + by = c$) или выражений вида $\gcd(f(n), g(n))$.

• Алгоритм Евклида. $\gcd(a, b) = \gcd(b, a \bmod b)$, база: $\gcd(a, 0) = a$. Условие: $a, b \in \mathbb{N}$. Когда использовать: вычислить $\gcd$ за $O(\log \min(a,b))$ шагов.

• Тождество Безу. Для любых $a, b \in \mathbb{Z}$ (не оба нуль) существуют $x, y \in \mathbb{Z}$: $ax + by = \gcd(a, b)$. Условие: целые числа. Когда использовать: доказать взаимную простоту, решить линейное диофантово уравнение.

• Связь НОД и НОК. $\gcd(a, b) \cdot \text{lcm}(a, b) = a \cdot b$ для натуральных $a, b$. Когда использовать: задачи, где даны и НОД и НОК одновременно.

• Лемма Евклида. Если $\gcd(a, b) = 1$ и $a \mid bc$, то $a \mid c$. Условие: взаимная простота $a$ и $b$. Когда использовать: доказательства на делимость при взаимно простых числах.

• Линейное диофантово уравнение. $ax + by = c$ имеет целочисленные решения $\Leftrightarrow \gcd(a, b) \mid c$. Когда использовать: задачи на существование целочисленных решений.

• Применить алгоритм Евклида. Последовательно применяй $\gcd(a,b) = \gcd(b, a \bmod b)$ до достижения нуля.
• Доказать взаимную простоту через тождество Безу. Найди явные $x, y$ такие, что $ax + by = 1$.
• Использовать $\gcd(a,b) \cdot \text{lcm}(a,b) = ab$. При заданных НОД и НОК найди $a, b$.
• Вычислить $\gcd(f(n), g(n))$ для выражений. Пиши $f(n) = q \cdot g(n) + r(n)$ и применяй $\gcd(f, g) = \gcd(g, r)$.
• Лемма Евклида для делимости. При $\gcd(a, b) = 1$ и $a \mid bc$ — немедленно $a \mid c$.
• Разложение на простые множители. $\gcd(a, b) = \prod p_i^{\min(\alpha_i, \beta_i)}$, $\text{lcm}(a, b) = \prod p_i^{\max(\alpha_i, \beta_i)}$.

Поверхностные признаки (что буквально написано):
- «Найдите НОД», «найдите НОК», «числа $a$ и $b$ взаимно просты».
- «Докажите, что $\gcd(f(n), g(n)) = $ const для всех $n$».
- «Уравнение $ax + by = c$ в целых числах».

Структурные признаки (форма выражения, объекты):
- В задаче фигурирует пара чисел и их делители или кратные.
- Нужна взаимная простота двух выражений, зависящих от параметра.
- Дано произведение $a \cdot b$ и один из: $\gcd(a, b)$ или $\text{lcm}(a, b)$.

Цель задачи (что от тебя хотят):
- Вычислить НОД или НОК.
- Решить линейное диофантово уравнение.
- Доказать, что $\gcd(a_n, b_n)$ не зависит от $n$ или всегда равно конкретному числу.

Задача 1. Найдите все натуральные числа $n$, для которых $\gcd(n^2 + 4, n + 2) > 1$.

Источник: тренировочная (стиль ВсОШ муниципальный)

Как думать (рассуждение ученика):
1. Что я вижу? НОД выражений, зависящих от $n$. Обозначу $d = \gcd(n^2 + 4, n + 2)$.
2. Первый ход: применю алгоритм Евклида — нахожу $n^2 + 4 \pmod{n+2}$.
3. $n^2 + 4 = (n+2)(n-2) + 8$. Значит $d = \gcd(n+2, 8)$.
4. Вывод: $d > 1 \Leftrightarrow \gcd(n+2, 8) > 1 \Leftrightarrow n + 2$ чётно $\Leftrightarrow n$ чётное.

Решение:

$\gcd(n^2+4, n+2) = \gcd((n+2)(n-2)+8, n+2) = \gcd(8, n+2)$.

Это больше 1 тогда и только тогда, когда $\gcd(8, n+2) > 1$, то есть $n+2$ чётно, то есть $n$ чётное.

Ответ: все чётные натуральные числа $n$.

Что было главным: алгоритм Евклида применяется к выражениям от $n$, а не к конкретным числам — тот же принцип.

Задача 2. Докажите, что для любых натуральных $m, n$ выполняется $\gcd(F_m, F_n) = F_{\gcd(m,n)}$, где $F_k$ — числа Фибоначчи.

Источник: классическое тождество (ВсОШ, заключительный этап, различные годы)

Как думать (рассуждение ученика):
1. Что я вижу? НОД чисел Фибоначчи выражается через НОД индексов. Нетривиальное тождество.
2. Ключевая идея: достаточно доказать, что $\gcd(F_m, F_n) = \gcd(F_{m \bmod n}, F_n)$ — это аналог алгоритма Евклида для индексов.
3. Ключевое тождество Фибоначчи: $F_{m+n} = F_m F_{n+1} + F_{m-1} F_n$. Из него следует $F_m = F_{m-n} F_{n+1} + F_{m-n-1} F_n$ при $m > n$, значит $\gcd(F_m, F_n) = \gcd(F_{m-n}, F_n)$.
4. Итог: применяя это рекурсивно, получаем $\gcd(F_m, F_n) = F_{\gcd(m,n)}$.

Решение:$

*$Лемма:* $\gcd(F_m, F_n) = \gcd(F_{m-n}, F_n)$ при $m > n$.

Доказательство леммы: из тождества $F_m = F_{m-n} F_{n+1} + F_{m-n-1} F_n$ следует, что любой общий делитель $F_m$ и $F_n$ делит $F_{m-n} F_{n+1}$. Так как $\gcd(F_{n+1}, F_n) = 1$ (соседние числа Фибоначчи взаимно просты), любой делитель $F_n$ взаимно прост с $F_{n+1}$, значит общий делитель $F_m$ и $F_n$ делит $F_{m-n}$. Аналогично в обратную сторону.

Поэтому $\gcd(F_m, F_n) = \gcd(F_n, F_{m \bmod n})$ — алгоритм Евклида на индексах. База: $\gcd(F_n, F_0) = \gcd(F_n, 0) = F_n$. Итого: $\gcd(F_m, F_n) = F_{\gcd(m,n)}$. $\square$

Ответ: доказано.

Что было главным: перенести алгоритм Евклида с самих чисел Фибоначчи на их индексы через специальное тождество.

• Ошибка: при вычислении $\gcd(f(n), g(n))$ подставлять конкретные числа, а не работать в общем виде. Почему неверно: для разных $n$ результат разный. Как избежать: применяй алгоритм Евклида к выражениям: $f(n) = q(n) \cdot g(n) + r(n)$, $\gcd(f, g) = \gcd(g, r)$.
• Ошибка: считать, что $\text{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}$ работает для трёх и более чисел. Почему неверно: $\text{lcm}(a, b, c) \neq \frac{abc}{\gcd(a,b,c)}$. Как избежать: для трёх чисел: $\text{lcm}(a, b, c) = \text{lcm}(\text{lcm}(a, b), c)$.
• Ошибка: утверждать $\gcd(a, b) = 1$ без явного обоснования. Почему неверно: взаимная простота — утверждение, требующее доказательства. Как избежать: найди конкретные $x, y$ из тождества Безу или используй алгоритм Евклида.
• Ошибка: из $a \mid bc$ и $a \mid b$ делать вывод $a \mid c$ без проверки $\gcd(a, b) = 1$. Почему неверно: лемма Евклида требует взаимной простоты. Как избежать: сначала докажи $\gcd(a, b) = 1$, только потом применяй лемму.
• Ошибка: путать НОД и НОК в формуле $\gcd \cdot \text{lcm} = a \cdot b$. Почему неверно: перепутав, получишь неверный ответ. Как избежать: запомни мнемонику: НОД «маленький», НОК «большой»; их произведение равно произведению чисел.