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）最终变为常数？
第 2/5 步：建立关键的模
上一步下一步
通俗地说

数 ab+1ab+1 的构造使得 aa 和 1/a1/a 分别在模 MM 下接近 −b-b 和 −1/b-1/b，这样当 nn 是 MM 的欧拉函数的适当倍数时，欧拉定理就能与数列很好地配合。

M=ab+1,gcd⁡(a,M)=gcd⁡(b,M)=1M=ab+1,\quad \gcd(a,M)=\gcd(b,M)=1
详细分析

假设 xn:=gcd⁡(an+b,bn+a)x_n:=\gcd(a^n+b,b^n+a) 最终为常数，令 M=ab+1M=ab+1。由于 a∣M−1a\mid M-1，故 gcd⁡(a,M)=1\gcd(a,M)=1，同理 gcd⁡(b,M)=1\gcd(b,M)=1。取 nn 为 φ(M)\varphi(M) 的一个足够大的倍数，使得 xn−1=xn=xn+1x_{n-1}=x_n=x_{n+1}。