Lemat o zwiększaniu wykładnika p-adycznego

Lemat o zwiększaniu wykładnika $p$-adycznego, lemat o zwiększaniu wykładnika, lemat o podnoszeniu wykładnika (ang. Lifting the Exponent Lemma, LTE) – twierdzenie w teorii liczb, które w szczególnych przypadkach pozwala na znalezienie największej potęgi liczby pierwszej $p$, która jest dzielnikiem różnicy lub sumy $n$-tych potęg.

Kluczowe obserwacje, które składają się na lemat o zwiększaniu wykładnika, były znane Gaussowi i zostały zaprezentowane wraz z dowodem w jego dziele Disquisitiones Arithmeticae. Choć lemat LTE jest szczególnie użyteczny w zadaniach z konkursów i olimpiad matematycznych, znajduje on również zastosowanie m.in. w badaniach nad krzywymi eliptycznymi.

Twierdzenie

Symbolem $\nu _{p}(n)$ oznaczamy wykładnik $p$-adyczny liczby $n$, czyli największą taką liczbę całkowitą $k$, że $p^{k}\mid n$.

Wersja z odejmowaniem

Niech $a$ i $b$ będą liczbami całkowitymi, $n$ będzie liczbą naturalną, a $p>2$ – liczbą pierwszą. Wówczas jeśli $p$ nie jest dzielnikiem żadnej z liczb $a$ i $b$ oraz $p\mid a-b$, to zachodzi równość

$\nu _{p}(a^{n}-b^{n})=\nu _{p}(a-b)+\nu _{p}(n).$

Z kolei dla nieparzystych liczb całkowitych $a$ i $b$ oraz liczby naturalnej $n$ prawdziwe są następujące stwierdzenia

• jeśli $4\mid a-b$, to $\nu _{2}(a^{n}-b^{n})=\nu _{2}(a-b)+\nu _{2}(n)$,
• jeśli $n$ jest nieparzyste, to $\nu _{2}(a^{n}-b^{n})=\nu _{2}(a-b)$,
• jeśli $n$ jest parzyste, to $\nu _{2}(a^{n}-b^{n})=\nu _{2}(a^{2}-b^{2})+\nu _{2}(n)-1$.

Wersja z dodawaniem

Niech $a$ i $b$ będą liczbami całkowitymi, $n$ będzie nieparzystą liczbą naturalną, a $p\geq 2$ – liczbą pierwszą. Wówczas jeśli $p$ nie jest dzielnikiem żadnej z liczb $a$ i $b$ oraz $p\mid a+b$, to zachodzi równość

$\nu _{p}(a^{n}+b^{n})=\nu _{p}(a+b)+\nu _{p}(n).$

Dowód

Wersja z odejmowaniem, $p$ nieparzyste lub $p=2$ i $4\mid a-b$

Załóżmy, że twierdzenie jest prawdziwe dla pewnych $n=n_{1}$ oraz $n=n_{2}$. Wówczas na mocy własności $\nu _{p}(AB)=\nu _{p}(A)+\nu _{p}(B)$ zachodzi

${\begin{aligned}\nu _{p}(a^{n_{1}n_{2}}-b^{n_{1}n_{2}})&=\nu _{p}((a^{n_{1}})^{n_{2}}-(b^{n_{1}})^{n_{2}})\\&=\nu _{p}(a^{n_{1}}-b^{n_{1}})+\nu _{p}(n_{2})\\&=\nu _{p}(a-b)+\nu _{p}(n_{1})+\nu _{p}(n_{2})\\&=\nu _{p}(a-b)+\nu _{p}(n_{1}n_{2}),\end{aligned}}$

czyli lemat o zwiększaniu wykładnika jest prawdziwy także dla $n=n_{1}n_{2}$. Możemy zatem ograniczyć dowód do przypadku, gdy $n$ jest liczbą pierwszą.

Przyjmijmy $s=\nu _{p}(a-b)$. Wtedy $a=b+p^{s}m$ dla pewnego $m$ niepodzielnego przez $p$. Ze wzoru dwumianowego Newtona mamy

$a^{n}-b^{n}=(b+p^{s}m)^{n}-b^{n}=\sum _{k=1}^{n}{\binom {n}{k}}b^{n-k}p^{sk}m^{k}.$

(1)

