MathLabs

第2题

对于哪些正整数对 (a,b)(a,b),数列 gcd⁡(an+b,bn+a)\gcd(a^n+b,b^n+a)(n=1,2,…n=1,2,\ldots)最终变为常数?
第 5/5 步:利用 xn+1x_{n+1} 完成证明
通俗地说

在下一步重复同样的论证表明 an+1+ba^{n+1}+b 模 MM 与 a+ba+b 同余,而由于 aa 和 bb 都模 MM 余 −1-1,这个值等于 −2-2,从而迫使 MM 至多为 22,只剩下平凡的一对。

M∣2  ⟹  a=b=1M\mid2\implies a=b=1
详细分析

由于 xn+1=xnx_{n+1}=x_n,也有 M∣an+1+bM\mid a^{n+1}+b。现在 an+1=an⋅a≡1⋅a≡a≡−1(modM)a^{n+1}=a^n\cdot a\equiv1\cdot a\equiv a\equiv-1\pmod M(第 4 步),所以 an+1+b≡−1+b≡−1−1=−2(modM)a^{n+1}+b\equiv-1+b\equiv-1-1=-2\pmod M,从而迫使 M∣2M\mid2。由于对正整数 a,ba,b 有 M=ab+1≥2M=ab+1\ge2,这给出 M=2M=2,即 ab=1ab=1,于是 a=b=1a=b=1。结合第 1 步,使数列最终变为常数的唯一一对是 (a,b)=(1,1)(a,b)=(1,1)。