x^n+1をx^2+x+1で割った余りをどう求めるか教えてください。

x^n+1をx^2+x+1で割った余りをどう求めるか教えてください。

No.3 回答者： mister_moonlight 回答日時： 2010/07/16 10:32

書いてないが、nは自然数なんだろう。

Ａ(x)を商とすると、x^n+1＝(x^2+x+1)*Ａ(x)＋(ax＋b)となるから、aとbの値を求めると良い。
x^2+x+1＝0　は　(x-1)*(x^2+x+1)＝0から　x＾3＝1。
x^2+x+1＝0の1つの解をωとすると、ω＾3＝1、ω＾2＋ω＋1＝0　であるから、mを自然数として、n＝3m、n＝3m＋1、n＝3m＋2　の3つの場合わけが必要になることに気がつく。

(1)　n＝3mの時　x^n+1＝(ω＾3)＾n＋1＝2＝aω＋b。　aとbは実数から、a＝0、b＝2。
(2)　n＝3m＋1の時　x^n+1＝(ω＾3)＾n*ω＋1＝ω＋1＝aω＋b。　aとbは実数から、a＝b＝1。
(3)　n＝3m＋2の時　x^n+1＝(ω＾3)＾n*ω＾2＋1＝ω＾2＋1＝-ω＝aω＋b。　aとbは実数から、a＝-1、b＝0。

No.2 回答者： f272 回答日時： 2010/07/15 23:03

x+1=(x^2+x+1)(0)+x+1

x^2+1=(x^2+x+1)(1)-x
x^3+1=(x^2+x+1)(x-1)+2
ここまで求めておけば，あとは
　x^(n+3)+1=(x^3-1)(x^n)+(x^n+1)=(x^2+x+1)(x-1)(x^n)+(x^n+1)
　だからx^(n+3)+1をx^2+x+1で割った余りと，x^n+1をx^2+x+1で割った余りは等しい。
ということから，繰り返すだけ。

No.1 回答者： naniwacchi 回答日時： 2010/07/15 22:58

こんばんわ。

割る式が 2次式ですから、余りは 1次式以下であることはわかりますね。
ひとまず、ax+ bとでも置きましょう。
すると、
x^n+ 1＝ (x^2+ x+ 1)* Q(x)+ ax+ b

と表すことができます。
あとは、x^2+ x+ 1＝ 0となる xの値（2つ）を代入して、係数比較をすればいいのですが。

x^2+ x+ 1＝ 0ならば、両辺に xをかけて
(左辺)＝ x^3+ x^2+ x＝ x^3+ (-x-1)+ x＝ x^3- 1
右辺は 0のままですから、整理すると x^3＝ 1となります。

ここまでくると、nの値で場合分けが必要になることが見えてくると思います。