LTE-лемма

Лемма о поднятии экспоненты (lifting-the-exponent lemma, LTE-лемма) — утверждение элементарной теории чисел, позволяющее найти наибольшую степень ${\displaystyle \nu _{p}}$ простого числа ${\displaystyle p}$, делящего целые числа специального вида. Наибольшее распространение получила в среде математических олимпиад. Связана с леммой Гензеля.

Обозначим через ${\displaystyle \nu _{p}(m)}$ наибольшую степень простого числа ${\displaystyle p}$, делящего ${\displaystyle m}$ (т.е. степень ${\displaystyle p}$ в разложении ${\displaystyle m}$ на простые множители).

Для любых целых чисел ${\displaystyle x}$ и ${\displaystyle y}$, положительного целого ${\displaystyle n}$ и простого числа ${\displaystyle p}$ таких, что ${\displaystyle p\nmid x}$ и ${\displaystyle p\nmid y}$, выполнено:

• для нечётного ${\displaystyle p}$:
  • если ${\displaystyle p\mid x-y}$, то ${\displaystyle \nu _{p}(x^{n}-y^{n})=\nu _{p}(x-y)+\nu _{p}(n)}$
  • если ${\displaystyle p\mid x+y}$ и ${\displaystyle n}$ нечётное, то ${\displaystyle \nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)+\nu _{p}(n)}$
  • если ${\displaystyle p\mid x+y}$ и ${\displaystyle n}$ чётное, то ${\displaystyle \nu _{p}(x^{n}+y^{n})=0}$
• для ${\displaystyle p=2}$:
  • если ${\displaystyle 2\mid x-y}$ и ${\displaystyle n}$ чётное, то ${\displaystyle \nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y)+\nu _{2}(x+y)+\nu _{2}(n)-1=\nu _{2}\left({\frac {x^{2}-y^{2}}{2}}\right)+\nu _{2}(n)}$
  • если ${\displaystyle 2\mid x-y}$ и ${\displaystyle n}$ нечётное, то ${\displaystyle \nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y)}$
  • следствия:
    • если ${\displaystyle 4\mid x-y}$ и ${\displaystyle x}$ и ${\displaystyle y}$ оба нечётные, то ${\displaystyle \nu _{2}(x+y)=1}$ и, следовательно, ${\displaystyle \nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y)+\nu _{2}(n)}$
    • если ${\displaystyle 2\mid x+y}$ и ${\displaystyle n}$ чётное, то ${\displaystyle \nu _{2}(x^{n}+y^{n})=1}$
    • если ${\displaystyle 2\mid x+y}$ и ${\displaystyle n}$ нечётное, то ${\displaystyle \nu _{2}(x^{n}+y^{n})=\nu _{2}(x+y)}$
• для всех ${\displaystyle p}$:
  • если ${\displaystyle p\mid x-y}$ и ${\displaystyle p\nmid n}$, то ${\displaystyle \nu _{p}(x^{n}-y^{n})=\nu _{p}(x-y)}$
  • если ${\displaystyle p\mid x+y}$, ${\displaystyle p\nmid n}$ и ${\displaystyle n}$ нечётное, то ${\displaystyle \nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)}$

• Лемма Гензеля

• Amir Hossein Parvardi, Lifting The Exponent Lemma (LTE)
• П. Кожевников, LTE-лемма и рекурренты, Квант, 2022, № 8, 8-12, 18