Lemma zvedání exponentu - Lifting-the-exponent lemma - Wikipedia

V základní teorie čísel, lemma zvedání exponentu (LTE) poskytuje několik vzorců pro výpočet ocenění p-adic ${ displaystyle nu _ {p}}$ speciálních forem celých čísel. Lema je pojmenována jako taková, protože popisuje kroky nutné ke „zvednutí“ exponentu ${ displaystyle p}$ v takových výrazech. Souvisí to s Henselův lemma.

Pozadí

Přesný původ LTE lemmatu je nejasný; výsledek se svým současným názvem a formou se dostal do centra pozornosti pouze za posledních 10 až 20 let.^[1] Bylo však známo několik klíčových myšlenek použitých v jeho důkazu Gauss a odkazoval se na jeho Disquisitiones Arithmeticae.^[2] Přes hlavně vystupovat v matematické olympiády, někdy se aplikuje na výzkumná témata, jako např eliptické křivky.^[3][4]

Prohlášení

Pro všechna celá čísla ${ displaystyle x, y}$ a kladná celá čísla ${ displaystyle n}$ a ${ displaystyle p}$, kde ${ displaystyle p}$ je takovým prvkem ${ displaystyle p nmid x}$ a ${ displaystyle p nmid y}$, platí tyto identity:

• Když ${ displaystyle p}$ je liché:
  • Li ${ displaystyle p mid x-y}$, ${ displaystyle nu _ {p} (x ^ {n} -y ^ {n}) = nu _ {p} (x-y) + nu _ {p} (n)}$.
  • Li ${ displaystyle n}$ je liché a ${ displaystyle p mid x + y}$, ${ displaystyle nu _ {p} (x ^ {n} + y ^ {n}) = nu _ {p} (x + y) + nu _ {p} (n)}$.
• Když ${ displaystyle p = 2}$:
  • Li ${ displaystyle 4 mid x-y}$, ${ displaystyle nu _ {2} (x ^ {n} -y ^ {n}) = nu _ {2} (x-y) + nu _ {2} (n)}$.
  • Li ${ displaystyle 2 mid x-y}$ a ${ displaystyle n}$ je dokonce, ${ displaystyle nu _ {2} (x ^ {n} -y ^ {n}) = nu _ {2} (xy) + nu _ {2} (x + y) + nu _ {2 } (n) -1}$.
• Pro všechny ${ displaystyle p}$:
  • Li ${ displaystyle gcd (n, p) = 1}$ a ${ displaystyle p mid x-y}$, ${ displaystyle nu _ {p} (x ^ {n} -y ^ {n}) = nu _ {p} (x-y)}$.
  • Li ${ displaystyle gcd (n, p) = 1}$, ${ displaystyle p mid x + y}$ a ${ displaystyle n}$ zvláštní, ${ displaystyle nu _ {p} (x ^ {n} + y ^ {n}) = nu _ {p} (x + y)}$.

Nástin důkazu

Základní případ

Základní případ ${ displaystyle nu _ {p} (x ^ {n} -y ^ {n}) = nu _ {p} (x-y)}$ když ${ displaystyle gcd (n, p) = 1}$ je prokázáno jako první. Protože ${ 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)}$

Skutečnost, že ${ displaystyle x ^ {n} -y ^ {n} = (xy) (x ^ {n-1} + x ^ {n-2} y + x ^ {n-3} y ^ {2} + tečky + y ^ {n-1})}$ doplňuje důkaz. Kondice ${ displaystyle nu _ {p} (x ^ {n} + y ^ {n}) = nu _ {p} (x + y)}$ pro liché ${ displaystyle n}$ je podobný.

Obecný případ (lichý p)

Přes binomická expanze, střídání ${ displaystyle y = x + kp}$ lze použít v (1) k prokázání toho ${ displaystyle nu _ {p} (x ^ {p} -y ^ {p}) = nu _ {p} (x-y) +1}$ protože (1) je násobkem ${ displaystyle p}$ ale ne ${ displaystyle p ^ {2}}$.^[1] Rovněž, ${ displaystyle nu _ {p} (x ^ {p} + y ^ {p}) = nu _ {p} (x + y) +1}$.

Pak, pokud ${ displaystyle n}$ je psán jako ${ displaystyle p ^ {a} b}$ kde ${ displaystyle p nmid b}$, uvádí základní případ ${ 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}})}$. Indukcí dne ${ 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 {(umocňování) used}} a { text {krát za semestr)}} & = nu _ {p} (xy) + a end {zarovnáno}}}$

Lze použít podobný argument ${ displaystyle nu _ {p} (x ^ {n} + y ^ {n})}$.

Obecný případ (p = 2)

