D7 LTE (Lifting the Exponent)

Метод состоит в точном вычислении показателя вхождения простого числа $p$ в разложение выражений вида $a^n \pm b^n$. Лемма LTE (Lifting the Exponent) даёт формулу для $v_p(a^n \pm b^n)$ через $v_p(a \pm b)$ и $v_p(n)$, где $v_p(x)$ — показатель наивысшей степени $p$, делящей $x$.

Интуиция: если хочешь узнать, сколько раз $5$ делит $2024^{100} - 1$, нужна точная «счётная» формула, а не оценка. LTE — это именно такая формула. Она «поднимает» информацию о делимости $a - b$ на $p$ до информации о делимости $a^n - b^n$ на $p$.

Метод находится на стыке алгебраических тождеств и $p$-адической теории. Он применяется в задачах высшей сложности, где требуется точно определить степень делимости (а не просто факт делимости). LTE существенно экономит вычисления: без него такие задачи требуют громоздкого анализа модулей высоких степеней $p$.

• LTE для $p$ нечётного, $p \mid a - b$, $p \nmid a$, $p \nmid b$:$v_p(a^n - b^n) = v_p(a - b) + v_p(n).$ Условие: $p$ нечётное простое, $p \mid a - b$, $p \nmid a$, $p \nmid b$. Когда использовать: при вычислении $v_p(a^n - b^n)$.

• LTE для $p = 2$, $2 \mid a - b$:$$v_2(a^n - b^n) = v_2(a - b) + v_2(a + b) + v_2(n) - 1.$$ Условие: $n$ чётное, $2 \mid a - b$ (то есть $a$ и $b$ одной чётности$). *$Когда использовать:* при работе по модулю степени двойки.

• LTE для суммы, $p$ нечётный, $p \mid a + b$:$$v_p(a^n + b^n) = v_p(a + b) + v_p(n),\quad n \text{ нечётное}.$$ Условие: $p$ нечётное, $p \mid a + b$, $p \nmid a$, $p \nmid b$, $n$ нечётное.

• Связь с $v_p$: $v_p(ab) = v_p(a) + v_p(b)$; $v_p(a + b) \geq \min(v_p(a), v_p(b))$ (равенство при $v_p(a) \neq v_p(b)$$). *$Когда использовать:* при разложении выражений на множители для применения LTE.

• Проверить условия LTE перед применением. $p \nmid a$, $p \nmid b$, $p \mid a \mp b$ — все три условия обязательны. Запиши проверку явно.

• Выбор простого $p$. Анализируй, какое $p$ делит $a - b$ или $a + b$, и применяй LTE для этого $p$.

• Разложение $n$ на простые. Поскольку $v_p(n)$ входит в формулу, разложи $n$ на простые множители заранее.

• Комбинирование LTE с оценками делимости. Вычисли $v_p$ для каждого простого делителя отдельно, затем сравни с требуемой степенью.

• Работа с уравнениями через LTE. Если задано равенство $a^n - b^n = p^k \cdot c$, приравняй $v_p$ обеих сторон и применяй формулу LTE.

Поверхностные признаки (что буквально написано):
- «Докажите, что $p^k \mid a^n - b^n$» или «найдите $v_p(a^n - 1)$»
- «При каких $n$ выражение $a^n - 1$ делится на $p^k$, но не на $p^{k+1}$?»
- «Найдите все натуральные $n$, при которых $2^n - 1$ делится на $n$»

Структурные признаки (форма выражения, объекты):
- В задаче стоит $a^n - b^n$ или $a^n + b^n$ с конкретными $a$, $b$ и переменным $n$ - Требуется точная степень делимости (не просто «делится»)
- В условии задачи присутствует $v_p$ или подобное обозначение степени вхождения

Цель задачи (что от тебя хотят):
- Точно вычислить показатель степени простого в делении выражения
- Доказать делимость на конкретную степень простого
- Решить уравнение в натуральных числах, включающее степени

Задача 1. Найдите все натуральные числа $n$, такие что $3^n - 1$ делится на $2^n$.

Источник: тренировочная задача (стандартный тип LTE)

Как думать (рассуждение ученика$):
1. $Что вижу?* $2^n \mid 3^n - 1$. Это делимость на степень $2$. Нужно $v_2(3^n - 1) \geq n$. Это классический запрос LTE!$2. *$Применяю LTE для $p = 2$: $a = 3$, $b = 1$. $2 \mid 3 - 1 = 2$ ✓, $2 \nmid 3$ ✓, $2 \nmid 1$ ✓.
3. При нечётном $n$: формула $v_2(3^n - 1^n) = v_2(3 - 1) + v_2(n) = 1 + v_2(n) = 1 + 0 = 1$. Нужно $1 \geq n$, то есть $n = 1$.
4. При чётном $n$: $v_2(3^n - 1) = v_2(3-1) + v_2(3+1) + v_2(n) - 1 = 1 + 2 + v_2(n) - 1 = 2 + v_2(n)$. Нужно $2 + v_2(n) \geq n$.

