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で割り切れる。

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

\(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}\)が整数であることがいえます。