Лемма о поднятии экспоненты - Lifting-the-exponent lemma - Wikipedia

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

Фон

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

Заявления

Для любых целых чисел ${\displaystyle x,y}$ и положительные целые числа ${\displaystyle n}$ и ${\displaystyle p}$, куда ${\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 n}$ это странно и ${\displaystyle p\mid x+y}$, ${\displaystyle \nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)+\nu _{p}(n)}$.
• Когда ${\displaystyle p=2}$:
  • Если ${\displaystyle 4\mid x-y}$, ${\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})=\nu _{2}(x-y)+\nu _{2}(x+y)+\nu _{2}(n)-1}$.
• Для всех ${\displaystyle p}$:
  • Если ${\displaystyle \gcd(n,p)=1}$ и ${\displaystyle p\mid x-y}$, ${\displaystyle \nu _{p}(x^{n}-y^{n})=\nu _{p}(x-y)}$.
  • Если ${\displaystyle \gcd(n,p)=1}$, ${\displaystyle p\mid x+y}$ и ${\displaystyle n}$ странный, ${\displaystyle \nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)}$.

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

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

Базовый случай ${\displaystyle \nu _{p}(x^{n}-y^{n})=\nu _{p}(x-y)}$ когда ${\displaystyle \gcd(n,p)=1}$ доказано первым. Потому что ${\displaystyle p\mid x-y\iff x\equiv 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}=(x-y)(x^{n-1}+x^{n-2}y+x^{n-3}y^{2}+\dots +y^{n-1})}$ завершает доказательство. Условие ${\displaystyle \nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)}$ для нечетных ${\displaystyle n}$ похож.

Общий случай (нечетный п)

Через биномиальное разложение, замена ${\displaystyle y=x+kp}$ можно использовать в (1), чтобы показать, что ${\displaystyle \nu _{p}(x^{p}-y^{p})=\nu _{p}(x-y)+1}$ потому что (1) кратно ${\displaystyle p}$ но нет ${\displaystyle p^{2}}$.^[1] Так же, ${\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 a}$,

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

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

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

Доказательство странного ${\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}(x-y)+\nu _{2}(n)}$ когда ${\displaystyle 4\mid x-y}$ написав ${\displaystyle n=2^{a}b}$ куда ${\displaystyle a}$ и ${\displaystyle b}$ целые числа с ${\displaystyle b}$ странно и отмечая, что

${\displaystyle {\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}}}$

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

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

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

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

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

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

Решение. Обратите внимание, что ${\displaystyle 149-2=147=3\cdot 7^{2}}$. Используя лемму LTE, поскольку ${\displaystyle 3\nmid 149}$ и ${\displaystyle 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}$.

С ${\displaystyle 5\nmid 147}$, множители 5 обращаются, замечая, что, поскольку остатки ${\displaystyle 149^{n}}$ по модулю 5 следовать циклу ${\displaystyle 4,1,4,1}$ и те из ${\displaystyle 2^{n}}$ следовать циклу ${\displaystyle 2,4,3,1}$, остатки ${\displaystyle 149^{n}-2^{n}}$ по модулю 5 цикл по последовательности ${\displaystyle 2,2,1,0}$. Таким образом, ${\displaystyle 5\mid 149^{n}-2^{n}}$ если только ${\displaystyle n=4k}$ для некоторого положительного целого числа ${\displaystyle k}$. Теперь можно снова применить лемму LTE: ${\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}$ положительные делители.

Рекомендации

1. Паварди, А. Х. (2011). Поднятие леммы об экспоненте (LTE). Получено 11 июля 2020 г., из http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.221.5543 (Примечание: старая ссылка на статью не работает; попробуйте https://s3.amazonaws.com/aops-cdn.artofproblemsolving.com/resources/articles/lifting-the-exponent.pdf вместо.)
2. Гаусс, К. (1801) Disquisitiones arithmeticae. Результаты показаны в статьях 86–87. https://gdz.sub.uni-goettingen.de/id/PPN235993352?tify={%22pages%22%3A%5B70%5D}
3. Геречлегер, Р. (2020). Привлечение молодых студентов к математике через соревнования - Мировые перспективы и практика. World Scientific. https://books.google.com/books?id=FNPkDwAAQBAJ&lpg=PA3&ots=rkjtruFbsM&lr&pg=PP1
4. Хойбергер, К. и Маццоли, М. (2017). Эллиптические кривые с изоморфными группами точек над конечными расширениями поля. Журнал теории чисел, 181, 89–98. https://doi.org/10.1016/j.jnt.2017.05.028
5. 2020 AIME I. Проблемы. (2020). Искусство решения проблем. Получено 11 июля 2020 г., из https://artofproblemsolving.com/wiki/index.php/2020_AIME_I_Problems