質問: 整数の問題の解答解説お願いします。 X^(n+1)をX^2-X-1で割った余りをAnX+Bnとおく(n=1、2、3...) このときAn、Bnは整数であり、互いに素であることを示せ。
回答: まず、A[n], B[n]の漸化式を求めます。 X^(n+1)をX^2-X-1で割った商をQnとすると、余りはA[n]X+B[n]だから X^(n+1)=Qn(X^2-X-1)+A[n]X+B[n]となるので X^(n+2)=XQn+A[n]X^2+B[n]X =(XQn+A[n])(X^2-X-1)+(A[n]+B[n])X+A[n] よって、A[n+1]=A[n]+B[n], B[n+1]=A[n] では、数学的帰納法を用いて、A[n], B[n]が整数であり、互いに素であることを示します。 まず、n=1のときは X^2=1*(X^2-X-1)+X+1なので A[1]=B[1]=1 よって、成り立ちます。 次に、n=kのときに成り立つと仮定すると A[k], B[k]は整数で A[k+1]=A{k]+B[k], B[k+1]=A[k]なので A[k+1], B[k+1]は整数です。 そして、A[k+1]とB[k+1]の最大公約数をdとすると A[k]=B[k+1], B[k]=A[k+1]-B[k+1]なので dはA[k]とB[k]の公約数となり、A[k]とB[k]は互いに素だから d=1 よって、A[k+1]とB[k+1]は互いに素です。 したがって、n=k+1のときも成り立ちます。 以上から、任意の正整数nに対して、A[n], B[n]は整数であり、互いに素です。 【補足についての追記】 「X^(n+2)=XQn+An]X^2+B[n]X=(XQ[n+A[n])(X^2-X-1)+(A[n]+B[n])X+A[n]」の式は、X^(n+2)をX^2-X-1で割った余りを求めるための式であり、X(X^2-X-1)で割っているわけではありません。 この式変形を補足すると、次のようになります。 X^(n+1)=Qn(X^2-X-1)+A[n]X+B[n]の両辺にXをかけると X^(n+2)=XQn(X^2-X-1)+A[n]X^2+B[n]X ここで、X^2=(X^2-X-1)+X+1なので XQn(X^2-X-1)+A[n]X^2+B[n]X =XQn(X^2-X-1)+A[n]{(X^2-X-1)+X+1}+B[n]X =(XQn)(X^2-X-1)+An+An+B[n]X =(XQn+A[n])(X^2-X-1)+(A[n]+B[n])X+A[n] よって、X^(n+2)=(XQn+A[n])(X^2-X-1)+(A[n]+B[n])X+A[n]となるので X^(n+2)をX^2-X-1で割った余りは(A[n]+B[n])X+A[n] したがって、A[n+1]=A[n]+B[n], B[n]=A[n]となります。