Математикадан республикалық олимпиада, 2015-2016 оқу жылы, 9 сынып

Кез келген натурал $n$ үшін, ${{F}_{n}}-p\left( n \right)$ саны $m$-ге бөлінетіндей, $m\ge 2$ натурал саны және коэффициенттері бүтін болатын $p\left( x \right)$ көпмүшесі табылады ма? Бұл жерде $\left( {{F}_{n}} \right)$ — келесі шарттармен анықталатын Фибоначчи тізбегі: ${{F}_{1}}={{F}_{2}}=1$ және барлық натурал $n$ үшін \[{{F}_{n+2}}={{F}_{n+1}}+{{F}_{n}}.\] ( А. Васильев )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. Нет.
Для функции $g$ натурального аргумента рассмотрим оператор $\vartriangle g\left( n \right)=g\left( n+1 \right)-g\left( n \right).$ Ясно, что если $p$ — многочлен степени $k$, то ${{\vartriangle }^{k+1}}p=\vartriangle \left( \vartriangle \ldots \left( p \right)\ldots \right)=0$ (объясните, почему!).
От противного. Имеем: $p\left( n \right)\equiv {{F}_{n}}\pmod m$ для всех натуральных $n$. Применяя $k+1$ раз оператор $\vartriangle $ к обеим частям, получим: $0 \equiv {{F}_{n-k-1}}\pmod m$ для любого натурального $n$ (объясните, почему!). Подставляя $n=k+2$, находим: $0\equiv 1 \pmod m$, что невозможно при $m\ge 2$.

Решение#2

Мы можем допустить что $m=p$ где $p\in\mathbb{P}$

Докажем от противного пусть найдется такой $p$.

Теорема: $F_p\equiv 5^{\frac{p-1}{2}}\pmod p$

Доказательство Теоремы вы можете найти в платформе AOPS .

Лемма: $F_{p+i}-F_{i}$ делится на $p$ для любого $i\in\mathbb{N}$

Доказательство Леммы: $F_{p+i}\equiv g(p+i)\equiv g(i) \equiv F_{i}\pmod p$

Заметим что для $p\le 5$ Одно из

(1)*$p \mid F_{p+1}-F_{1}$

(2)*$p \mid F_{p+2}-F_{2}$

Неверно, откуда $p\ge7$. Так как $p$ делит и (1)* и (2)* , то оно делит и их разность, а их разность равна $F_{p}$ значит получаем что $p \mid F_p \implies p \mid 5^{\frac{p-1}{2}}$ что и неверно при $p\ge7$.

это подходит для непростых натуральных?