Komentarz

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.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz