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

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

 

 

 

ある素数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になるからである

 

 

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

この投稿にフォローする

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

全件表示

No メッセージ 投稿者 日時    
1
一般化できることに気付きました
pを素数とし、nを(p-1)の約数とする
modpにおいて位数がnのすべての数の和は、nが素数の2乗で割り切れるときは0に、nが素数の2乗で割り切れないとき、nの素因数の個数が偶数個なら1に、奇数個なら‐1になる
証明は上の投稿の内容と同様にしてできます

特に、qを(p-1)の約数になっている素数とするとき、位数がqの数の総和が必ず-1になっていることが面白いと思いました
水宮うみ さん 2017/07/19 13:44:41 報告
2
このことから、
Nを2以上の自然数とするとき
(Nの、平方数を素因数に持たない、素因数の個数が奇数の約数の個数)=(Nの、平方数を素因数に持たない、素因数の個数が奇数の約数の個数)
となっていることに気付きました

例をあげると
6の約数=1,2,3,6
平方数を素因数に持たない素因数の個数が偶数のもの――1,6
平方数を素因数に持たない素因数の個数が奇数のもの――2,3

30の約数=1,2,3,5,6,10,15,30
平方数を素因数に持たない素因数の個数が偶数のもの――1,6,10,15
平方数を素因数に持たない素因数の個数が奇数のもの――2,3,5,30
というような感じです

証明は、投稿内容と>>1で書いたことと位数がm(mは2以上の自然数)の約数になっているすべての数の総和が0になっていることから証明できます
他のもっとシンプルな証明方法も、あるような気はします
水宮うみ さん 2017/07/19 23:54:03 報告
3
>>1

「原始根の和と円分多項式」(7/16)にもありますね。

位数が「nまたはその約数」である元xは x^n - 1 ≡ 0(mod p)のn個の根ですね。

位数が「ちょうどn」である元xは、上記から 位数d<n の元
 d|n、d<n、x^d - 1 ≡ 0(mod p)
を除いたもの、つまり円分多項式
 Φ_n(x)≡ 0(mod p)
のφ(n)個の根になりますね。
 Φ_n(x)=(x^n - 1)/{Π[d|n、d<n] Φ_d(x)},
 φ(n)はオイラーの関数。

p'が素数のときは
 Φ_p'(x)=(x^p' - 1)/(p'-1)= x^(p'-1)+ x^(p'-2)+ …… + x + 1
 なので右辺 p'-2 次の係数は1.

さてφ(n)個の根の和は、根と係数の関係から、Φ_n(x)の φ(n)-1 次の係数×(-1)で、
 nが平方因子をもつとき ・・・ 0
 nが square-free のとき ・・・ (-1)^(nの素因数の個数)
ですね。

とくに原始根の場合は、位数nがp-1です。
p-1 が square-free のとき原始根はたしかに存在します。


>>2
Nが平方因子をもたないとき、その約数は、Nの素因数のいくつかの積です。
偶数個の素因数の積と、奇数個の素因数の積は、同数ありますね。
prime_132 さん 2017/08/02 22:59:28 報告