LIII OM - III - Zadanie 6

Zawody matematyczne:

LIII OM, 2001-2002

Etap:

III

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

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

$ (1) \qquad a_{n+1} = a_1a_2 \ldots a_n + k. $

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

$ a_2 = (k + 1)^2 - k(k + 1) + k = 2k + 1 = a_1 + k, $

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

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

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.