京都大学 2013年度 前期日程 第2次学力試験理系数学 第3問

$x^n$ を $x^2-2x-1$ で割った余りを$$A_{n}x+B_n$$と書く。余りを計算するとき$$x^2\equiv 2x+1(\mathrm{m}\mathrm{o}\mathrm{d}{x}^2-2x-1)$$としてよい。

$x^{n+1}=x\cdot x^n$ だから$$\begin{array}{rl}{\displaystyle x(A_{n}x+B_n)}& {\displaystyle =A_n{x}^2+B_{n}x}\\ {\displaystyle }& {\displaystyle \equiv A_n(2x+1)+B_{n}x}\\ {\displaystyle }& {\displaystyle =(2A_n+B_n)x+A_n\mathrm{.}}\end{array}$$よって$$\begin{array}{cccc}& A_{n+1}=2A_n+B_n,B_{n+1}=A_n\mathrm{.}& & \text{(1)}\end{array}$$初期値は$$\begin{array}{cccc}& A_1=1,B_1=0& & \text{(2)}\end{array}$$である。(1)、(2)から、数学的帰納法によりすべての $A_n,B_n$ は整数である。

次に、ある素数 $p$ が $A_n,B_n$ をともに割ると仮定する。$n=1$ なら $p\mid A_1=1$ となって不可能なので、$n\geqq 2$ とする。

(1) を1段前に用いると$$B_n=A_{n-1},A_n=2A_{n-1}+B_{n-1}\mathrm{.}$$したがって$$\begin{array}{cccc}& A_{n-1}=B_n,B_{n-1}=A_n-2B_n\mathrm{.}& & \text{(3)}\end{array}$$$p\mid A_n$ かつ $p\mid B_n$ なら、(3)より$$p\mid A_{n-1},p\mid B_{n-1}\mathrm{.}$$これを繰り返すと$$p\mid A_1=1$$となるが、これは矛盾である。

以上より、問題の $a=A_n,b=B_n$ は整数であり、両方を割り切る素数は存在しない。