Problem
NT-B2-M01-P019 Neighbouring Terms of a Sequence
#19
★★★★★ Level 5 of 5
A sequence is defined by \(u_1=2\), \(u_{n+1}=u_n^2-u_n+1\). Prove that any two distinct terms of the sequence are coprime.
Observe that \(u_{n+1}\equiv1\pmod{u_n}\). Then extend this to later terms.
We have \(u_{n+1}=u_n(u_n-1)+1\), so \(u_{n+1}\equiv1\pmod{u_n}\). If \(u_k\equiv1\pmod{u_n}\), then \(u_{k+1}=u_k^2-u_k+1\equiv1-1+1=1\pmod{u_n}\). Hence for every \(m>n\), \(u_m\equiv1\pmod{u_n}\). Thus a common divisor of \(u_m\) and \(u_n\) divides \(1\), so the gcd is \(1\).
This bridges to recurrence sequences and modular periodicity.