中国の余剰定理の応用

質問

find all the solutions of each of the following congruences.
a) x^3+8*x^2-x-1≡0(mod 11)
b) x^3+8*x^2-x-1≡0(mod 121)
c) x^3+8*x^2-x-1≡0(mod 1331)
d) x^3+8*x^2-x-1≡0(mod 77)
e) x^3+8*x^2-x-1≡0(mod 847)

これはどうやって解けばいいのでしょうか？
modが11, 11^2, 11^3, 7*11, 7*11^2と11の倍数なのでそれを使う事はうっすらとわかるのですがいかんせん、わかりません。

a)はx≡4(mod 11), x≡5(mod 11)までは出せました。
これを連立合同方程式で解いて(a)は完了でしょうか？
b、c、d、eもはどうすればいいのでしょうか？

回答No.2

ferien · ベストアンサー

find all the solutions of each of the following congruences.
a) x^3+8*x^2-x-1≡0(mod 11)
b) x^3+8*x^2-x-1≡0(mod 121)
c) x^3+8*x^2-x-1≡0(mod 1331)
d) x^3+8*x^2-x-1≡0(mod 77)
e) x^3+8*x^2-x-1≡0(mod 847)

これはどうやって解けばいいのでしょうか？
modが11, 11^2, 11^3, 7*11, 7*11^2と11の倍数なのでそれを使う事はうっすらとわかるのですが
＞いかんせん、わかりません。

ａ）～ｅ）は個別の問題だと思います。解く途中で連立合同式の解法を使います。
>a)はx≡4(mod 11), x≡5(mod 11)までは出せました。
この２つが解です。

>b) x^3+8*x^2-x-1≡0(mod 121)
>c) x^3+8*x^2-x-1≡0(mod 1331)
この２つはうまい解法が分からなくて、結局、余りとして考えられる全部の値を代入して、121，1331で割って余りが０になる場合を調べました。（手計算でやるのは大変なので、短いプログラムを作ってパソコンで計算しました。）
ｂ）の解は、ｘ≡59（mod121）
ｃ）の解は、ｘ≡1148（mod1331）
の１つずつでした、
５９は素数だし、1148は１１を因数に持たないので、１１との関連がよく分かりません。

>d) x^3+8*x^2-x-1≡0(mod 77)
７７＝７×１１なので、x^3+8*x^2-x-1≡0(mod 7)の解を求めます。
ｘ＝０～６まで代入して、７で割って余りが０になるのは、
ｘ≡１（mod7)，ｘ≡６（mod７）……（１）
ａ）の解　x≡4(mod 11), x≡5(mod 11)と組み合わせて連立合同式を作って解を求めます。
組み合わせは４通り
ｘ≡１（mod7)，x≡4(mod 11),
ｘ≡１（mod7)，x≡5(mod 11)
ｘ≡６（mod７）x≡4(mod 11),
ｘ≡６（mod７）x≡5(mod 11)
中国の余剰定理を使って解きます。
解は、ｘ＝１５，２７，４８，７１（mod77）

e) x^3+8*x^2-x-1≡0(mod 847)
８４７＝７×１１^2なので、（１）とｂ）の解を使って連立合同式を作ります。
ｘ≡１（mod7)，ｘ≡59（mod121），
ｘ≡６（mod7）ｘ≡59（mod121），
最初の方を解いてみます。
mod7で、ｘ1・１２１≡１
　　　　　１２１ｘ1≡１
　　　　　　２ｘ１≡８
　　　　　　　ｘ1≡４
mod121で、ｘ2・７≡５９
　　　　　　　７ｘ2≡５９
　　　　　　　７ｘ2≡３０１　
　　　　　　　　ｘ2≡４３
ｘ＝４×１２１＋４３×７
　＝４８４＋３０１　
　＝７８５
よって、ｘ≡７８５（mod847），ｘ≡６６４（mod847）
になりました。
ｂ）ｃ）は答えだけで申し訳ないですが参考にして下さい。
何かあったらお願いします。

回答No.7

ferien

No.1No.6さん、別解ありがとうございます。

>んで d は #2 の筋だけど 8 ≡ 1 (mod 7) を使えば左辺が因数分解できる, と.

x^3+8*x^2-x-1≡ｘ^3＋ｘ^2－ｘ－１
　　　　　　　≡ｘ^2（ｘ＋１）－（ｘ＋１）
　　　　　　　≡（ｘ＋１）（ｘ^2－１）
　　　　　　　≡（ｘ＋１）^2（ｘ－１）
　　　　　　　≡０（mod7）
ｘ＋１≡０（mod7）→ｘ≡－１≡６（mod７）
ｘ－１≡０（mod7）→ｘ≡１（mod7）

回答No.6

Tacosan

えぇと, 正直なところ #2 の「うまい解法が分からなくて、結局、余りとして考えられる全部の値を代入して」は #4 の (従って #1 の) 筋でやったものだと思ってました. いや, #1 はいくらなんでも直接的なんで (「ゴリゴリ押せば」がその辺のニュアンス), もっと賢い方法があるかもしれないとは考えてたんです.... そのわりに「５９は素数だし、1148は１１を因数に持たないので、１１との関連がよく分かりません」というのが謎だったです.

んで d は #2 の筋だけど 8 ≡ 1 (mod 7) を使えば左辺が因数分解できる, と.

回答No.5

ferien

No.4さん、ありがとうございます。

最初は、式変形の過程があまりにも簡潔でよく分からなかったのですが、実際に代入して計算して得られた結果なのだとようやく理解できました。
マネして、ｃ）もやってみます。

＞どの式も、左辺が同じでしょう？ それを使います。
＞A≡B mod mn ⇒ A≡B mod m より、
＞b) の解は a) を、c) の解は b) を満たします。

x≡59+121k （mod 1331）を ｃ) へ代入すれば、
（ｘ＝1331n＋59+121k の余りの部分を代入）
実際はもっとかなり込み入った式になりますが、
1331の倍数になっている部分と、残りの部分（余り）に分けて
余りだけ取り出して書くと、
11^2ｋ＋233167≡11^2（ｋ＋1927）より、
11^2（ｋ＋1927）≡０（mod1331）
これより、ｋ＋1927≡０（mod11）→ｋ≡-1927≡９（mod11）
ｋ＝11n＋9とおくと、
ｘ＝59＋121（11n＋9）＝59＋1331n＋1089＝1148＋1331n
よって、ｘ≡1148（mod1331）

回答No.4

alice_44

A No.1 の方針で、落ち穂拾いです。

どの式も、左辺が同じでしょう？ それを使います。
A≡B mod mn ⇒ A≡B mod m より、
b) の解は a) を、c) の解は b) を満たします。

x≡4+11k, 5+11k mod 121 を b) へ代入すれば、
x≡4+11k ⇒ 11(k+6)≡0 mod 121 ⇒ k≡-6 mod 11
k≡-6 mod 121 とは限らないので、注意してください。
よって、x=4+11(5+11n)=59+121n≡59 mod 121.
x≡5+11k ⇒ 77≡0 mod 121 ⇒ 解なし
以上より、b) は x≡59 mod 121.

c) も同様です。

回答No.3

ferien

すみません。訂正です。

解は、ｘ≡１５，２７，４８，７１（mod77）

です。他に何か間違いがあったら連絡お願いします。

回答No.1

Tacosan

「連立合同方程式で解いて」って, どういう意味でしょうか?

で, 例えば x≡4 mod 11 が出ているなら, これから法 121 で x がどう書けそうかわかるはず. それを代入してゴリゴリ押せば b や c はできるんじゃない?