Tekst źródłowy strony Lemat o zwiększaniu wykładnika p-adycznego

'''Lemat o zwiększaniu wykładnika''' <math>p</math>'''-adycznego'''<ref name=":2">{{Cytuj |autor = Bartłomiej Bzdęga |tytuł = Kącik początkującego olimpijczyka |czasopismo = Delta |data = 12-2020 |issn = 0137-3005 |s = 25 |opublikowany = Uniwersytet Warszawski |url = https://www.deltami.edu.pl/2020/12/lemat-o-zwiekszaniu-wykladnika-p-adycznego/ |język = pl |dostęp = o}}</ref>, '''lemat o zwiększaniu wykładnika'''<ref name=":0">{{Cytuj |autor = Adam Neugebauer |tytuł = Algebra i teoria liczb |data = 2020 |isbn = 9788372677105 |wydanie = 2 |wydawca = Wydawnictwo Szkolne OMEGA |s = 39-41 |seria = Matematyka olimpijska |język = pl}}</ref>, '''lemat o podnoszeniu wykładnika'''<ref name=":3">{{Cytuj |autor = Jakub Byszewski |tytuł = Lemat o podnoszeniu wykładnika oraz twierdzenie Zsigmondy'ego |data dostępu = 2024-02-12 |opis = Jagiellońskie Warsztaty Olimpijskie |s = 1 |url = https://satori.tcs.uj.edu.pl/view/Subpage/6401343/content_files/Jakub_Byszewski_JWO.pdf/Jakub_Byszewski_JWO.pdf |język = pl}}</ref>  – twierdzenie w [[Teoria liczb|teorii liczb]], które w szczególnych przypadkach pozwala na znalezienie największej potęgi [[Liczby pierwsze|liczby pierwszej]] <math>p</math>, która jest [[Dzielnik|dzielnikiem]] różnicy lub sumy <math>n</math>-tych potęg.

Kluczowe obserwacje, które składają się na lemat o zwiększaniu wykładnika, były znane [[Carl Friedrich Gauss|Gaussowi]] i zostały zaprezentowane wraz z dowodem w jego dziele ''Disquisitiones Arithmeticae''<ref>{{Cytuj |autor = Carl Friedrich Gauss |tytuł = Disquisitiones Arithmeticae |czasopismo = SpringerLink |data = 1986 |data dostępu = 2024-02-12 |s = 56 |doi = 10.1007/978-1-4939-7560-0 |url = https://link.springer.com/book/10.1007/978-1-4939-7560-0 |język = en |dostęp = z}}</ref>. Choć lemat ten jest szczególnie użyteczny w zadaniach z konkursów i olimpiad matematycznych<ref name=":1">{{Cytuj |autor = Amir Hossein Parvardi |tytuł = Lifting The Exponent Lemma (LTE) |data = 2011-04-07 |data dostępu = 2024-02-12 |url = https://pregatirematematicaolimpiadejuniori.files.wordpress.com/2016/07/lte.pdf |język = en}}</ref>, znajduje on również zastosowanie m.in. w badaniach nad [[Krzywa eliptyczna|krzywymi eliptycznymi]]<ref>{{Cytuj |autor = Clemens Heuberger, Michela Mazzoli |tytuł = Elliptic curves with isomorphic groups of points over finite field extensions |czasopismo = Journal of Number Theory |data = 2017-12-01 |data dostępu = 2024-02-12 |issn = 0022-314X |wolumin = 181 |s = 89–98 |doi = 10.1016/j.jnt.2017.05.028 |url = https://www.sciencedirect.com/science/article/pii/S0022314X17302561}}</ref>.

== Twierdzenie<ref name=":2" /><ref name=":1" /> ==
Symbolem <math>\nu_p(n)</math> oznaczamy wykładnik <math>p</math>-adyczny liczby <math>n</math>, czyli największą taką liczbę całkowitą <math>k</math>, że <math>p^k \mid n</math>.

=== Wersja z odejmowaniem ===
Niech <math>a</math> i <math>b</math> będą liczbami całkowitymi, <math>n</math> będzie liczbą naturalną, a <math>p > 2</math> – liczbą pierwszą. Wówczas jeśli <math>p</math> nie jest dzielnikiem żadnej z liczb <math>a</math> i <math>b</math> oraz <math>p \mid a - b</math>, to zachodzi równość
{{Wzór|<math>\nu_p(a^n - b^n) = \nu_p(a - b) + \nu_p(n).</math>}}

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

* jeśli <math>4 \mid a - b</math>, to <math>\nu_2(a^n - b^n) = \nu_2(a - b) + \nu_2(n)</math>,
* jeśli <math>n</math> jest nieparzyste, to <math>\nu_2(a^n - b^n) = \nu_2(a - b) </math>,
* jeśli <math>n</math> jest parzyste, to <math>\nu_2(a^n - b^n) = \nu_2(a^2 - b^2) + \nu_2(n) - 1 </math>.

=== Wersja z dodawaniem ===
Niech <math>a</math> i <math>b</math> będą liczbami całkowitymi, <math>n</math> będzie nieparzystą liczbą naturalną, a <math>p \ge 2</math> – liczbą pierwszą. Wówczas jeśli <math>p</math> nie jest dzielnikiem żadnej z liczb <math>a</math> i <math>b</math> oraz <math>p \mid a + b</math>, to zachodzi równość
{{Wzór|<math>\nu_p(a^n + b^n) = \nu_p(a + b) + \nu_p(n).</math>}}

== Dowód ==

=== Wersja z odejmowaniem, <math>p
</math> nieparzyste lub <math>p = 2</math> i <math>4 \mid a - b</math><ref name=":3" /> ===
Załóżmy, że twierdzenie jest prawdziwe dla pewnych <math>n = n_1</math> oraz <math>n = n_2</math>. Wówczas na mocy własności <math>\nu_p(AB) = \nu_p(A) + \nu_p(B)
</math> zachodzi 
{{Wzór|<math>
\begin{align}
\nu_p(a^{n_1n_2} - b^{n_1n_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_1n_2),
\end{align}
</math>}}
czyli lemat o zwiększaniu wykładnika jest prawdziwy także dla <math>n = n_1n_2
</math>. Możemy zatem ograniczyć dowód do przypadku, gdy <math>n
</math> jest liczbą pierwszą.

Przyjmijmy <math>s = \nu_p(a - b)
</math>. Wtedy <math>a = b + p^sm
</math> dla pewnego <math>m
</math> niepodzielnego przez <math>p
</math>. Ze [[Dwumian Newtona|wzoru dwumianowego Newtona]] mamy 
{{Wzór|<math>a^n - b^n = (b + p^sm)^n - b^n = \sum_{k=1}^n\binom{n}{k}b^{n-k}p^{sk}m^k.</math>|1}}

Wyrazy powyższej sumy są dla <math>k \ge 2</math> podzielne przez <math>p^{2s}</math>. Stąd dla pewnej liczby całkowitej <math>M</math>
{{Wzór|<math>a^n - b^n = nb^{n-1}p^sm + p^{2s}M = p^s(nb^{n-1}m + p^s).</math>|2}}

Liczby <math>b</math> i <math>m</math> są niepodzielne przez <math>p</math>. Zatem jeśli <math>n</math> jest liczbą pierwszą różną od <math>p</math>, to <math>p\nmid nb^{n-1}m</math>. Wtedy <math>p \nmid nb^{n-1}m + p^s</math> oraz
{{Wzór|<math> \nu_p(a^n-b^n) = s = \nu_p(a - b) + \nu_p(n)</math>}}

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

Pozostał do rozpatrzenia jedynie przypadek <math>n = p</math> i <math>s=1</math> (<math>p</math> nieparzyste). Ponownie posłużmy się {{LinkWzór|1}} i zauważmy, że dla <math>k \ge 3</math> odpowiednie wyrazy rozpatrywanej sumy są podzielne przez <math>p^3</math>. Stąd dla pewnej liczby całkowitej <math>N</math> mamy
{{Wzór|<math>\begin{align}
a^n - b^n &= nb^{n-1}p^sm + \textstyle\frac{n(n-1)}{2}b^{n-2}p^{2s}m^2 + p^3N \\
&= p^2b^{p-1}m + p^2\textstyle\frac{p(p-1)}{2}b^{p-2}m^2 + p^3N\\
&= p^2(b^{p-1}m + \textstyle\frac{p(p-1)}{2}b^{p-2}m^2 + pN).
\end{align}</math>}}

Ponieważ <math>p \ne 2</math>, dwa ostatnie wyrazy w nawiasie są podzielne przez <math>p</math>. Jednak <math>p \nmid b^{p-1}m</math>, czyli suma w nawiasie jest niepodzielna przez <math>p</math>, co daje
{{Wzór|<math>\nu_p(a^n - b^n) = 2 = \nu_p(a - b) + \nu_p(n).</math>}}

To kończy dowód w tym przypadku.

=== Wersja z odejmowaniem, <math>p=2</math> ===
Dowód pierwszego ze stwierdzeń przywołanych w artykule przeprowadziliśmy już powyżej. 

Aby udowodnić drugie stwierdzenie, przyjmijmy nieparzyste <math>n</math> i, korzystając ze [[Wzory skróconego mnożenia|wzorów skróconego mnożenia]], zapiszmy
{{Wzór|<math> a^n - b^n = (a-b)(a^{n-1} + a^{n-2}b +  \dots + ab^{n-2} + b^{n-1}). </math>}}
Ponieważ z założenia <math>a</math> i <math>b</math> są nieparzyste, w nawiasie znajduje się suma <math>n</math> liczb nieparzystych, która wobec nieparzystości <math>n</math> jest również nieparzysta. Stąd zachodzi równość <math>\nu_2(a^n - b^n) = \nu_2(a - b) </math>, co było do wykazania.

Kluczowe w dowodzie trzeciego stwierdzenia jest spostrzeżenie, że <math>a^2 - b^2 = (a - b)(a + b)</math> jest podzielne przez 4 dla nieparzystych <math>a</math> i <math>b</math>. Wtedy z pierwszego stwierdzenia otrzymujemy równość
{{Wzór|<math>\begin{align}
\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{align}</math>}}

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

== Zobacz też ==

* [[Wzory skróconego mnożenia]]
* [[Lemat Hensela]]
* [[Twierdzenie Zsigmondy’ego]]

== Przypisy ==
{{Przypisy}}

[[Kategoria:Lematy teorii liczb]]