- ベストアンサー
原始根
pは素数、kは自然数で、kはp-1の倍数ではないとき、pと互いに素な自然数aで、a^k-1がpの倍数とならないものが存在する。 これを原始根を持ち出さずに証明する方法があれば教えてください。
- みんなの回答 (1)
- 専門家の回答
質問者が選んだベストアンサー
関連するQ&A
- 原始根の問題です。
整数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はフェルマー素数の原始根となるということの 証明もいまいちよくわかりません。 この回答あってますか? もっとわかりやすい回答があったら教えてください。 お願いします。
- ベストアンサー
- 数学・算数
- 中国の剰余定理と原始根
アドバイスよろしくおねがいします。 p,qを素数としたときに mod p と mod q において 原始根になる値gが存在する。それは中国剰余定理からいえる。 という記述があったのですが、原始根と中国剰余定理が結びつきません。 mod p,mod q において原始根ということは gを法pにおいてp-1乗してはじめて1になり、かつ法qにおいてもq-1乗してはじめて1になるわけだと思います。(ほかにも条件がありますが…) で、中国剰余定理は 簡単に言うと 複数の法が違い、法の数が互いに素な連立合同式に対して、解が一意に定まるということだと思います。 この二つが結びつきません。 ご教授お願いします
- ベストアンサー
- 数学・算数
- 原始n乗根
FMTの話しの中に、nを偶数として、 整数ω>=2とすると、P=1+ω^(n/2)上でωは原始n乗根となる。 と書いてある。 たしかに、ωはn乗して初めて1とPを法として合同になる。 これは、Pが素数でなくても成立します。 しかし、 原始n乗根の性質として ω^0 + ω^j + ・・ + ω^((n-1)j) = 0 (j=1,2,...,n-1) が成立すると書いてある。 ω=2、n=6とすると、 j=1のときは 1+2+4+8+16+32=63=9*7≡0 mod(9) 9=2^(6/2)+1 j=2のときは、 1+4+16+64+256+1024=1365=151*9+6 アルゴリズムの設計と解析II (エイホ 他)の28ページには 原始n乗根の定義の中の条件として、原始n乗根は条件 ω^0 + ω^j + ・・ + ω^((n-1)j) = 0 (j=1,2,...,n-1) を満たさなくてはならない。 と書いてある。 さて、原始n乗根の定義は何でしょうか? 最初の2は原始n乗根なのでしょうか? Pには他に条件が付くのでしょうか? j に条件をつけるのでしょうか? 計算間違いなのか、誤解なのかよく分かりません。 混乱しています。よろしくお願いします。
- ベストアンサー
- 数学・算数
- x^2+y^2=n×pを満たす整数x,y,nが存在する奇素数pについて
x^2+y^2=n×pを満たす整数x,y,nが存在する奇素数pについて、 a^2+b^2=p^2を満たす互いに素なa,bは必ず存在するでしょうか? 換言しますと、奇素数pについて 「x^2+y^2=n×pとなる整数の組x,y,nが存在する」と 「a^2+b^2=p^2となる互いに素な自然数の組a,bが存在する」は同値でしょうか? 先ほど似た質問をさせていただいたのですが、 http://okwave.jp/qa/q6216192.html 私が確認してるのは「互いに素」でしたので改めて質問し直しました。 私の確認したところでは 2平方数の和がpの倍数にならないもの→3,7,11,19 2平方数の和がp倍数になり、且つp^2を満たすa,bが存在するもの→5,13,17 3^2+4^2=5^2, 5^2+12^2=13^2, 8^2+15^2=17^2
- ベストアンサー
- 数学・算数
- 整数の問題
整数(?)の問題です。よろしく御指導下さい。 1)3つの自然数a,b,cがa~2+b~2=c~2を満たしている。このとき、a,bの少なくとも一方は偶数であることを証明せよ。 2)自然数はa,b,c,dはc=4a+7b,d=3a+4bを満たしている。 2-1) c+3dが5の倍数ならば、2a+bも5の倍数であることを示せ。 2-2) aとbが互いに素で、cとdがどちらも素数pの倍数ならば,p=5であることを示せ。. (2-1は解決済みです。2-2の方がよく分かりません) 尚、このような整数、約数、倍数、素数、互いに素 というような問題(例題)を扱った 参考書、WEB サイト等ありましたら、ご紹介いただければありがたいです。よろしくお願いします。
- ベストアンサー
- 数学・算数
- 2週間前に使えるようにしたプリンタが、今日使用したところエラーが出て印刷ができません。
- ブラザーユーティリティなどを参考にしましたが、エラーが解消されません。
- DCP-J926N-Wモデルのプリンタについての質問です。お願いいたします。
お礼
ありがとうございます。 意外と高度な議論が必要なのですね…。 私が 1^k≡1 2^k≡1 3^k≡1 …… (p-2)^k≡1 (p-1)^k≡1 をいじり回していてもどうにもならなかったわけです…。