原始根があることの証明

  • 公開日時: 2017/02/11 18:48
  • 閲覧数: 702
  • コメント数: 5
  • カテゴリ: 教養・雑学

原始根があることの証明を読んでも僕には難しくて、しっかりとは分からなかったので、自分で考えてみました

 

 

 

フェルマーの小定理より、a{1,2,3,……,p-1}のとき、a^(p-1)=1(mod p)である(pは素数)

 

位数がp-1aが必ず存在することが示せれば、原始根があることが証明できる

 

 

 

■証明

 

原始根がないと仮定する

 

すべてのaの位数が(p-1)より小さいということになるが、フェルマーの小定理より、位数は必ず(p-1)の約数だ

 

位数が (p-1)の約数になる(p-1)未満の数が、必ず(p-1)個より少ないことが示せれば、位数が(p-1)の数が必ず存在することが分かり、つまり原始根があることが分かる

 

位数が4の4つの数と位数が6の6つの数があるとき、2つの数がダブってしまう(ダブった数は位数が2だ)

位数をすべて互いに素にしないと数がダブってしまうのだ

なので(p-1)より小さい(p-1)の約数になる位数の数の個数を調べるなら、(p-1)を素因数分解し、素因数ごとに個数を調べればよい(それでも、位数が1の数(つまり1)がダブってしまうのだが)

 

(p-1)=x[1]^y[1]×x[2]^y[2]×……×x[n]^y[n](xはそれぞれ互いに異なる素数、yは自然数)とする

 

上に書いたように素因数ごとに個数を調べればよく、b乗するとcになる数の個数は多くてもb個なので、

 

 (p-1)より小さい(p-1)の約数になる位数の数の個数は多くても(x[1]^y[1]+x[2]^y[2]+……+x[n]^y[n])個になることが分かる

 

xの個数が2個以上なら(x[1]^y[1]+x[2]^y[2]+……+x[n]^y[n])<(x[1]^y[1]×x[2]^y[2]×……×x[n]^y[n])なので、証明できる

 

xの個数が1個のときもaの位数が(p-1)より小さいことを考えれば、aの個数が(p-1)より少ないことが分かるので、証明できる

 

よって、位数がp-1aが必ず存在し、原始根は存在する

 

 

 

公序良俗に反する不適切な投稿を発見された方はこちらよりご報告ください

この投稿にフォローする

コメントをつけるにはログインが必要です。

全件表示

No メッセージ 投稿者 日時    
1
証明に間違いがあったので、修正しました
すみません、まだ間違いがありそうです
水宮うみ さん 2017/06/12 17:26:54 報告
2
ちゃんとした証明思いつきました

modpにおいて、すべての数の位数は、必ずそのなかで一番大きい位数の約数になっている。という補題を使って証明します。

■補題の証明
x,yを自然数とし、x,yのうちのどちらかが、もう一方の倍数になっていないとする
また、pを素数とする
mod pにおいてaの位数がx、bの位数がyであるとするとき、(ab)の位数はx,yの最小公倍数になる
ab≠1(mod p)のときとab=1(mod p)のときに分けて考える
以下ではmod pを省略して書くことにする

・ab≠1のとき
(ab)^z=1(zは自然数)であるためにはa^z=1かつb^z=1でなければならず、一番小さいzはx,yの最小公倍数になる

・ab=1のとき
そもそもab=1になることがないことをこれから示す
ab=1になる為には、bがaの逆数でなければならない。
しかし、aの逆数の位数はaと同じはずであり、aとbの位数は違う値なので矛盾
よってaとbの位数が違うとき、ab=1になることはない

補題によって、modpにおける全ての数の位数の最小公倍数を位数に持つ数が存在することが分かった。

mod pにおいて一番大きい位数をNとすると、すべての数がN乗して1になる。N乗して1になる数の個数はN個で、mod pにおける0以外の数の個数は(p-1)なので、Nはp-1に等しい

よって、素数を法とするとき原始根が存在することが分かる

間違っているところや、分かりづらいところがあれば教えてください

