LVI OM - III - Zadanie 5

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

\[<br />
x_{1}=a,\ x_{2}=b,\ x_{n+2}=x_{n+1}+x_{n}\ \textrm{dla}\ n\geq 1<br />
\]

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:

\[<br />
2b=4k^{2}+2k-4\equiv 2k+1(\mathrm{mod}\ m),<br />
\]
\[<br />
4b^{2}\equiv 4k^{2}+4k+1\equiv 4k+6\equiv 4b+4(\mathrm{mod}\ m).<br />
\]

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

\[<br />
x_{n+2}=x_{n+1}+x_{n}\equiv b^{n}+b^{n-1}\equiv b^{n+1}(\mathrm{mod}\ m).<br />
\]

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.

Komentarze

Dodaj nową odpowiedź