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 – 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 ten 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ść Szablon:Wzór

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\ge 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ść Szablon:Wzór

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 Szablon:Wzór 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 Szablon:Wzór

Wyrazy powyższej sumy są dla $k\ge 2$ podzielne przez $p^{2s}$. Stąd dla pewnej liczby całkowitej $M$ Szablon:Wzór

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

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

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

Ponieważ $p\ne 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 Szablon:Wzór

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 Szablon:Wzór 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ść Szablon:Wzór

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