LIX OM - I -Zadanie 10

Dana jest liczba pierwsza p. Ciąg liczb całkowitych dodatnich $ a_1, a_2, a_3, \dots $ spełnia warunek

\[<br />
(1) \qquad a_{n+1} = a_n +p\left[ \sqrt[p]{a_n} \right]\quad \text{dla } n =1, 2,3,\dots.<br />
\]

Wykazać, że pewien wyraz tego ciągu jest $ p $-tą potęgą liczby całkowitej.
(Uwaga: Symbol $ [x] $ oznacza największą liczbę całkowitą nie przekraczającą $ x $.)

Rozwiązanie

Zdefiniujmy ciągi liczb całkowitych nieujemnych $ b_1, b_2, b_3, \dots $ oraz $ r_1, r_2, r_3, \dots $
w następujący sposób:

\[<br />
b_n^p \leqslant a_n < (b_n + 1)^p \quad \text{ oraz } \quad r_n = a_n -b_^p<br />
\]

dla $ n =1,2,3,\dots $. Inaczej mówiąc, $ r_n $ jest różnicą między wyrazem an a największą nie
przekraczającą tego wyrazu $ p $-tą potęgą liczby całkowitej. Warunek (1) przepisujemy teraz w postaci

\[<br />
(2) \qquad	a_{n+1} = a_n +pb_n.<br />
\]

Zauważmy, ze jeżeli $ r_n = 0 $, to $ a_n = b_n^p $ jest $ p $-tą potęgą liczby całkowitej. Zadanie będzie
więc rozwiązane, jeśli udowodnimy, że $ r_n = 0 $ dla pewnej wartości $ n $.

Przypuśćmy, że wszystkie wyrazy ciągu $ r_1, r_2, r_3, \dots $ są liczbami całkowitymi dodatnimi. Niech
$ r_m $ będzie najmniejszym wśród tych wyrazów. Mamy więc $ a_m = b_m^p +rm $. Ponadto
$ b_{m-1} <b_m $, gdyż w przeciwnym razie mielibyśmy

\[<br />
r_{m-1} = a_{m-1} -b^p_{m-1} < a_m -b^p_{m-1} = r_m<br />
\]

wbrew określeniu $ m $. Zauważmy dalej, że $ a_{m-1} <(b_{m-1}+1)^p \leqslant b^p_m \leqslant a_m $
i wobec tego zachodzi nierówność

\[<br />
(3)\qquad r_m = a_m -b_m^p <am -a_{m-1} = pb_{m-1} < pb_m.<br />
\]

Niech ponadto $ k>m $ będzie najmniejszym wskaźnikiem, dla którego $ b_k >b_m $. Wówczas
$ b_m = b_{m+1} = \dots  = b_{k-1} $, więc na mocy (2) otrzymujemy

\[<br />
\begin{split}<br />
a_{m+1} &= a_m +pb_m, \\<br />
a_{m+2} &= a_{m+1} +pb_m, \\<br />
\dots \\<br />
a_k &= a_{k-1} +pb_m<br />
\end{split}<br />
\]

i sumując stronami dochodzimy do wniosku, że

\[<br />
(4) \qquad a_k = a_m +pb_m(m -k)= b^p_m +pb_m(m-k)+r_m.<br />
\]

Wykażemy z kolei, że $ b_k = b_m +1 $. Istotnie, gdyby zachodziła nierówność
$ b_k \geqslant b_m +2= b_{k-1} +2 $, mielibyśmy $ a_{k-1} < (b_{k-1} +1)^p $, $ a_k \geqslant (b_{k-1} +2)^p $
oraz

\[<br />
(5) \qquad pb_{k-1} = a_k -a_{k-1} > (b_{k-1} +2)^p -(b_{k-1} +1)^p,<br />
\]

ale pisząc $ x = b_{k-1} +2 $, $ y = b_{k-1} +1 $ mamy $ x-y =1 $, $ x>y>b_{k-1} $ i widzimy, że

\[<br />
x^p-y^p=(x-y)(x^{p-1} + x^{p-2}y +\dots +y^{p-1}) > 1\cdot py^{p-1} > pb^{p-1}_{k-1} \geqslant pb_{k-1}.<br />
\]

Nierówność (5) jest więc fałszywa, co dowodzi równości $ b_k = b_m +1 $.

Na mocy (4) możemy zatem napisać

\[<br />
(b_m +1)^p +r_k = b^p_k +r_k = a_k = b^p_m +pb_m(m-k)+r_m,<br />
\]

czyli

\[<br />
(6) \qquad r_m -r_k=(b_m+1)^p -b^p_m -pb_m(m-k).<br />
\]

Ze wzoru dwumianowego otrzymujemy

\[<br />
(b_m +1)^p - b_m^p = \binom{p}{1} b^{p-1}_m + \binom{p}{2}b^{p-2}_m + \dots + \binom{p}{p-1} b_m +1<br />
\]

Ponieważ $ p $ jest liczbą pierwszą, więc współczynniki dwumianowe $ \binom{p}{i} $ są dla $ i =1,2,\dots ,p - 1 $
liczbami podzielnymi przez $ p $. Zatem liczba $ (b_m + 1)^p - b_m^p $ daje resztę 1 z dzielenia przez
$ pb_m $. Wobec tego z (6) wynika, że liczba $ r_m -r_k $ daje resztę 1 z dzielenia przez $ pb_m $.

W (3) uzyskaliśmy nierówność $ r_m <pb_{m-1} $ korzystając jedynie z tego, że
$ b_{m-1} <b_m $. Analogicznie wyprowadzamy z nierówności $ b_{k-1} <b_k $, że $ r_k <pb_m $.
Liczby $ r_m $ i $ r_k $ należą więc do przedziału $ (0; pb_m) $, a różnica $ r_m-r_k $ daje resztę 1 z dzielenia
przez $ pb_m $. Wynika stąd, że $ r_k = r_m -1 $, co przeczy założeniu, że $ r_m $ jest najmniejszym wyrazem
w ciągu $ r_1, r_2, r_3, \dots $.

To oznacza, że $ r_n = 0 $ dla pewnego wskaźnika $ n $, skąd wynika teza.

Komentarze

Dodaj nową odpowiedź