Question

设a1=3,a(n+1)=an^2+an-1,n为正整数，证明：

（1）对所有n，an≡3（mod4）
（2）当m≠n时，（am,an)=1(即am，an互质）

Answer 1

因为a1=3,
且若a(k)≡3(mod4）,则a(k+1))=ak^2+ak-1≡3^2+3-1≡3(mod4）,
所以根据数学归纳法，可以得到对所有n，an≡3（mod4）

不妨设m<n,
则对于任意整除am的素数p
a(m+1)))=am^2+am-1≡-1(modp).
又因为若a(m+k)≡-1(modp）,则a(m+k+1))=a(m+k)^2+a(m+k)-1≡(-1)^2-1-1≡-1(modp）,
所以根据数学归纳法，可以得到对所有k>0，a(m+k)≡-1(modp）,
因为m<n，所以a(n)≡-1(modp）,
所以若（am,an)=d≠1，则d|am和d|an
所以存在素数p|d，使得p|am且p|an。
根据刚才所证明的，a(n)≡-1(modp）,这与p|an矛盾。
所以当m≠n时，（am,an)=1(即am，an互质）。