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 は、法 MM のもとで aa と 1/a1/a がそれぞれ −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} となるようにする。