Лемма о поднятии показателя степени

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

Фон

Точное происхождение леммы ЛТР неясно; результат, с его нынешним названием и формой, стал предметом внимания только в последние 10–20 лет. Однако несколько ключевых идей, использованных в его доказательстве, были известны Гауссу и упомянуты в его Disquisitiones Arithmeticae . Несмотря на то, что оно в основном используется в математических олимпиадах , иногда оно применяется к темам исследований, таким как эллиптические кривые .

Заявления

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

• Когда $p$ странно:
  • Если $p\mid x-y$, затем $\nu _{p}(x^{n}-y^{n})=\nu _{p}(x-y)+\nu _{p}(n)$.
  • Если $p\mid x+y$ и $n$ странно, тогда $\nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)+\nu _{p}(n)$.
  • Если $p\mid x+y$ и $n$ четно, тогда $\nu _{p}(x^{n}+y^{n})=0$.
• Когда $p=2$:
  • Если $2\mid x-y$ и $n$ четно, тогда $\nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y)+\nu _{2}(x+y)+\nu _{2}(n)-1$.
  • Если $2\mid x-y$ и $n$ странно, тогда $\nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y)$. (Следует из общего случая, приведенного ниже.)
  • Следствия:
    • Если $4\mid x-y$, затем $\nu _{2}(x+y)=1$ и таким образом $\nu _{2}(x^{n}-y^{n})=\nu _{2}(x-y)+\nu _{2}(n)$.
    • Если $2\mid x+y$ и $n$ четно, тогда $\nu _{2}(x^{n}+y^{n})=1$.
    • Если $2\mid x+y$ и $n$ странно, тогда $\nu _{2}(x^{n}+y^{n})=\nu _{2}(x+y)$.
• Для всех $p$:
  • Если $p\mid x-y$ и $p\nmid n$, затем $\nu _{p}(x^{n}-y^{n})=\nu _{p}(x-y)$.
  • Если $p\mid x+y$, $p\nmid n$ и $n$ странно, тогда $\nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)$.

Обобщения

LTE был обобщен на комплексные значения $x,y$ при условии, что стоимость ${\tfrac {x^{n}-y^{n}}{x-y}}$ является целым числом.

Схема доказательства

Базовый вариант

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

$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)$

Тот факт, что $x^{n}-y^{n}=(x-y)(x^{n-1}+x^{n-2}y+x^{n-3}y^{2}+\dots +y^{n-1})$ завершает доказательство. Состояние $\nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)$ для странных $n$ похож.

Общий случай (нечетное p )

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

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

${\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{(exponentiation used }}a{\text{ times per term)}}\\&=\nu _{p}(x-y)+a\end{aligned}}$

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

Общий случай ( р = 2)

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

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

${\begin{aligned}\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)(x-y))\\&=\nu _{2}(x-y)+a\end{aligned}}$

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

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

В соревнованиях

Пример проблемы

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

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

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

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

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