查看数据源：59084bf3060a05000bf2920b
给定正整数 $p,q$，数列 $\{a_n\}$ 满足：$a_1=a_2=1$，$a_{n+2}=pa_{n+1}+qa_n$（$n=1,2,3\cdots $）．求证：要使得对任意正整数 $m,n$，均有 $(a_m,a_n)=a_{(m,n)}$，当且仅当 $p=1$ 时成立．
【难度】
【出处】
2016年北京大学数学学科夏令营初赛
【标注】
  • 方法
    >
    论述方式
    >
    数学归纳法
    >
    第一数学归纳法
  • 知识点
    >
    数论初步
    >
    整除与同余
【答案】
略
【解析】
必要性根据题意，有\[\begin{split}a_1&=1,\\ a_2&=1,\\ a_3&=p+q,\\ a_4&=p^2+pq+q,\\ a_5&=p^3+p^2q+2pq+q^2,\\ a_6&=p^4+p^3q+3p^2q+2pq^2+q^2,\end{split}\]而由 $(a_3,a_4)=a_1$，可得 $(p,q)=1$；又由 $(a_3,a_6)=a_3$，可得$$p+q\mid p^2q+q^2,$$即$$p+q\mid pq(p-1)+q(p+q),$$因此 $p=1$．
充分性当 $p=1$ 时，$a_{n+2}=a_{n+1}+qa_n$，于是$$(a_{n+2},q)=(a_{n+1}+qa_n,q)=(a_{n+1},q)=\cdots =(a_1,q)=1,$$进而$$(a_{n+1},a_{n+2})=(a_{n+1},a_{n+1}+qa_n)=(a_{n+1},a_n)=\cdots =(a_1,a_2)=1.$$记 $a_0=0$，用数学归纳法可以证明对任意 $m,n\in\mathbb N^*$，$m\leqslant n$，均有$$a_n=a_ma_{n-m+1}+qa_{m-1}a_{n-m},$$于是$$\begin{split} (a_m,a_n)=&(a_m,a_ma_{n-m+1}+qa_{m-1}a_{n-m})\\=&(a_m,a_{n-m})=\cdots \\=&(a_{(m,n)},a_{(m,n)})=a_{(m,n)},\end{split} $$原命题得证．
答案 解析 备注
0.109627s