Kącik początkującego olimpijczyka

Lemat o zwiększaniu wykładnika p-adycznego

O zależnościach między $|˚ (a± b) p$ i $˚ (an± bn): p$

W poprzednim kąciku omówiłem wykładnik $p$ -adyczny $νp(n)$ i jego podstawowe własności - zachęcam Czytelnika, aby się z nimi zapoznał przed przystąpieniem do lektury.

Weźmy dwie liczby całkowite $a$ i $b.$ Niech $p > 2$ będzie liczbą pierwszą oraz $|p a, b,$ ale $|p a− b.$ Możemy wówczas zapisać $|a = b + kp$ dla pewnego całkowitego $k.$ Zachodzi równość

p p p ap− bp = (b + kp)p − bp = ( )bp −1kp + ( )bp −2k2p2 + ...+ ( )kppp. 1 2 p

Zauważmy, że $p νp(( 1)bp−1kp) = νp(kp) +1 = νp(a− b) + 1,$ natomiast pozostałe składniki ostatniej sumy mają większe wykładniki $p$ -adyczne. Na mocy własności (2') z poprzedniego kącika wynika z tego, że $p p |νp(a − b ) = νp(a− b) +1.$

Niech teraz $p = 2.$ Interesują nas liczby nieparzyste $|a$ i $b.$ Zachodzi równość $2 2 |ν2(a + b ) = ν2(a −b) + ν2(a+ b),$ ale równość $ν2(a + b) = 1$ ma miejsce tylko wtedy, gdy $4 a− b.$

Trzymając się wciąż powyższych założeń, wybierzmy liczbę naturalną $|m,$ która nie jest podzielna przez $|p.$ Wtedy

amb−m --------= am +am b+. ..+abm +bm ≡ mam /≡ 0 (mod p), −1 −2 −2 −1 −1 a − b

więc w tym przypadku $νp(amb−m) = νp(a − b).$

Stosując indukcję oraz powyższe rozważania, wykazujemy tytułowy lemat.

Lemat (o zwiększaniu wykładnika $p$ -adycznego (wersja z odejmowaniem)). Niech $a$ i $b$ będą całkowite, $n$ - naturalne, $p > 2$ - pierwsze. Wówczas:

(1)

jeśli

p a,b

oraz

p a− b,

n n νp(a − b ) =νp(a − b) +νp(n)

;

(2)

dla nieparzystych

a

|b

(a): jeśli $4 a −b,$ to $n n |ν2(a − b ) = ν2(a− b) +ν 2(n)$ ;
(b): $|ν2(an− bn) = ν2(a − b)$ dla $n$ nieparzystych;
(c): $n n 2 2 |ν2(a − b ) = ν2(a − b )+ ν2(n) −1$ dla $n$ parzystych.

Dla nieparzystego $n$ zachodzi równość $|an− bn = an + (−b)n.$ Pisząc $|− b$ zamiast $b,$ otrzymamy analogiczny lemat dla dodawania.

Lemat (o zwiększaniu wykładnika $p$ -adycznego (wersja z dodawaniem)). Niech $a$ i $b$ będą całkowite, $n$ - naturalne nieparzyste, $p$ - pierwsze. Jeśli $|p a, b$ oraz $|p a + b,$ to $νp(an + bn) =νp(a + b) +νp(n).$

W zadaniach dość powszechne jest stosowanie nierówności $|νp(n)⩽ logpn,$ która być może jest oczywista, ale warto tu o niej wspomnieć.