質問

２次方程式x^2-x-1=0の２解A,Bに対して、
数列｛a_ｎ｝をa_n=A^n＋B＾nによって定義する。
このとき、Pを奇素数（２以外の素数）とするとき、
a_pをpでわったあまりを求めよ。
という問題なのですが、
具体値で考えると答えは１と出せるのですが
すべての奇素数でそれを証明することができません。
教えてください。

お便り２００４／７／１７
from=風あざみ

AとBはx^2-x-1=0の解ですから、解と係数の関係よりA+B=1、AB=-1です。

a_p=A^p+B^pをpで割った余りを求める。

天下りですが(A+B)^pを二項定理で展開します。

1=(A+B)^p
=∑_(i=0)^(p){(p_C_i)*(A^i)*{B^(p-i)}}
=A^p+B^p+(p_C_1){A^(p-1)*B+A*B^(p-1)}+(p_C_2){A^(p-2)*B^2+A^2*B^(p-2)}+
　　　・・・+(p_C_{(p-1)/2)})*(A^{(p-1)/2}*B^{(p+1)/2}+A^{(p+1)/2}*B^{(p-1)/2})
=A^p+B^p+(p_C_1)A*B{A^(p-2)+B^(p-2)}+(p_C_2)(AB)^2*{A^(p-4)+B^(p-4)}+
　　　・・・+(p_C_{(p-1)/2)})*(AB)^{(p-1)/2})*(A+B)

ここで、a_i=A^i+B^iとAB=-1を思い出すと

A^p+B^p+(p_C_1)A*B{A^(p-2)+B^(p-2)}+(p_C_2)(AB)^2*{A^(p-4)+B^(p-4)}+
　　　・・・+(p_C_{(p-1)/2)})*(AB)^{(p-1)/2})*(A+B)
=a_p+(p_C_1)(-1)*a_(p-2)+(p_C_2)*(-1)^2*a_(p-4)+
　　　・・・+(p_C_{(p-1)/2})*(-1)^{(p-1)/2}*a_1

p_C_1、p_C_2、・・・、p_C_{(p-1)/2}はpで割り切れるので…※(一番下で証明する)

1=a_p+(p_C_1)(-1)*a_(p-2)+(p_C_2)*(-1)^2*a_(p-4)+
　　　・・・+(p_C_{(p-1)/2})*(-1)^{(p-1)/2}*a_1
　=a_p+p

*(整数)+・・・+p*(整数)=1+p*(整数)と書ける。

よって
a_p=1+p*(整数)となる。

このことより、a_pをpで割った余りは1であることがわかる。

※の証明
1≦i≦p-1のとき
(i!)*(p_C_i)=p*(p-1)*…*(p-i+1)
i!とpは互いに素だから、p_C_iがpで割り切れる
とくに、p_C_1、p_C_2、・・・、p_C_{(p-1)/2}はpで割り切れる。

お便り２００４／７／１８
from=juin

証明の中で「a_n=A^n+B^nが整数である」ことを使っている様ですが、
これはどうやって示すのですか。

お便り２００４／７／１８
from=風あざみ

a_nが整数であることですか。

AとBはx^2-x-1=0の二つの解だから
A^2-A-1=0、B^2-B-1=0も成立します。
解と係数の関係より
A+B=1、AB=-1 も成立します。 

まず、a_n=A^n＋B^nは漸化式a_(n+2)=a_(n+1)+a_(n)を満たすことを言います。

証明は
a_(n+2)-{a_(n+1)+a_n}=A^(n+2)+B^(n+2)-{A^(n+1)+B^(n+1)}-{A^n+B^n}
　　　　　　　　　　=A^n(A^2-A-1)+B^n(B^2-B-1)
　　　　　　　　　　=(A^n)*0+(B^n)*0=0

と言う風にやります。

漸化式a_(n+2)=a_(n+1)+a_nを利用して数学的帰納法で、
a_nが整数であることを言います。

a_0=A^0+B^0=1+1=2、a_1=A+B=1
n=k-1、n=kのときa_nは整数と仮定する、
つまり、a_(k-1)とa_kが整数であると仮定します。

a_(k+1)=a_k+a_(k-1)ですからa_(k+1)も整数であることがわかります。

よってn=k+1のときもa_nが整数であることがいえます。

よって数学的帰納法より、
任意の自然数nに対してa_nが整数であることがいえます。