m,nは正の整数とする。

質問

m,nは正の整数とする。
x^nをx^2+x+1で割った余りを求めよ。
x^3m=(x^3-1)Q(x^3)+1・・・(1)を利用。

解答
(1)⇔x^3m=(x-1)(x^2+x+1)Q(x^3)+1
これはx^3mをx^3-1で割ったときの商がQ(x^3),余りが1であることを示す。
すると、
x^3m=(x^3m-1)+1
x^3m+1=x(x^3m-1)+x
x^3m+2=x^2(x^3m-1)+x^2 = x^2(x^3m-1)+(x^2+x+1)-x-1

上の(x^3m-1)、x(x^3m-1)、x^2(x^3m-1)+(x^2+x+1)は(x^2+x+1)で割り切れるから
答えは
nを3で割った余りが0のときは、1
nを3で割った余りが1のときは、x
nを3で割った余りが2のときは、-x-1

わからないのは、
(x^3m-1)、x(x^3m-1)、x^2(x^3m-1)+(x^2+x+1)は(x^2+x+1)で割り切れるから
とあるのですが割り切れますか？なんか凄く大変なんですが・・・
それと すると、からの式はどんな発想から来るのですか？

回答No.2

D-Matsu · ベストアンサー

すると以降の式はn = 3mである場合をベースにしてxを積み重ねていきます。

n = 3m(余りが0になる場合)は単純に
x^3m = (x^3m - 1) + 1

n = 3m + 1(余りが1の場合)は上の式の両辺にxを掛けて、
x^(3m + 1) = x(x^3m - 1) + x

n = 3m + 2(余りが2の場合)は更にxを両辺に掛けて
x^(3m + 2) = x^2(x^3m - 1) + x^2 = x^2(x^3m - 1) + (x^2 + x + 1) - (x + 1)

となります。最後の変形はx + 1を足して引くから差引ゼロ、というのがポイント。

回答No.1

D-Matsu

(1)を更に変形すると、
x^3m - 1 = (x - 1)(x^2 + x + 1)Q(x^3)

になります。この式の右辺に(x^2 + x + 1)が含まれる、つまりx^3m-1の因数分解式にx^2 + x + 1が含まれるということは、これで割り切れるという事ですよね。

x^3m - 1がx^2 + x + 1で割り切れる事はこれで証明されてますから、あとは自明ですよね？

お礼

なるほど、よく分かりました！
丁寧な解説ありがとうございます。