Komentarz

XLVI OM - III - Zadanie 3

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

\[<br /> \begin{split}<br /> a_n = n & \text{ dla } n=0,1,2,\ldots,p-1, \\<br /> a_n = a_{n-1} + a_{n-p} & \text{ dla } n\geq p.<br /> \end{split}<br /> \]

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

Rozwiązanie

Podany wzór rekurencyjny

\[<br /> (1) \qquad \quad a_n = a_{n-1} + a_{n-p} \quad \textrm{dla} \quad n \geq p<br /> \]

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ść

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

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

\[<br /> \begin{split}<br /> a_n &= (a_{n-3}+ a_{n-2-p}) + 2(a_{n-p-2}+ a_{n-1-2p}) + (a_{n-2p-1} +a_{n-3p}) = \\<br /> & = a_{n-3} + 3a_{n-2-p} + 3a_{n-1-2p} + a_{n-3p}<br /> \end{split}<br /> \]

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

\[<br /> \begin{split}<br /> (2) \qquad \quad a_n & = a_{n-k} + {{k}\choose{1}} a_{n-k+1-p} + {{k}\choose{2}} a_{n-k+2-2p}+\ldots+ a_{n-kp}=\\<br /> & = \sum_{i=0}^k {{k}\choose{i}} a_{n-k+i-ip},<br /> \end{split}<br /> \]

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

\[<br /> (3) \qquad \quad a_n = \sum_{i=0}^p {{p}\choose{i}} a_{n+i -(i+1)p}.<br /> \]

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 $:

\[<br /> (4) \qquad \quad a_n \equiv a_{n-p} +a_{n-p^2} \pmod p<br /> \]

(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

\[<br /> a_{n-1} \equiv a_{n-p^2} \pmod p.<br /> \]

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

\[<br /> r_{n-1} = r_{n-p^2} \quad \textrm{dla} \quad n \geq p^2.<br /> \]

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

\[<br /> r_n = r_{n-k(p^2-1)} \quad \textrm{dla} \quad k = 1,2,\ldots,[n/(p^2-1)].<br /> \]

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

\[<br /> r_{p^3}= r_{p^3-p(p^2-1)} = r_p.<br /> \]

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

\[<br /> a_p = a_{p-1} +a_0 = (p-1) + 0 = p-1<br /> \]

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 $).

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz