- 締切済み
原始根をつかって合同式を解く計算過程について
2が11の原始根で有る事をつかって3X^3 ≡ 2(mod 11)を解きたいのですが計算途中でつまずいてしまいます。 φ(11) = 10 2^10 = 1(mod 11) ind_2 (3X^3) ≡ ind_2 2 = 1(mod 11) ind_2 (3X^3) ≡ ind_2 3 + ind_2 X^3 ≡ 8 + 3 * ind_2 X (mod 11) 8+3*ind_2 X ≡ 2(mod 11) ここまでわかったのですがここから先の計算がわかりません。どうやれば X ≡ n1, n2, n3 ,.... (mod 11)の形に持っていけるのでしょうか？
- koni-ami
- お礼率14% (22/147)
- 数学・算数
- 回答数2
- ありがとう数0
- みんなの回答 （2）
- 専門家の回答
みんなの回答
- Tacosan
- ベストアンサー率23% (3656/15482)
ind_2 (X) の意味を理解しているなら造作もないこと. 最初から自分で考えることを放棄し, 他人に完全に依存する生き方をこれからもするつもり?
- f272
- ベストアンサー率46% (8012/17124)
最初から変だぞ。 ind_2 (3X^3) ≡ ind_2 2 = 1(mod 11) ではなくて ind_2 (3X^3) ≡ ind_2 2 = 1(mod 10) だろう。で， ind_2 (3) + 3*ind_2 (X) ≡ 1(mod 10) 8 + 3*ind_2 (X) ≡ 1(mod 10) 3*ind_2 (X) ≡ 3(mod 10) ind_2 (X) ≡ 1(mod 10) 以下省略。
関連するQ&A
- 原始ｎ乗根
FMTの話しの中に、ｎを偶数として、 整数ω＞＝２とすると、P=1+ω^(n/2)上でωは原始ｎ乗根となる。 と書いてある。 たしかに、ωはｎ乗して初めて１とPを法として合同になる。 これは、Pが素数でなくても成立します。 しかし、 原始ｎ乗根の性質として ω^0 + ω^j + ・・ + ω^((n-1)j) = 0 (j=1,2,...,n-1) が成立すると書いてある。 ω＝２、ｎ＝6とすると、 ｊ＝１のときは 1+２+４+８+16+32＝63＝9*7≡0 mod(9) 9=2^(6/2)+1 j=2のときは、 １+４+16+64+256+1024＝1365＝151*9+6 アルゴリズムの設計と解析II （エイホ 他）の28ページには 原始ｎ乗根の定義の中の条件として、原始ｎ乗根は条件 ω^0 + ω^j + ・・ + ω^((n-1)j) = 0 (j=1,2,...,n-1) を満たさなくてはならない。 と書いてある。 さて、原始ｎ乗根の定義は何でしょうか？ 最初の２は原始ｎ乗根なのでしょうか？ Pには他に条件が付くのでしょうか？ ｊ に条件をつけるのでしょうか？ 計算間違いなのか、誤解なのかよく分かりません。 混乱しています。よろしくお願いします。
- ベストアンサー
- 数学・算数
- 原始ｎ乗根の和をｆ（ｎ）
高木貞治 初等整数論に Ｆn(x）：１の原始ｎ乗根のみを根とする方程式 問題：Ｆn(x）の第2項の係数は-μ(n)に等しい これはほぼ理解できるのですが 解のプロセスの中で、原始ｎ乗根の和をｆ（ｎ）とすれば、、x^n-1=0から d|n Σｆ（ｄ）＝１(n=1のとき） d|n Σｆ（ｄ）＝0(n＞1のとき） ←これがいまひとつよくわかりません。 よろしくお願いします。 ----------------------------------- 原始ｎ乗根；ｎ乗して始めて１になる数
- ベストアンサー
- 数学・算数
- 離散対数の計算について
m = 7のとき、φ(7) = 6なので 3^1 ≡ 3 ( mod 7), 3^2 ≡ 2 ( mod 7), 3^3 ≡ 6 ( mod 7) 3^4 ≡ 4 ( mod 7), 3^5 ≡ 5 ( mod 7), 3^6 ≡ 1 ( mod 7) よって3が７の原始根というのはわかったのですが ここから離散対数を求める過程がわかりません。 ind_3 1 = 6, ind_3 2 = 2, ind_3 3 = 1, ind_3 4 = 4, ind_3 5 = 5, ind_3 6 = 3 この答えはどうやって出しているのでしょうか？お願いします。
- ベストアンサー
- 数学・算数
- 原始根の問題です。
整数aがpの原始根であるための必要十分条件は（a/p)=-1であることを示せ。という問題です。（ちなみにこの（a/p)=-1のかっこはルシャンドルの記号です。） 回答には p=2^(2n) +1とおく。3がpの原始根ならば、（3/p)=-1 原始根でなければ、p-1の約数は2べきだから(3/p)=1 ところで、相互法則から、(3/p)=(p/3), p≡(-1)^(2n) +1≡2(mod3)より、 (p/3)=(2/3)=-1 よって原始根になる。 と書いてあったのですが、 なんで、p=2^(2n) +1と最初におくのかわかりません。 これってフェルマー素数におくっていうことですよね？ ちなみに3はフェルマー素数の原始根となるということの 証明もいまいちよくわかりません。 この回答あってますか？ もっとわかりやすい回答があったら教えてください。 お願いします。
- ベストアンサー
- 数学・算数
- 二次合同方程式の解法過程について
Mr_Holland さんが以前回答された過程で、 「x≡±1 (mod 3)・・・・（１） ∴x=3n±1」・・・・・・（２） と 「±2n≡2 (mod 3)・・・・（３） この合同式は ±n=1 のとき成立するので・・・（４） ±n=3m+1 （m:整数）とおける。」・・・・・（５） の２つの展開が異なっているのが、よくわかりませんのでご教授願います。 【補足】 前者は展開が納得できるのですが、 後者は、 ±n=1(mod 3)から ⇔n=±1(mod 3)と同じだから、 ⇔n=3m±1と展開できるので、 （5）式±n=3m+1と異なります。 後者の妥当性が知りたいです。 以下、Mr_Holland さんからの 回答 2010-11-17 10:57:57 回答No.2 Mr_Holland ANo.1は煩雑でした。 もう少しスマートに計算することができましたので、以下に示します。 x^2≡7 (mod 27) ⇒x^2≡7 (mod 9) ⇒x^2≡1 (mod 3) ⇔x≡±1 (mod 3) ∴x=3n±1 (n:整数）とおける。 以下、複号同順とします。 x^2=(3n±1)^2= 9n^2±6n+1 だから x^2≡±6n+1≡7 (mod 9) ∴±6n≡6 (mod 9) ∴±2n≡2 (mod 3) この合同式は ±n=1 のとき成立するので ±n=3m+1 （m:整数）とおける。 x^2=9(3m+1)^2+6(3m+1)+1 =81m^2+72m+16 だから x^2≡18m+16≡7 (mod 27) ∴18m+9≡0 (mod 27) ∴2m+1≡0 (mod 3) この合同式は m=1 のとき成立するので m=3k+1 （k:整数）とおける。 x=3n±1=±(±3n+1)=±{3(3m+1)+1}=±(9m+4)=±{9(3k+1)+4}=±(27k+13) ∴x≡±13 (mod 27) ∴x≡13,14 (mod 27)
- 締切済み
- 数学・算数
- 原始根の求め方について
gcd(m, x) =1 ord_m(x) = φ(m) mが５、７、８、９、１０、１２、１５、２７、３０の時にそれぞれの原始根を求めたいのですがどうやればいいのでしょうか？
- ベストアンサー
- 数学・算数
- 合同式の解き方を教えてください。
解き方が別の合同式だと思うのですが、それぞれの問題の解き方を教えてください。 一つ目 次の合同式を解く、または、解けないことを証明せよ。 (a) 3x^2 - 5x + 7 ≡ 0 (mod 13) (b) 5x^2 - 6x + 2 ≡ 0 (mod 13) (c) x^2 + 7x + 10 ≡ 0 (mod 11) 二つ目 29の原始根は2であり、指数表を作り、それを使って合同式を解け。 (d) 17x^2 - 3x + 10 ≡ 0 (mod 29) (e) x^7 ≡ 17 (mod 29) これらの問題の解き方を教えてください。 よろしくお願いします。
- ベストアンサー
- 数学・算数
補足
>ind_2 (X) ≡ 1(mod 10) >以下省略。 省略せずにどうやるかお願いします。