Arithmetic Sequence

Bài toán (Poland Finals 2002)

Cho $k$ là một số nguyên dương cố định. Xét dãy $(a_n)$ thỏa mãn :

$$\{\begin{array}{c}{a}_1=k+1\\ a_{n+1}=a_n^2-k{a}_n+k,\forall n\ge 1\end{array}$$

Chứng minh rằng với mọi số nguyên dương $m$ khác $n$ thì $a_m,a_n$ nguyên tố cùng nhau.

Lời giải :

Ta có :

$$a_{n+1}-k=a_n(a_n-k)=a_n{a}_{n-1}(a_{n-1}-k)=...=a_n{a}_{n-1}{a}_{n-2}...a_1(a_1-k)=a_n{a}_{n-1}...a_1$$

Không giảm tổng quát, ta giả sử $m>n$. Khi đó gọi $p$ là một ước nguyên tố chung của $\gcd (a_m,a_n)$. Ta có :

$$a_m-k=a_{m-1}{a}_{m-2}...a_n..a_1⋮p\Rightarrow p\mid k$$

Suy ra :

$p\mid a_n-k$$=a_{n-1}(a_{n-1}-k)$$=a_{n-1}^2-k{a}_{n-1}$$\Rightarrow p\mid a_{n-1}^2$$\Rightarrow p\mid a_{n-1}$

Và lại suy ra :

$$p\mid a_{n-1}-k=a_{n-2}^2-k{a}_{n-2}\Rightarrow p\mid a_{n-2}^2\Rightarrow p\mid a_{n-2}$$

Cứ tiếp tục quá trình này ta suy ra $p\mid a_1=k+1$, suy ra $p\mid 1$. Mâu thuẫn.

Như vậy $\gcd (a_m,a_n)$ không có một ước nguyên tố nào, tức là $\gcd (a_m,a_n)=1$. Điều phải chứng minh.