LIII OM - III - Zadanie 6

Dana jest liczba naturalna $ k $. Określamy ciąg $ (a_n) $ wzorami

\[<br />
a_{1}=k+1,\ a_{n+1}=a_{n}^{2}-ka_{n}+k\ \textrm{dla}\ n\geq 1.\]

Wykazać, że jeżeli $ m \ne n $, to liczby $ a_m $ i $ a_n $ są względnie pierwsze.

Rozwiązanie

Udowodnimy najpierw indukcyjnie, że dla $ n \geq 1 $ zachodzi równość

\[<br />
(1) \qquad a_{n+1} = a_1a_2 \ldots a_n + k.<br />
\]

Z danej w treści zadania zależności rekurencyjnej obliczamy

\[<br />
a_2 = (k + 1)^2 - k(k + 1) + k = 2k + 1 = a_1 + k,<br />
\]

co dowodzi prawdziwości zdania (1) dla $ n = 1 $, natomiast krok indukcyjny sprowadza się do ciągu równości:

\[<br />
a_{n+1}=a_{n}^{2}-ka_{n}+k=a_{n}(a_{1}a_{2}\ldots a_{n-1}+k)-ka_{n}+k=a_{1}a_{2}\ldots a_{n}+k.<br />
\]

Przypuśćmy teraz, że $ p $ jest wspólnym dzielnikiem pierwszym liczb $ a_l $ i $ a_m $, przy czym $ l > m $. Wówczas z zależności (1) dla $ n = l-1 $ wynika, że $ p | k $, a więc $ p\nmid a_1 $. Niech $ r $ będzie najmniejszą liczbą naturalną, dla której $ p | a_r $ (taka liczba $ r $ istnieje). Wtedy $ 1 <r \leq m $. Stosując ponownie równość (1), lecz tym razem dla $ n = r-1 $ wnioskujemy, że $ p $ jest dzielnikiem jednej z liczb $ a_1 ,a_2,\ldots,a_{r-1} $, wbrew temu, że $ r $ jest najmniejszą liczbą o własności $ p | a_r $.

Otrzymana sprzeczność dowodzi, że liczby $ a_l $ i $ a_m $ są względnie pierwsze.

Komentarze

Dodaj nową odpowiedź