質問<1811>2004/7/16
2次方程式x^2-x-1=0の2解A,Bに対して、 数列{a_n}をa_n=A^n+B^nによって定義する。 このとき、Pを奇素数(2以外の素数)とするとき、 a_pをpでわったあまりを求めよ。 という問題なのですが、 具体値で考えると答えは1と出せるのですが すべての奇素数でそれを証明することができません。 教えてください。
お便り2004/7/17
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で割り切れる。
お便り2004/7/18
from=juin
証明の中で「a_n=A^n+B^nが整数である」ことを使っている様ですが、 これはどうやって示すのですか。
お便り2004/7/18
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が整数であることがいえます。