Глава
Теория
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\)?
Примеры
Первое прямое применение 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 разложение было бы очень длинным.
Показывает случай \(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\).
Комментарий. Важно, что показатель чётен.
Отдельная формула для двоек.
Задача. Найдите \(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\) отличается от нечётного случая.
Показывает, как 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\).
Показывает переход от \(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\).
Комментарий. Сначала считаем простой показатель, потом учитываем составное основание.
Готовит к задачам с ответом через \(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\).
Учит находить все \(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)\).
Олимпиадный шаблон для \(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\).
Комментарий. Очень частая подзадача в сильных примерах.
Задачи
Найдите \(v_3(10^{2025}-1)\).
Используйте \(3\mid10-1\).
По LTE \(v_3(10^{2025}-1)=v_3(10-1)+v_3(2025)=v_3(9)+4=2+4=6\).
Найдите \(v_7(8^{100}-1)\).
\(7\mid8-1\).
По LTE \(v_7(8^{100}-1)=v_7(7)+v_7(100)=1+0=1\).
Найдите \(v_5(6^{50}-1)\).
\(5\mid6-1\).
\(v_5(6^{50}-1)=v_5(5)+v_5(50)=1+2=3\).
Найдите \(v_3(2^{100}-1)\).
\(3\mid2+1\), а \(100\) чётно.
Так как \(3\mid2+1\) и \(100\) чётно, \(v_3(2^{100}-1)=v_3(3)+v_3(100)=1\).
Найдите \(v_2(3^{100}-1)\).
Используйте формулу для \(p=2\).
\(v_2(3^{100}-1)=v_2(2)+v_2(4)+v_2(100)-1=1+2+2-1=4\).
Найдите все натуральные \(n\), для которых \(7^3\mid8^n-1\).
Посчитайте \(v_7(8^n-1)\).
\(v_7(8^n-1)=1+v_7(n)\). Нужно \(1+v_7(n)\ge3\), то есть \(v_7(n)\ge2\). Ответ: все \(n\), кратные \(49\).
Найдите наибольшее \(k\), для которого \(9^k\mid10^{2025}-1\).
Сначала найдите \(v_3\).
Из задачи 1 \(v_3(10^{2025}-1)=6\). Так как \(9^k=3^{2k}\), получаем \(2k\le6\), значит \(k=3\).
Найдите \(v_5(11^n-1)\).
\(5\mid11-1\).
По LTE \(v_5(11^n-1)=v_5(10)+v_5(n)=1+v_5(n)\).
Найдите \(v_3(4^n-1)\).
\(3\mid4-1\).
\(v_3(4^n-1)=v_3(3)+v_3(n)=1+v_3(n)\).
Найдите \(v_3(5^{2n}-1)\).
\(3\mid5+1\), показатель \(2n\) чётен.
По случаю \(a+b\): \(v_3(5^{2n}-1)=v_3(6)+v_3(2n)=1+v_3(n)\).
Найдите \(v_2(5^n-1)\) в зависимости от чётности \(n\).
Для нечётного \(n\) используйте разложение по \(5-1\); для чётного - формулу для \(2\).
Если \(n\) нечётно, то \(v_2(5^n-1)=v_2(5-1)=2\). Если \(n\) чётно, то \(v_2(5^n-1)=v_2(4)+v_2(6)+v_2(n)-1=2+1+v_2(n)-1=2+v_2(n)\).
Найдите все \(n\), для которых \(16\mid3^n-1\).
Разберите чётность \(n\).
Если \(n\) нечётно, \(v_2(3^n-1)=v_2(2)=1\), не хватает. Если \(n\) чётно, то \(v_2(3^n-1)=v_2(2)+v_2(4)+v_2(n)-1=2+v_2(n)\). Нужно \(2+v_2(n)\ge4\), то есть \(v_2(n)\ge2\). Ответ: \(4\mid n\).
Найдите все \(n\), для которых \(3^5\mid4^n-1\).
Используйте \(v_3(4^n-1)=1+v_3(n)\).
Нужно \(1+v_3(n)\ge5\), то есть \(v_3(n)\ge4\). Ответ: \(81\mid n\).
Пусть \(p\) - нечётный простой, \(p\mid a-b\), \(p\nmid ab\). Докажите, что \(p^r\mid a^{p^{r-1}}-b^{p^{r-1}}\) для любого \(r\ge1\).
Примените LTE к показателю \(p^{r-1}\).
По LTE \(v_p(a^{p^{r-1}}-b^{p^{r-1}})=v_p(a-b)+v_p(p^{r-1})\). Так как \(p\mid a-b\), первое слагаемое не меньше \(1\), а второе равно \(r-1\). Итого показатель не меньше \(r\), значит делимость на \(p^r\) доказана.
Найдите наибольшее \(k\), для которого \(3^k\mid2^{2n}-1\).
Замените \(2^{2n}\) на \(4^n\).
\(2^{2n}-1=4^n-1\). Так как \(3\mid4-1\), \(v_3(4^n-1)=1+v_3(n)\). Следовательно, \(k=1+v_3(n)\).
Найдите \(v_3(13^n-1)\).
\(3\mid13-1\).
По LTE \(v_3(13^n-1)=v_3(12)+v_3(n)=1+v_3(n)\).
Найдите все натуральные \(n\), для которых \(3^n\mid10^n-1\).
Сравните \(n\) с \(v_3(10^n-1)\).
По LTE \(v_3(10^n-1)=v_3(9)+v_3(n)=2+v_3(n)\). Нужно \(2+v_3(n)\ge n\). Проверяем: \(n=1,2,3\) подходят. Если \(n\ge4\), то \(v_3(n)\le n-3\) с большим запасом; точнее \(2+v_3(n)
Найдите все натуральные \(n\), для которых \(7^n\mid8^n-1\).
Используйте \(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
Пусть \(p\) - нечётный простой, \(p\mid a-b\), \(p^2\nmid a-b\), \(p\nmid ab\). Докажите, что \(p^r\mid a^n-b^n\) тогда и только тогда, когда \(p^{r-1}\mid n\).
При данных условиях \(v_p(a-b)=1\).
По LTE \(v_p(a^n-b^n)=v_p(a-b)+v_p(n)=1+v_p(n)\). Делимость \(p^r\mid a^n-b^n\) равносильна \(1+v_p(n)\ge r\), то есть \(v_p(n)\ge r-1\). Это равносильно \(p^{r-1}\mid n\).
Докажите, что при \(m\ge1\) выполнено \(v_2(3^{2^m}-1)=m+2\).
Примените формулу LTE для \(p=2\), \(a=3\), \(b=1\), \(n=2^m\).
\(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\).
Лестницы