3京都大学 2013年 数学 第3問解答・解説

$f(x)=x^2-2x-1$ とおくと、$x^2\equiv2x+1\pmod{f(x)}$。$x^n$ を $f(x)$ で割った余りを $a_nx+b_n$ とおく。$n=0$ では $(a_0,b_0)=(0,1)$、$n=1$ では $(a_1,b_1)=(1,0)$ である。また $$x(a_nx+b_n)\equiv(2a_n+b_n)x+a_n\pmod{f(x)}$$ より $$a_{n+1}=2a_n+b_n,\qquad b_{n+1}=a_n.$$ 初期値は整数で漸化式も整数係数なので、帰納的に各 $a_n,b_n$ は整数である。さらに $$\gcd(a_{n+1},b_{n+1})=\gcd(2a_n+b_n,a_n)=\gcd(b_n,a_n)=\gcd(a_n,b_n).$$ $\gcd(a_0,b_0)=1$ より、全ての $n\ge0$ で $\gcd(a_n,b_n)=1$。従って問題の係数 $a,b$ は整数であり、共通の素因数を持たない。

余りの係数に漸化式を立てると、整数性は帰納法で従い、ユークリッドの互除法により最大公約数が初項から変わらない。