Задача
NT-B2-M01-P019 Соседние значения последовательности
#19
★★★★★ Уровень 5 из 5
Последовательность задана условиями \(u_1=2\), \(u_{n+1}=u_n^2-u_n+1\). Докажите, что любые два различных члена последовательности взаимно просты.
Заметьте, что \(u_{n+1}\equiv1\pmod{u_n}\). Затем распространите это на более поздние члены.
Имеем \(u_{n+1}=u_n(u_n-1)+1\), поэтому \(u_{n+1}\equiv1\pmod{u_n}\). Если \(u_k\equiv1\pmod{u_n}\), то \(u_{k+1}=u_k^2-u_k+1\equiv1-1+1=1\pmod{u_n}\). Следовательно, для любого \(m>n\) выполнено \(u_m\equiv1\pmod{u_n}\). Поэтому общий делитель \(u_m\) и \(u_n\) делит \(1\), и НОД равен \(1\).
Это мост к задачам на рекуррентные последовательности и периодичность по модулю.