すみません、間違いを見つけました
また、修正できるか考えます
水宮うみ さん 2017/07/04 11:01:53 報告
3
お邪魔します。

〔新しい補題の補題〕
mod p において aの位数がx、bの位数がyであるとき、位数がz(x,yの最小公倍数)である元(a^j)(b^k)が存在する。


b ≠ {1, a, aa, …, a^(x-1), a^x≡1} = <a>
とします。
(右辺を、aが生成する巡回部分群(Z_x)とか言うらしいです。)

a ≠ 原始根(x < p-1)ならば、そのようなbは存在します。
しかしながら、y|x でないことは自明ではありません。

ご指摘のように、k^x ≡ 1(mod p)となる k はx個しかなく、<a> の元に限ります。
そこで、y|x だったと仮定すると、
 b^x = (b^y)^t ≡ 1^t = 1 (mod p)
∴ b ∈ <a> これはbの定義に反します。
よって y|x ではなく、z =(x,yの最小公倍数)≧ 2x。

新しい補題の補題から、位数がzである元(a^j)(b^k)が存在する。
 (下記を参照)

∴ x < p-1 のとき aは位数が最大の元ではない。
∴ p-1 ≦ N

一方、フェルマーの小定理より、
N|(p-1)

したがって、N=p-1
prime_132 さん 2017/07/06 07:52:59 報告
4
新しい補題の補題については、次を参照。

青空学園
http://aozoragakuen.sakura.ne.jp/suuron/node35.html#SECTION00251010000000000000
prime_132 さん 2017/07/06 08:07:17 報告
5
prime_132さん、いつも証明してくれてありがとうございます
自分なりに>>2を修正して、ちゃんとした証明に直してみました

>>2の補題の補題は間違っていました

※>>2の補題の補題
mod pにおいてaの位数がx、bの位数がyであるとするとき、(ab)の位数はx,yの最小公倍数になる

けれど、新しい補題の補題で、>>2の補題を証明でき、原始根が存在することを証明できることに気付きました

※>>2の補題
modpにおいて、すべての数の位数は、必ずそのなかで一番大きい位数の約数になっている

新しい補題の補題は、このようなものです
mod pにおいてaの位数がx、bの位数がyであるとするとき、x,yの最小公倍数zを位数にもつようなa^j×b^k(j,kは自然数)が必ず存在する

>>2の補題の補題の反例をまずあげます
■mod61のとき、aの位数が6、bの位数が10であるとする
abの位数は15になり、6と10の最小公倍数にならない
(abの位数が15になることは、(ab)^15=a^15×b^15=a^3×b^5=(-1)×(-1)=1という計算から分かる)
よって、>>2の補題の補題は間違っています


新しい補題の補題が真であることを、この例を使って説明します
■aの位数が6なので、a^2の位数は3である
a^2×bの位数は30になり、6と10の最小公倍数になる
なぜなら、(a^2×b)^z、つまりa^2z×b^zを考えるとき
a^2zのとりうる位数は1,3、b^zのとりうる位数は1,2,5,10で
ある数とある数が逆数の関係になるには位数が同じにならなければならないので、
a^2zの位数とb^zの位数が、唯一の同じ数である1にならなければならない。つまり、
a^2z×b^z=1になるにはa^2z=1かつb^z=1でなければならないからである

今から新しい補題の補題を証明する
xとyのどちらかがどちらかの倍数のときは、xとyの最小公倍数がx,yどちらかになるので、これからxとyのどちらかがどちらかの倍数になっていない場合を考える
dの位数をh、eの位数をi、hとiが互いに素とするとき、(de)の位数が(hi)になるのは上記の例で見た通りである
d=a^j,e=b^kとおく(つまりx=jh、y=kiとなる)
hi=z(zはx,yの最小公倍数)となるようなjkを置くことは可能なので
位数がzになるような(a^j×b^k)は存在する

新しい補題の補題の証明終わり
って感じです
水宮うみ さん 2017/07/07 15:37:52 報告