Důkaz pro liché ${ displaystyle p}$ případ nelze přímo použít, když ${ displaystyle p = 2}$ protože binomický koeficient ${ displaystyle { binom {p} {2}} = { frac {p (p-1)} {2}}}$ je pouze integrální násobek ${ displaystyle p}$ když ${ displaystyle p}$ je zvláštní.

Je však možné ukázat, že ${ displaystyle nu _ {2} (x ^ {n} -y ^ {n}) = nu _ {2} (x-y) + nu _ {2} (n)}$ když ${ displaystyle 4 mid x-y}$ písemně ${ displaystyle n = 2 ^ {a} b}$ kde ${ displaystyle a}$ a ${ displaystyle b}$ jsou celá čísla s ${ displaystyle b}$ zvláštní a poznamenávám to

${ displaystyle { begin {zarovnáno} 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 {zarovnáno}}}$

protože od té doby ${ displaystyle x equiv y equiv pm 1 { pmod {4}}}$, každý faktor v rozdílu čtverců krok ve formě ${ displaystyle x ^ {2 ^ {k}} + y ^ {2 ^ {k}}}$ je shodný s 2 modulo 4.

Silnější prohlášení ${ displaystyle nu _ {2} (x ^ {n} -y ^ {n}) = nu _ {2} (xy) + nu _ {2} (x + y) + nu _ {2 } (n) -1}$ když ${ displaystyle 2 mid x-y}$ je prokázáno analogicky.^[1]

V soutěžích

Příklad problému

Lemma LTE lze použít k řešení roku 2020 AIME I # 12:

Nechat ${ displaystyle n}$ být nejméně kladné celé číslo, pro které ${ displaystyle 149 ^ {n} -2 ^ {n}}$ je dělitelné ${ displaystyle 3 ^ {3} cdot 5 ^ {5} cdot 7 ^ {7}.}$ Najděte počet kladných celých dělitelů čísla ${ displaystyle n}$.^[5]

Řešení. Všimněte si, že ${ displaystyle 149-2 = 147 = 3 cdot 7 ^ {2}}$. Používání LTE lemmatu, protože ${ displaystyle 3 nmid 149}$ a ${ displaystyle 2}$ ale ${ displaystyle 3 mid 147}$, ${ displaystyle nu _ {3} (149 ^ {n} -2 ^ {n}) = nu _ {3} (147) + nu _ {3} (n) = nu _ {3} ( n) +1}$. Tím pádem, ${ displaystyle 3 ^ {3} střední 149 ^ {n} -2 ^ {n} iff 3 ^ {2} střední n}$. Podobně, ${ displaystyle 7 nmid 149,2}$ ale ${ displaystyle 7 mid 147}$, tak ${ displaystyle nu _ {7} (149 ^ {n} -2 ^ {n}) = nu _ {7} (147) + nu _ {7} (n) = nu _ {7} ( n) +2}$ a ${ displaystyle 7 ^ {7} střední 149 ^ {n} -2 ^ {n} iff 7 ^ {5} střední n}$.

Od té doby ${ displaystyle 5 nmid 147}$, faktory 5 jsou řešeny povšimnutím, že od zbytků ${ displaystyle 149 ^ {n}}$ modulo 5 následovat cyklus ${ displaystyle 4,1,4,1}$ a ti z ${ displaystyle 2 ^ {n}}$ sledujte cyklus ${ displaystyle 2,4,3,1}$, resiudes of ${ displaystyle 149 ^ {n} -2 ^ {n}}$ modulo 5 prochází sekvencí ${ displaystyle 2,2,1,0}$. Tím pádem, ${ displaystyle 5 mid 149 ^ {n} -2 ^ {n}}$ iff ${ displaystyle n = 4k}$ pro nějaké kladné celé číslo ${ displaystyle k}$. Lema LTE lze nyní znovu použít: ${ displaystyle nu _ {5} (149 ^ {4k} -2 ^ {4k}) = nu _ {5} ((149 ^ {4}) ^ {k} - (2 ^ {4}) ^ {k}) = nu _ {5} (149 ^ {4} -2 ^ {4}) + nu _ {5} (k)}$. Od té doby ${ displaystyle 149 ^ {4} -2 ^ {4} equiv (-1) ^ {4} -2 ^ {4} equiv -15 { pmod {25}}}$, ${ displaystyle nu _ {5} (149 ^ {4} -2 ^ {4}) = 1}$. Proto ${ displaystyle 5 ^ {5} střední 149 ^ {n} -2 ^ {n} iff 5 ^ {4} střední k iff 4 cdot 5 ^ {4} střední n}$.

Kombinací těchto tří výsledků se zjistilo, že ${ displaystyle n = 2 ^ {2} cdot 3 ^ {2} cdot 5 ^ {4} cdot 7 ^ {5}}$, který má ${ displaystyle (2 + 1) (2 + 1) (4 + 1) (5 + 1) = 270}$ kladné dělitele.

Reference