Лемма о подъеме экспоненты

В элементарной теории чисел лемма о подъеме экспоненты ( лемма ЛТЕ ) дает несколько формул для вычисления p-адической оценки специальных форм целых чисел. Лемма так названа, потому что она описывает шаги, необходимые для «подъема» экспоненты в таких выражениях. Она связана с леммой Гензеля .${\displaystyle \nu _{p}}$${\displaystyle p}$

Точное происхождение леммы ЛТЭ неясно; результат, с его нынешним названием и формой, оказался в центре внимания только в последние 10–20 лет. ^[1] Однако несколько ключевых идей, использованных в ее доказательстве, были известны Гауссу и упоминались в его Disquisitiones Arithmeticae . ^[2] Несмотря на то, что она в основном фигурирует на математических олимпиадах , ее иногда применяют к исследовательским темам, таким как эллиптические кривые . ^{[3] [4]}

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

• Когда нечетное:${\displaystyle p}$
  • Если , то .${\displaystyle p\mid xy}$${\displaystyle \nu _{p}(x^{n}-y^{n})=\nu _{p}(xy)+\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\середина xy}$${\displaystyle n}$${\displaystyle \nu _{2}(x^{n}-y^{n})=\nu _{2}(xy)+\nu _{2}(x+y)+\nu _{2 }(n)-1=\nu _{2}\left({\frac {x^{2}-y^{2}}{2}}\right)+\nu _{2}(n)}$
  • Если и нечетно, то . (Следует из общего случая ниже.)${\displaystyle 2\середина xy}$${\displaystyle n}$${\displaystyle \nu _{2}(x^{n}-y^{n})=\nu _{2}(xy)}$
  • Следствия:
    • Если , то и таким образом .${\displaystyle 4\середина xy}$${\displaystyle \nu _{2}(x+y)=1}$${\displaystyle \nu _{2}(x^{n}-y^{n})=\nu _{2}(xy)+\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 xy}$${\displaystyle p\nmid n}$${\displaystyle \nu _{p}(x^{n}-y^{n})=\nu _{p}(xy)}$
  • Если , и нечетно, то .${\displaystyle p\mid x+y}$${\displaystyle p\nmid n}$${\displaystyle n}$${\displaystyle \nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)}$

LTE был обобщен до комплексных значений при условии, что значение является целым числом. ^[5]${\displaystyle x,y}$${\displaystyle {\tfrac {x^{n}-y^{n}}{xy}}}$

Базовый случай, когда доказан первым. Потому что ,${\displaystyle \nu _{p}(x^{n}-y^{n})=\nu _{p}(xy)}$${\displaystyle p\nmid n}$${\displaystyle p\mid xy\если x\эквивалент y{\pmod {p}}}$

${\displaystyle x^{n-1}+x^{n-2}y+x^{n-3}y^{2}+\dots +y^{n-1}\equiv nx^{n-1}\not \equiv 0{\pmod {p}}}$

1

Факт, который завершает доказательство. Условие для нечетного аналогично.${\displaystyle x^{n}-y^{n}=(xy)(x^{n-1}+x^{n-2}y+x^{n-3}y^{2}+\ точки +y^{n-1})}$${\displaystyle \nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)}$${\displaystyle n}$

С помощью биномиального разложения можно использовать замену в ( 1 ), чтобы показать, что поскольку ( 1 ) является кратным , но не . ^[1] Аналогично, .${\displaystyle y=x+kp}$${\displaystyle \nu _{p}(x^{p}-y^{p})=\nu _{p}(xy)+1}$${\displaystyle p}$${\displaystyle p^{2}}$${\displaystyle \nu _{p}(x^{p}+y^{p})=\nu _{p}(x+y)+1}$

Тогда, если записывается как , где , базовый случай дает . Индукцией по ,${\displaystyle n}$${\displaystyle p^{a}b}$${\displaystyle p\nmid b}$${\displaystyle \nu _{p}(x^{n}-y^{n})=\nu _{p}((x^{p^{a}})^{b}-(y^{ p^{a}})^{b})=\nu _{p}(x^{p^{a}}-y^{p^{a}})}$${\displaystyle а}$

${\displaystyle {\begin{aligned}\nu _{p}(x^{p^{a}}-y^{p^{a}})&=\nu _{p}(((\dots (x^{p})^{p}\dots ))^{p}-((\dots (y^{p})^{p}\dots ))^{p})\ {\text{(возведение в степень использовано }}a{\text{ раз за член)}}\\&=\nu _{p}(xy)+a\end{aligned}}}$

Аналогичный аргумент можно применить и к .${\displaystyle \nu _{p}(x^{n}+y^{n})}$

