XLVI OM - III - Zadanie 3

Dana jest liczba pierwsza $ p \geq 3 $. Określamy ciąg $ (a_n) $ wzorami






Wyznaczyć resztę z dzielenia liczby $ a_{p^3} $ przez $ p $.


Podany wzór rekurencyjny






możemy zastosować do każdego ze składników jego prawej strony (pod warunkiem, że numer $ n - p $ jest nie mniejszy od $ p $, czyli że $ n \geq 2p $); dostajemy zależność






Stosując ponownie wzór (1) do każdego ze składników ostatniej sumy otrzymujemy równość






(jeśli tylko $ n \geq 3p $). Po $ k $-krotnym zastosowaniu analogicznego przekształcenia uzyskujemy związek






sensowny i słuszny pod warunkiem że $ n \geq kp $.
(Wyprowadzenie wzoru (2) ma charakter indukcyjny; proponujemy Czytelnikowi, jako proste ćwiczenie, przeprowadzenie szczególowego uzasadnienia, przez indukcję względem $ k = 1,2,\ldots,[n/p] $, z wielokrotnym wykorzystaniem wzoru (1).)
Jeśli teraz $ n \geq p^2 $, to możemy w równości (2) podstawić $ k = p $, otrzymując






Dla $ i = 1,2,\ldots,p-1 $ współczynniki dwumianowe $ {{p}\choose{i}} $ są liczbami podzielnymi przez $ p $ (patrz: Uwaga). Jeśli więc z sumy napisanej po prawej stronie równości (3) odrzucimy wszystkie składniki z wyjątkiem dwóch skrajnych (odpowiadających wartościom wskaźnika $ i = 0 $ oraz $ i = p $), to otrzymamy liczbę przystającą do $ a_n $ modulo $ p $:






(dla $ n \geq p^2 $). Przyrównując (modulo $ p $) prawe strony związków (1) i (4) stwierdzamy, że $ a_{n-1}+a_{n-p} \equiv a_{n-p} + a_{n-p^2} $, czyli






Oznaczmy przez $ r_j $ resztę z dzielenia liczby $ a_j $ przez $ p $ (dla $ j = 0,1,2,\ldots $). Uzyskaną zależność przepisujemy w postaci






To znaczy, że ciąg ($ r_j $) jest okresowy, z okresem $ p^2-1 $; zatem






Podstawiamy $ n = p^3 $, $ k = p $, i otrzymujemy wynik:






Pozostaje zauważyć, że (w myśl wzoru (1))






i wobec tego $ r_{p^3} = r_p = p-1 $. Tak więc reszta z dzielenia liczby $ a_{p^3} $ przez $ p $ równa się $ p-1 $.
Uwaga. Fakt, na który powołaliśmy się w rozwiązaniu:
liczba pierwsza $ p $ jest dzielnikiem liczb $ {{p}\choose{1}} $, $ {{p}\choose{2}} $, $ \ldots $, $ {{p}\choose{p-1}} $
jest dobrze znany (oraz banalnie prosty: w równości $ {{p}\choose{i}} \cdot (i!) \cdot ((p-i)!) = p! $ czynniki $ i! $ oraz $ (p-i)! $ są dla $ i \in \{1,2,\ldots,p-1\} $ niepodzielne przez $ p $, więc czynnik $ {{p}\choose{i}} $ musi dzielić się przez $ p $).
