Задача №4 Shortlist-a ММО 2004(Теория чисел)

[student]

Пусть $k$- фиксированное целое число большее 1 и $m=4k^2-5$.
Показать, что существуют натуральные $a$ и $b$ для которых каждый член последовательности
$x_0=a, x_1=b, x_{n+2}=x_{n+1}+x_{n}, n=0,1,2,\ldots $взаимно просто с $m.$

PS: Приведу английской версии этой задачи. Если есть ошибки в переводе скажите.
Let $k$ be a fixed integer greater than 1, and let $m=4k^2-5.$
Show that there exist positive integers $a$ and $b$ such that the sequence $(x_n)$
defined by
$x_0=a, x_1=b, x_{n+2}=x_{n+1}+x_{n}$, for $n=0,1,2,\ldots $
has all of its terms relatively prime to $m.$

[RIP]

В английской версии ни слова не сказано о бесконечности $a,b$

[ИСН]

Это мелочи. Найдётся одна пара - найдётся и сколько угодно, бо нам интересны не сами по себе эти числа, а по модулю m.

[student]

RIP писал(а):

В английской версии ни слова не сказано о бесконечности

Ах да конечно!

[Руст]

Это действительно мелочь. Для решения надо перейти к целым числам кольца
$Z[q], q=\frac{1+\sqrt 5}{2},x_n=\frac a2 (q^n+r^n)+\frac{2b-a}{2\sqrt 5}(q^n-r^n)=cq^n+dr^n, \ r=1-q.$
Тогда m раскладывается на взаимно простые множители $m=(2k+\sqrt 5 )(2k-\sqrt 5 )$. Если брать a и b так, чтобы c делился на первый множитель, но не делился на второй, а d делился на второй и не делился на первый, то это свойство сохранится при любом n, т.е. все члены будут взаимно простыми с m.