XLVI OM - III - Zadanie 3

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

III

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

$ \begin{split} a_n = n & \text{ dla } n=0,1,2,\ldots,p-1, \\ a_n = a_{n-1} + a_{n-p} & \text{ dla } n\geq p. \end{split} $

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

Rozwiązanie

Podany wzór rekurencyjny

$ (1) \qquad \quad a_n = a_{n-1} + a_{n-p} \quad \textrm{dla} \quad n \geq p $

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

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

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

$ \begin{split} 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}) = \\ & = a_{n-3} + 3a_{n-2-p} + 3a_{n-1-2p} + a_{n-3p} \end{split} $

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

$ \begin{split} (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}=\\ & = \sum_{i=0}^k {{k}\choose{i}} a_{n-k+i-ip}, \end{split} $

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

$ (3) \qquad \quad a_n = \sum_{i=0}^p {{p}\choose{i}} a_{n+i -(i+1)p}. $

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

$ (4) \qquad \quad a_n \equiv a_{n-p} +a_{n-p^2} \pmod 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

$ a_{n-1} \equiv a_{n-p^2} \pmod p. $

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

$ r_{n-1} = r_{n-p^2} \quad \textrm{dla} \quad n \geq p^2. $

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

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

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

$ r_{p^3}= r_{p^3-p(p^2-1)} = r_p. $

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

$ a_p = a_{p-1} +a_0 = (p-1) + 0 = p-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$ ).