Lemat o zwiększaniu wykładnika -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 , która jest dzielnikiem różnicy lub sumy -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 oznaczamy wykładnik -adyczny liczby , czyli największą taką liczbę całkowitą , że .

Wersja z odejmowaniem Niech i będą liczbami całkowitymi, będzie liczbą naturalną, a – liczbą pierwszą. Wówczas jeśli nie jest dzielnikiem żadnej z liczb i oraz , to zachodzi równość

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

jeśli , to , jeśli jest nieparzyste, to , jeśli jest parzyste, to .

Wersja z dodawaniem Niech i będą liczbami całkowitymi, będzie nieparzystą liczbą naturalną, a – liczbą pierwszą. Wówczas jeśli nie jest dzielnikiem żadnej z liczb i oraz , to zachodzi równość

Dowód

Wersja z odejmowaniem, nieparzyste lub i Załóżmy, że twierdzenie jest prawdziwe dla pewnych oraz . Wówczas na mocy własności zachodzi

czyli lemat o zwiększaniu wykładnika jest prawdziwy także dla . Możemy zatem ograniczyć dowód do przypadku, gdy jest liczbą pierwszą.

Przyjmijmy . Wtedy dla pewnego niepodzielnego przez . Ze wzoru dwumianowego Newtona mamy

Wyrazy powyższej sumy są dla podzielne przez . Stąd dla pewnej liczby całkowitej

Liczby i są niepodzielne przez . Zatem jeśli jest liczbą pierwszą różną od , to . Wtedy oraz

jak chcieliśmy. Jeśli i , to z otrzymujemy . Analogicznie jak powyżej uzasadniamy równość

Pozostał do rozpatrzenia jedynie przypadek i ( nieparzyste). Ponownie posłużmy się i zauważmy, że dla odpowiednie wyrazy rozpatrywanej sumy są podzielne przez . Stąd dla pewnej liczby całkowitej mamy

Ponieważ , dwa ostatnie wyrazy w nawiasie są podzielne przez . Jednak , czyli suma w nawiasie jest niepodzielna przez , co daje

To kończy dowód w tym przypadku.

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

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

Ponieważ z założenia i są nieparzyste, w nawiasie znajduje się suma liczb nieparzystych, która wobec nieparzystości jest również nieparzysta. Stąd zachodzi równość , co było do wykazania.

Kluczowe w dowodzie trzeciego stwierdzenia jest spostrzeżenie, że jest podzielne przez 4 dla nieparzystych i . Wtedy z pierwszego stwierdzenia otrzymujemy równość

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

Zobacz też

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

Przypisy

Kategoria:Lematy teorii liczb