プロが教える店舗&オフィスのセキュリティ対策術

次の結果は初等的に証明することができるとかいてあったのですが、つまずいています。
g_pは法pでの最小の原始根( 1<g_p<p )のことです。
すべての素数について原始根g(1≦g≦p-1)が存在するのは理解できたのですが、最小といいますか最小の原始根は1だろうと思いますが、1でない次の原始根がMとp-Mの間に入るのは、帰納法ですと、まずM=2についてg_pが間に入る素数は原始根の表から一つは見つかりますが、無限に多くの素数があるかどうかで詰まっています。

A 回答 (4件)

まず注意


「最小といいますか最小の原始根は1だろうと思いますが」
とありますが、全く違います。

自然数aが素数pの原始根となるとは
p-1乗して初めてa^(p-1)≡1 (mod p)となることをいいます。
(よって、a,a^2,…a^(p-2)はmod pで1と合同ではありません)

したがって、1^1≡1 (mod p)となるから
1はpの原始根にはなりえません。
    • good
    • 0
この回答へのお礼

そうでした、ありがとうございました。
すごい、間抜けに我ながら反省しました。

お礼日時:2005/09/25 09:41

No.2の訂正


「その前に二つのことを確認」
ではなく
「その前に五つのことを確認」
    • good
    • 0

最後にp≡1 (mod m)となる素数が無数に存在すること(Dirichletの素数定理の特別な場合)の証明が書かれたページへのリンクを張っておきます。



参考URL:http://aozoragakuen.sakura.ne.jp/suuronN/node39. …
    • good
    • 0

「任意の正の整数Mに対して、M<g_p<p-Mとなる最小の原始根g_pが取れる無限に多くの素数pが存在する」ことを証明します。



その前に二つのことを確認
(1)
(a/p)をルジャントルの記号とします。
(a/p)=1となるとき、aはpの原始根ではない。
(1)の説明
a^{(p-1)/2}≡1 (mod p)となるのでaの位数は(p-1)/2の約数となるからです。
pの原始根gの位数はp-1です。
(1)の説明ここまで
(2)
pをp≡1 (mod 4)となる素数、qも素数とすると
(q/p)=(p/q)、(-1/p)=1
(2)の説明
平方剰余の相互法則と第一補充法則より明らか
(2)の説明ここまで
(3)
pをp≡1 (mod 8)となる素数とすると
(2/p)=1
(3)の説明
平方剰余の相互法則の第二補充法則より明らか
(3)の説明ここまで
(4)
m≡n (mod p)となるとき、(m/p)=(n/p)
(4)の説明
(m/p)≡m^{(p-1)/2}≡n^{(p-1)/2}≡(n/p)
したがって、(m/p)=(n/p)となる
(4)の説明ここまで
(5)
(mn/p)=(m/p)*(n/p)
(4)の説明
(mn/p)≡(mn)^{(p-1)/2}≡m^{(p-1)/2}*n^{(p-1)/2}≡(m/p)*(n/p)
したがって、(mn/p)=(m/p)*(n/p)となる
(4)の説明ここまで

さて、「任意の正の整数Mに対して、M<g_p<p-1となる無限に多くの素数pが存在する」ことを証明します。

「q_1、…、q_kをM以下の奇数の素数します。
p≡1 (mod 8*q_1*…*q_k )…※
となる素数pをとると
(2/p)=…=(M/p)=( (p-2)/p)=…=( (p-M)/p)=1となること」…○
を示します。
2≦a≦Mとなる自然数aをとる

○の証明に、上で説明した(2)~(5)を説明なしで用います

○の証明ここから

aが奇数のとき
a=Πq_i(q_iの積の意味)
(a/p)=Π( (q_i)/p)=Π(p/(q_i) )=Π(1/(q_i) )=1
( (p-a)/p)=( (-a)/p)=(-1/p)(a/p)=1*1=1
aが偶数のとき
a=(2^n)*b(bは3以上の整数)のとき
b=Πq_i
(a/p)=(2/p)^n*Π( (q_i)/p)=Π(p/(q_i) )=Π(1/(q_i) )=1
a=2^nのとき
(a/p)=(2/p)^n=1
( (p-a)/p)=( (-a)/p)=(-1/p)(a/p)=1*1=1
したがって、pを※のように取ると
(2/p)=…=(M/p)=( (p-2)/p)=…=( (p-M)/p)=1となることがわかる。

○の証明ここまで

上で注意した(1)より、1,2,…,M,p-M,p-M+1,…,p-1はpの原始根にはなりえません。
Dirichletの素数定理より※のような素数は無数に取れます。

よって、○より任意の正の整数Mに対して、M<g_p<p-Mとなる最小の原始根g_pが取れる無限に多くの素数pが存在することがいえました。
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!