余りについて

質問

x^100をx^2-1で割った余りを求めたいのですが、
どのような解法が良いのでしょうか？
普通に割り算すると商がx^98+x^96+…+x^2+1で余りが1になるのかなと
予測できたのですが、もっと良い解法を教えてください。
よろしくお願いします。

回答No.2

osaQ · ベストアンサー

x^2ー1　という２次式で割るので，余りは必ず１次以下の式，
すなわち　ax+b　という形に書くことができます。

x^100　を　x^2-1　で割ったときの商を　Q(x)，余りを　ax+b　とします。
（商Q(x)は98次式になりますが，問いに関係ないので単にQ(x)とします。）
このとき，
　　x^100 ＝ (x^2-1)・Q(x) ＋ (ax+b)
となりますが，さらにここで　x^2-1　が
　　x^2-1 ＝ (x+1)(x-1)
と因数分解できることに気が付けば
　　x^100 ＝ (x+1)(x-1)Q(x) ＋ (ax+b)　……〔★〕
とできます。

〔★〕式に x=1，x=-1をそれぞれ代入してみると，
　　1^100 ＝ 2・0・Q(x) ＋ (a+b) ，すなわち　　1＝a+b …… [1]
　　(-1)^100 ＝ 0・(-2)・Q(x) ＋ (-a+b) ，すなわち　　1＝-a+b …… [2]

[1] と [2] を連立して解けば，a=0，b=1 が求まり，
すなわち　x^100　を　x^2-1　で割ったとき余りは　0x+1，
すなわち「 1 」とわかります

回答No.3

koko_u_

>普通に割り算すると商がx^98+x^96+…+x^2+1で余りが1になるのかなと
それで全く問題ありませんね。

x^2 を Y と置換して Y^50 - 1 = (Y - 1)(Y^49 + Y^48 + ... + 1) などとしても良い。

回答No.1

debut

余りだけわかればいいんですよね。
x^100をx^2-1で割ったときの商をＰ(x)、余りをax+bとすれば
x^100=P(x)(x^2-1)+ax+b
x=-1を代入して　1=-a+b
x=1を代入して　1=a+b
この連立を解いて　a=0,b=1　とか。