LVI OM - III - Zadanie 5

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

III

Niech $k$ będzie liczbą naturalną większą od 1 i niech $m = 4k^2 - 5$ .

Wykazać, że istnieją takie liczby całkowite dodatnie $a$ , $b$ , że każdy wyraz ciągu $(x_n)$ określonego wzorami

$ x_{1}=a,\ x_{2}=b,\ x_{n+2}=x_{n+1}+x_{n}\ \textrm{dla}\ n\geq 1 $

jest względnie pierwszy z liczbą $m$ .

Rozwiązanie

Wykażemy, że warunki zadania spełniają liczby $a = 1$ , $b = 2k^2 + k - 2$ . Udowodnimy indukcyjnie, że $x_n \equiv b^{n-1}(\mathrm{mod}\ m)$ dla $n = 1,2,3,...$ . Dla $n = 1$ i $n = 2$ zależność ta jest oczywiście spełniona.

Korzystając ze związku $4k^2\equiv 5(\mathrm{mod}\ m)$ uzyskujemy kolejno:

$ 2b=4k^{2}+2k-4\equiv 2k+1(\mathrm{mod}\ m), $

$ 4b^{2}\equiv 4k^{2}+4k+1\equiv 4k+6\equiv 4b+4(\mathrm{mod}\ m). $

Liczby 4 i $m$ są względnie pierwsze, więc $b^2\equiv b+1(\mathrm{mod}\ m)$ . Stąd i z założenia indukcyjnego dostajemy

$ x_{n+2}=x_{n+1}+x_{n}\equiv b^{n}+b^{n-1}\equiv b^{n+1}(\mathrm{mod}\ m). $

Dowód indukcyjny jest zakończony.

Z uzyskanej w tym dowodzie zależności $b^2 \equiv b +1 (\mathrm{mod}\ m)$ wynika, że liczby $b$ i $m$ są względnie pierwsze. Skoro zaś $x_n \equiv b^{n-1} (\mathrm{mod}\ m)$ , wnosimy stąd, że (dla każdego $n$ ) liczby $x_n$ i $m$ są względnie pierwsze.