x^nをx^2+x+1で割った余りを求めよ。

高校生用の質問にご利用ください。
フォーラムルール
新規投稿は質問のみとさせていただきます。
返信する
ゲスト

x^nをx^2+x+1で割った余りを求めよ。

投稿記事 by ゲスト »

写真の問題について、x^2+x+1の解をα、βとおくとして、最終的にa=(α^n-β^n)/(√-3)、b=1・{β^(n-1)-α(n-1)}/(√-3) まで出たのです
が、その後答えがn=3kのとき・n=3k+1のとき・n=3k+2のときなど、3つになるのはどうしてですか?

説明不足ですみません。
考え方を教えて下さい。
よろしくお願いします。

基本的な解法は理解しております。
添付ファイル
vnson.png
vnson.png (226.53 KiB) 閲覧された回数 131 回
ゲスト

Re: x^nをx^2+x+1で割った余りを求めよ。

投稿記事 by ゲスト »

なるほどです、解説していきます。
$x^2+x+1=0$の解をα、βとおくと
$α^2=β 
α=β^2$
$α^3=β^3=1$がなりたちます
$x^nをx^2+x+1$で割った余りは一次式もしくは零次式になるはずなので
余りをax+bとおきます
xのある多項式をQ(x)とおいて
$f(x)=x^n=(x^2+x+1)Q(x)+ax+b$とあらわします
$f(α)=α^n=aα+b$
$f(β)=β^3=aβ+b$
より
$a={β^n-αn}/(β-α)$
$b={β^(n-1)-α(n-1)}/(β-α)$
となります
β-αは一定です
よってaとbの値は
当たり前ですがnの値に左右されます
ここで
$β^k=β^(k+3)$
$α^k=α^(k+3)$
という式が$α^3=β^3=1$から成り立ちます
よって三つの場合分けで求められることがわかります

3乗根は以下のように3周期になります
$ω^(3N)=(ω^3N)=1
ω^(3N+1)=(ω^3N)*ω=1*ω=ω
ω^(3N+2)=(ω^3N)*ω^2=1*ω^2=ω^2$

$(ω^2)^(3N)={(ω^3)^(2N)}=1
(ω^2)^(3N+1)={(ω^3)^(2N)}*ω^2=1*ω^2=ω^2
(ω^2)^(3N+2)={(ω^3)^(2N)}*(ω^2)^2=1*1*ω=ω$
返信する