Решение:

Нужно $v_2(3^n - 1) \geq n$.

Случай 1: $n$ нечётное. По LTE: $v_2(3^n - 1) = v_2(2) + v_2(n) = 1 + 0 = 1$. Нужно $1 \geq n$, то есть $n = 1$. Проверка: $3^1 - 1 = 2 = 2^1$ ✓.

Случай 2: $n$ чётное. $v_2(3^n - 1) = v_2(3-1) + v_2(3+1) + v_2(n) - 1 = 1 + 2 + v_2(n) - 1 = 2 + v_2(n)$. Нужно $2 + v_2(n) \geq n$. Пусть $n = 2^k \cdot m$, $m$ нечётное. Тогда $v_2(n) = k$ и $n \geq 2^k$. Нужно $2 + k \geq 2^k m \geq 2^k$:
- $k = 1$: $3 \geq 2m$, $m = 1$, $n = 2$ ✓.
- $k = 2$: $4 \geq 4m$, $m = 1$, $n = 4$ ✓.
- $k = 3$: $5 \geq 8m$ — невозможно.

Ответ: $n \in \{1, 2, 4\}$.

Что в этой задаче было главным: LTE для $p = 2$ при чётном показателе — формула с тремя слагаемыми, не забудь $-1$.

Задача 2. Докажите, что $5^{2n+1} + 11^{2n+1} + 17^{2n+1}$ делится на $33$ для любого натурального $n$.

Источник: тренировочная

Как думать (рассуждение ученика$):
1. $Что вижу?* $33 = 3 \cdot 11$. Нужна делимость на $3$ и на $11$ по отдельности.$2. *$По модулю $3$: $5 \equiv 2$, $11 \equiv 2$, $17 \equiv 2 \pmod 3$. Сумма $\equiv 3 \cdot 2^{2n+1} \equiv 0 \pmod 3$.$3. *$По модулю $11$:* $17 \equiv 6 \equiv -5 \pmod{11}$. Показатель $2n+1$ нечётный, значит $5^{2n+1} + (-5)^{2n+1} = 0$. И $11^{2n+1} \equiv 0 \pmod{11}$.

Решение:$

*$Делимость на $3$:* $5 \equiv 11 \equiv 17 \equiv 2 \pmod 3$. Поэтому $5^{2n+1} + 11^{2n+1} + 17^{2n+1} \equiv 3 \cdot 2^{2n+1} \equiv 0 \pmod 3$.

Делимость на $11$: $17 \equiv 6 \equiv -5 \pmod{11}$. Поскольку $2n+1$ нечётное:$$5^{2n+1} + 17^{2n+1} \equiv 5^{2n+1} + (-5)^{2n+1} = 0 \pmod{11}.$$ И $11^{2n+1} \equiv 0 \pmod{11}$. Итого сумма $\equiv 0 \pmod{11}$.

Так как $\gcd(3, 11) = 1$, сумма делится на $33$.

Ответ: делится на $33$ для любого натурального $n$.

Что в этой задаче было главным: формула $a^n + b^n = (a+b)(\ldots)$ при нечётном $n$ — и замечание $17 \equiv -5 \pmod{11}$.

• Ошибка: применять LTE, не проверив $p \nmid a$ и $p \nmid b$. → Почему неверно: если $p \mid a$, то $v_p(a^n - b^n) = v_p(-b^n)$ и формула LTE неприменима. → Как избежать: всегда проверяй оба условия в явном виде.

• Ошибка: использовать LTE при $p = 2$ без поправки $-1$ в формуле. → Почему неверно: для $p = 2$ формула: $v_2(a^n - b^n) = v_2(a-b) + v_2(a+b) + v_2(n) - 1$, а не просто $v_2(a-b) + v_2(n)$. → Как избежать: выпиши формулу для $p=2$ отдельно и не забывай $-1$.

• Ошибка: применять формулу для нечётного $p$ к $a^n + b^n$ при чётном $n$. → Почему неверно: формула $v_p(a^n + b^n) = v_p(a+b) + v_p(n)$ требует $n$ нечётного. → Как избежать: чётность $n$ — всегда первый вопрос при применении LTE.

• Ошибка: путать $v_p(a^n - b^n)$ при $p \nmid a - b$ (тогда LTE неприменим). → Почему неверно: LTE требует $p \mid a - b$. Если $p \nmid a - b$, то $v_p(a^n - b^n) = 0$ или нужна другая теорема. → Как избежать: первый шаг — проверить $p \mid a - b$.