Доказательство для нечетного случая нельзя применить напрямую, когда , поскольку биномиальный коэффициент является целым кратным только тогда , когда , является нечетным.${\displaystyle p}$${\displaystyle p=2}$${\displaystyle {\binom {p}{2}}={\frac {p(p-1)}{2}}}$${\displaystyle p}$${\displaystyle p}$

Однако можно показать, что когда, записав , где и — целые числа с нечетным числом, и заметив, что${\displaystyle \nu _{2}(x^{n}-y^{n})=\nu _{2}(xy)+\nu _{2}(n)}$${\displaystyle 4\середина xy}$${\displaystyle n=2^{a}b}$${\displaystyle а}$${\displaystyle б}$${\displaystyle б}$

${\displaystyle {\begin{align}\nu _{2}(x^{n}-y^{n})&=\nu _{2}((x^{2^{a}})^{b}-(y^{2^{a}})^{b})\\&=\nu _{2}(x^{2^{a}}-y^{2^{a}})\\&=\nu _{2}((x^{2^{a-1}}+y^{2^{a-1}})(x^{2^{a-2}}+y^{2^{a-2}})\cdots (x^{2}+y^{2})(x+y)(xy))\\&=\nu _{2}(xy)+a\end{align}}}$

поскольку , каждый множитель в разности квадратов шага в форме сравним с 2 по модулю 4.${\displaystyle x\equiv y\equiv \pm 1{\pmod {4}}}$${\displaystyle x^{2^{k}}+y^{2^{k}}}$

Более сильное утверждение доказывается аналогично. ^[1]${\displaystyle \nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y)+\nu _{2}(x+y)+\nu _{2}(n)-1}$${\displaystyle 2\mid x-y}$

Лемму LTE можно использовать для решения задачи AIME I № 12 2020 года:

Пусть будет наименьшим положительным целым числом, которое делится на Найдите количество положительных целых делителей числа . ^[6]${\displaystyle n}$${\displaystyle 149^{n}-2^{n}}$${\displaystyle 3^{3}\cdot 5^{5}\cdot 7^{7}.}$${\displaystyle n}$

Решение. Обратите внимание, что . Используя лемму ЛТЕ, поскольку и , но , . Таким образом, . Аналогично, но , поэтому и .${\displaystyle 149-2=147=3\cdot 7^{2}}$${\displaystyle 3\nmid 149}$${\displaystyle 3\nmid 2}$${\displaystyle 3\mid 147}$${\displaystyle \nu _{3}(149^{n}-2^{n})=\nu _{3}(147)+\nu _{3}(n)=\nu _{3}(n)+1}$${\displaystyle 3^{3}\mid 149^{n}-2^{n}\iff 3^{2}\mid n}$${\displaystyle 7\nmid 149,2}$${\displaystyle 7\mid 147}$${\displaystyle \nu _{7}(149^{n}-2^{n})=\nu _{7}(147)+\nu _{7}(n)=\nu _{7}(n)+2}$${\displaystyle 7^{7}\mid 149^{n}-2^{n}\iff 7^{5}\mid n}$

Так как , множители 5 рассматриваются, замечая, что поскольку остатки по модулю 5 следуют циклу , а остатки по модулю 5 следуют циклу , остатки по модулю 5 циклируют по последовательности . Таким образом, тогда и только тогда, когда для некоторого положительного целого числа . Теперь лемму ЛТЕ можно применить снова: . Так как , . Следовательно .${\displaystyle 5\nmid 147}$${\displaystyle 149^{n}}$${\displaystyle 4,1,4,1}$${\displaystyle 2^{n}}$${\displaystyle 2,4,3,1}$${\displaystyle 149^{n}-2^{n}}$${\displaystyle 2,2,1,0}$${\displaystyle 5\mid 149^{n}-2^{n}}$${\displaystyle n=4k}$${\displaystyle k}$${\displaystyle \nu _{5}(149^{4k}-2^{4k})=\nu _{5}((149^{4})^{k}-(2^{4})^{k})=\nu _{5}(149^{4}-2^{4})+\nu _{5}(k)}$${\displaystyle 149^{4}-2^{4}\equiv (-1)^{4}-2^{4}\equiv -15{\pmod {25}}}$${\displaystyle \nu _{5}(149^{4}-2^{4})=1}$${\displaystyle 5^{5}\mid 149^{n}-2^{n}\iff 5^{4}\mid k\iff 4\cdot 5^{4}\mid n}$

Объединяя эти три результата, находим, что , имеющее положительные делители.${\displaystyle n=2^{2}\cdot 3^{2}\cdot 5^{4}\cdot 7^{5}}$${\displaystyle (2+1)(2+1)(4+1)(5+1)=270}$