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

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

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

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

Базовый случай ${ displaystyle nu _ {p} (x ^ {n} -y ^ {n}) = nu _ {p} (x-y)}$ когда ${ Displaystyle НОД (п, р) = 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} = (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}$ похож.

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

Через биномиальное разложение, замена ${ 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 {align} nu _ {p} (x ^ {p ^ {a}} - y ^ {p ^ {a}}) & = nu _ {p} ((( точки ( x ^ {p}) ^ {p} dots)) ^ {p} - (( dots (y ^ {p}) ^ {p} dots)) ^ {p}) { text {(возведение в степень used}} a { text {раз за термин)}} & = nu _ {p} (xy) + a end {align}}}

Аналогичный аргумент можно применить для ${ Displaystyle ню _ {р} (х ^ {п} + у ^ {п})}$ .

Общий случай (п = 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 середина х-у}$ написав ${ Displaystyle п = 2 ^ {а} б}$ куда ${ displaystyle a}$ и ${ displaystyle b}$ целые числа с ${ displaystyle b}$ странно и отмечая, что

{ 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 конец {выровнено}}}

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

Более сильное заявление ${ displaystyle nu _ {2} (х ^ {n} -y ^ {n}) = nu _ {2} (xy) + 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} ( п) +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} ( п) +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 ^ {п}}$ следовать циклу ${ 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 п = 2 ^ {2} cdot 3 ^ {2} cdot 5 ^ {4} cdot 7 ^ {5}}$ , у которого есть ${ Displaystyle (2 + 1) (2 + 1) (4 + 1) (5 + 1) = 270}$ положительные делители.