原始根の和が0,-1,1のいずれかになることの証明

  • 公開日時: 2017/03/07 17:20
  • 閲覧数: 146
  • コメント数: 0
  • カテゴリ: 研究・考察

 

 

 

ある素数pの原始根の和を求める為に、原始根でない数の和を求める。

 

原始根とは(p-1)乗して初めて1になる、指数が(p-1)と互いに素な数のことを言うので、指数が(p-1)と互いに素でない数が原始根でない数だ。

 

例えば(p-1)が半素数で2qと書けるとき、指数が2の倍数の数とqの倍数の数を重複せずに出せれば、それが原始根でないすべての数だ。

 

ベン図を書けば分かるが、(2の倍数の数の和)+ (qの倍数の数の和)-(2qの倍数の数の和)(2の倍数あるいはqの倍数の数の和)

 

になっている。

 

指数が2の倍数の数の集合の和、指数がqの倍数の数の集合の和は0になる(証明は僕の「時計みたいな素数」という投稿を見て下さい)

 

しかし、指数が2qの倍数の数は1しかない

 

よって(2の倍数あるいはqの倍数の数の和)=-1で、p以下の全ての自然数の和が(mod pで)0になることも含めて考えると、原始根の和は1になる

 

この考え方で、包除原理を使って、(p-1)が素数の2乗で割り切れないとき、(p-1)の素因数の個数が偶数個なら原始根の和は1に、奇数個なら原始根の和は‐1になることが示せる

 

 

 

(p-1)がなにか素数の2乗で割り切れるとき、原始根の和は0になる

 

なぜなら、例えば(p-1)=2^2×q(qは素数)のとき、

 

(2の倍数の数の和)+ (qの倍数の数の和)-(2qの倍数の数の和)(2の倍数あるいはqの倍数の数の和)

 

となり、指数が2qの倍数の数の和も0になり(なぜなら1だけではなく-1も指数が2qの倍数の数だから)、原始根でない数の和が0になるからである

 

 

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

この投稿にフォローする

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

コメントはまだありません。