Att lyfta-exponenten lemma

I elementär talteori tillhandahåller lemmat lyft -exponenten (LTE) flera formler för att beräkna den p-adiska värderingen $\nu _{p}$ för speciella former av heltal. Lemmat heter som sådant eftersom det beskriver de steg som krävs för att "lyfta" exponenten för $p$ i sådana uttryck. Det är relaterat till Hensels lemma .

Bakgrund

Det exakta ursprunget till LTE-lemmat är oklart; resultatet, med sitt nuvarande namn och form, har kommit i fokus först under de senaste 10 till 20 åren. Men flera nyckelidéer som användes i dess bevis var kända för Gauss och refererade till i hans Disquisitiones Arithmeticae . Illviljan främst presenterar i matematiska olympiads , appliceras det ibland till forskningsämnen, liksom elliptiska kurvor .

Uttalanden

För alla heltal $x,y$ , ett positivt heltal $n$ och ett primtal $p$ så att $p\nmid x$ och $p\nmid y$ , följande påståenden gäller:

• När $p$ är udda:
  • Om $p\mid xy$ , då $\nu _{p}(x ^{n}-y^{n})=\nu _{p}(xy)+\nu _{p}(n)$ .
  • Om $n$ är udda och $p\mid x+y$ , då är $\nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)+\nu _{p}(n)$ .
• När $p=2$ :
  • Om $2\mid xy$ och $n$ är jämnt, då är $\nu _{2}(x^{n}-y^{n})=\nu _{2}(xy)+\nu _{2}(x+ y)+\nu _{2}(n)-1$ .
  • Om $2\mid xy$ och $n$ är udda, då är $\nu _{2 }(x^{n}-y^{n})=\nu _{2}(xy)$ . (Följer från det allmänna fallet nedan.)
  • Följd:
    • Om $4\mid xy$ , så är $\nu _{2}(x+y)=1$ och därmed $\nu _{2}(x^{n}-y^{n})=\nu _{2}(xy )+\nu _{2}(n)$ .
• För alla $p$ :
  • Om $\gcd(n,p)=1$ och $p\mid xy$ , då $\nu _{p}(x^{n}-y^{n})=\nu _{p}(xy)$ .
  • Om $\gcd(n,p)=1$ , $p\mid x+y$ och $n$ udda, då $\nu _{p}(x^{n}+y^{n})=\nu _{p}(x+y)$ .

Översikt över bevis

Basfallet

Basfallet $\nu _{p}(x^{n}-y^{n})=\nu _{p}( xy)$ när $\gcd(n,p)=1$ bevisas först. Eftersom $p\mid xy\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)$

Det faktum att $x^{n}-y ^{n}=(xy)(x^{n-1}+x^{n-2}y+x^{n-3}y^{2}+\dots +y^{n-1})$ avslutar beviset. Villkoret $\nu _{p}(x^{n}+y^{n})=\nu _{p}(x +y)$ för udda $n$ är liknande.

Allmänt fall (udda p )

Via den binomiala expansionen kan substitutionen $y=x+kp$ användas i (1) för att visa att ${\displaystyle \nu _{p}(x^{p}-y^{p})=\nu _{p}(xy)+1} eftersom (1) är en multipel av p {\$ displaystyle $}$ men inte $p^{2}$ . Likaså $\nu _{p}(x^{p}+y^{p})=\nu _{p} (x+y)+1$ .

Sedan, om $n$ skrivs som $p^{a}b$ där $p\nmid b$ , ger basfallet $\nu _{p}(x^{n}-y^{ n})=\nu _{p}((x^{p^{a}})^{b}-(y^{p^{a}})^{b})=\nu _{p} (x^{p^{a}}-y^{p^{a}})$ . Genom induktion på $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{(exponentiering används }}a{\text{ gånger per term)}}\\&=\nu _{p}(xy)+a\end{aligned}}$

Ett liknande argument kan användas för $\nu _{p}(x^{n}+y^{n})$ .

Allmänt fall ( p = 2)

Beviset för fallet med udda $p$ kan inte tillämpas direkt när $p=2$ eftersom binomialkoefficienten ${\binom { p}{2}}={\frac {p(p-1)}{2}}$ är bara en heltalsmultipel av $p$ när $p$ är udda.

Det kan dock visas att $\nu _{2}(x^{n}-y^{n })=\nu _{2}(xy)+\nu _{2}(n)$ när $4\mid xy$ genom att skriva $n=2 ^{a}b$ där $a$ och $b$ är heltal med $b$ udda och notera att

${\ 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)(xy))\\&=\nu _{2}(xy)+a\end {Justerat}}}$

eftersom ${\displaystyle x\equiv y\equiv \pm 1{\pmod {4}}} stegar$ varje faktor i kvadratskillnaden i formen $x^{2^{k}}+y^{2^{k}}$ är kongruent med 2 modulo 4.

Det starkare påståendet $\nu _{2}(x^{n }-y^{n})=\nu _{2}(xy)+\nu _{2}(x+y)+\nu _{2}(n)-1$ när ${ \displaystyle 2\mid xy}$ bevisas analogt.

I tävlingar

Exempel på problem

LTE-lemmat kan användas för att lösa 2020 AIME I #12:

Låt $n$ vara det minst positiva heltal för vilket $149^{n}-2^{n}$ är delbart med $3^{3}\cdot 5^{5}\cdot 7^{7}.$ Hitta antalet positiva heltalsdelare för $n$ .

Lösning. Observera att $149-2=147=3\cdot 7^{2}$ . Med hjälp av LTE-lemmat, eftersom $3\nmid 149$ och $2$ men $3\mid 147$ , $\nu _{3}(149^{n}-2^{n})=\nu _{3}(147)+\ nu _{3}(n)=\nu _{3}(n)+1$ . Således, $3^{3}\mid 149^{n}-2^{n}\iff 3^{2}\mid n$ . På liknande sätt, $7\nmid 149,2$ men $7\mid 147$ , så $\nu _{7}(149^{n}-2^{n})=\nu _{7}(147)+\nu _{7}( n)=\nu _{7}(n)+2$ och $7^{7}\mid 149^{n}-2^{n} \iff 7^{5}\mid n$ .

Eftersom $5\nmid 147$ adresseras faktorerna 5 genom att lägga märke till att eftersom resterna av $149^{n}$ modulo 5 följer cykeln ${ \displaystyle 4,1,4,1}$ och de av $2^{n}$ följer cykeln $2,4,3,1$ , resterna av $149^{n}-2^{n}$ modulo 5 cyklar genom sekvensen $2,2,1,0$ . Således, $5\mid 149^{n}-2^{n}$ iff $n=4k$ för något positivt heltal $k$ . LTE-lemmat kan nu tillämpas igen: $\nu _{5}(149^{4k}-2^{4k})=\nu _{5}((149^{4})^{k}-(2^{4} )^{k})=\nu _{5}(149^{4}-2^{4})+\nu _{5}(k)$ . Sedan $149^{4}-2^{4}\equiv (-1)^{4}-2^{ 4}\equiv -15{\pmod {25}}$ , $\nu _{5}(149^{4}-2^{4})=1$ . Därför $5^{5}\mid 149^{n}-2^{n}\iff 5^{4}\ mid k\iff 4\cdot 5^{4}\mid n$ .

Genom att kombinera dessa tre resultat visar det sig att $n=2^{2}\cdot 3^{2}\cdot 5^{4}\cdot 7^ {5}$ , som har $(2+1)(2+1)(4+1)(5+ 1)=270$ positiva delare.