Wyrazy powyższej sumy są dla $k\geq 2$ podzielne przez $p^{2s}$. Stąd dla pewnej liczby całkowitej $M$

$a^{n}-b^{n}=nb^{n-1}p^{s}m+p^{2s}M=p^{s}(nb^{n-1}m+p^{s}).$

(2)

Liczby $b$ i $m$ są niepodzielne przez $p$. Zatem jeśli $n$ jest liczbą pierwszą różną od $p$, to $p\nmid nb^{n-1}m$. Wtedy $p\nmid nb^{n-1}m+p^{s}$ oraz

$\nu _{p}(a^{n}-b^{n})=s=\nu _{p}(a-b)+\nu _{p}(n)$

jak chcieliśmy. Jeśli $n=p$ i $s\geq 2$, to z (2) otrzymujemy $a^{n}-b^{n}=p^{s+1}(b^{n-1}m+p^{s-1})$. Analogicznie jak powyżej uzasadniamy równość

$\nu _{p}(a^{n}-b^{n})=s+1=\nu _{p}(a-b)+\nu _{p}(n).$

Pozostał do rozpatrzenia jedynie przypadek $n=p$ i $s=1$ ($p$ nieparzyste). Ponownie posłużmy się (1) i zauważmy, że dla $k\geq 3$ odpowiednie wyrazy rozpatrywanej sumy są podzielne przez $p^{3}$. Stąd dla pewnej liczby całkowitej $N$ mamy

${\begin{aligned}a^{n}-b^{n}&=nb^{n-1}p^{s}m+\textstyle {\frac {n(n-1)}{2}}b^{n-2}p^{2s}m^{2}+p^{3}N\\&=p^{2}b^{p-1}m+p^{2}\textstyle {\frac {p(p-1)}{2}}b^{p-2}m^{2}+p^{3}N\\&=p^{2}(b^{p-1}m+\textstyle {\frac {p(p-1)}{2}}b^{p-2}m^{2}+pN).\end{aligned}}$

Ponieważ $p\neq 2$, dwa ostatnie wyrazy w nawiasie są podzielne przez $p$. Jednak $p\nmid b^{p-1}m$, czyli suma w nawiasie jest niepodzielna przez $p$, co daje

$\nu _{p}(a^{n}-b^{n})=2=\nu _{p}(a-b)+\nu _{p}(n).$

To kończy dowód w tym przypadku.

Wersja z odejmowaniem, $p=2$

Dowód pierwszego ze stwierdzeń przywołanych w artykule przeprowadziliśmy już powyżej.

Aby udowodnić drugie stwierdzenie, przyjmijmy nieparzyste $n$ i, korzystając ze wzorów skróconego mnożenia, zapiszmy

$a^{n}-b^{n}=(a-b)(a^{n-1}+a^{n-2}b+\dots +ab^{n-2}+b^{n-1}).$

Ponieważ z założenia $a$ i $b$ są nieparzyste, w nawiasie znajduje się suma $n$ liczb nieparzystych, która wobec nieparzystości $n$ jest również nieparzysta. Stąd zachodzi równość $\nu _{2}(a^{n}-b^{n})=\nu _{2}(a-b)$, co było do wykazania.

Kluczowe w dowodzie trzeciego stwierdzenia jest spostrzeżenie, że $a^{2}-b^{2}=(a-b)(a+b)$ jest podzielne przez 4 dla nieparzystych $a$ i $b$. Wtedy z pierwszego stwierdzenia otrzymujemy równość

${\begin{aligned}\nu _{p}(a^{n}-b^{n})&=\nu _{p}((a^{2})^{n/2}-(b^{2})^{n/2})\\&=\nu _{p}(a^{2}-b^{2})+\nu _{p}(\textstyle {\frac {n}{2}})\\&=\nu _{p}(a^{2}-b^{2})+\nu _{p}(n)-1.\end{aligned}}$

Wersja z dodawaniem

Gdy $p>2$, wystarczy w założeniach oraz w tezie lematu o zwiększaniu wykładnika w wersji z odejmowaniem przyjąć $-b$ w miejsce $b$, by otrzymać twierdzenie równoważne wersji z dodawaniem. Dla $p=2$ postępujemy analogicznie wychodząc od drugiego stwierdzenia.

Zobacz też

• Wzory skróconego mnożenia
• Lemat Hensela
• Twierdzenie Zsigmondy’ego