n^2=1(mod m)を満たすnの個数

  • 公開日時: 2017/01/01 08:52
  • 閲覧数: 221
  • コメント数: 1
  • カテゴリ: 研究・考察

 

一般にm(mは正の整数)を法とするとき、[式:…]=1(mod m)を満たすnの個数は、

 

m=2ならば1個、m=4ならば2個、m=8ならば4個、mが奇素数ならば2個、mが奇数の半素数(ただし素数の2乗ではない)ならば4個、ma個の素因数を持つ奇数ならば、[式:…]個である

 

ma個の素因数を持つ偶数(ただし4の倍数ではない)ならば[式:…]個で、ma個の素因数を持つ4の倍数(ただし8の倍数ではない)ならば[式:…]個で、ma個の素因数を持つ8の倍数ならば[式:…]個である

 

 

 

■証明

 

[式:…]=1(mod m)(n-1)(n+1)=0(mod m)と式変形でき、

 

mを法とするときの[式:…]=1(mod m)を満たすnの個数は?という問いは、

 

nm以下の正の整数とするとき、 (n-1)(n+1)mの倍数になるようなnの個数は?

 

という問いに変えることができる

 

 

 

まずは、ma個の素因数を持つ奇数ならば、nの個数が[式:…]個であることを示そうと思う

 

(n-1)(n+1)は、nが偶数のとき、奇数になり互いに素、nが奇数のとき、最大公約数が2になるが、mは奇数なので関係ない

 

ma個の素因数を持つ奇数なので、ある素因数を(n-1)(n+1)のどちらに入れるか。という選択がa回できるので、mの倍数となるような(n-1)(n+1)の個数が[式:…]個であることが分かる。

 

 

 

次は、ma個の素因数を持つ偶数(ただし4の倍数ではない)ならば、nの個数が[式:…]個であることを示そう

 

mを法とするときの要素は[式:…]を法とするときの2倍あるが、(n-1)(n+1)が偶数である必要があり、(n-1)(n+1)が奇数である場合を除かなければならないので、結局mの倍数になるような(n-1)(n+1)の個数は[式:…]のときと変わらない。

 

m2という素因数を除くと、(a-1)個の素因数を持つので、ある素因数を(n-1)(n+1)のどちらに入れるか。という選択が(a-1)回できるので、mの倍数となるような(n-1)(n+1)の個数が[式:…]個あることが分かる。

 

 

 

次は、ma個の素因数を持つ4の倍数(ただし8の倍数ではない)ならば、nの個数が[式:…]個であることを示そう

 

mを法とするときの要素は[式:…]を法とするときの4倍ある

 

(n-1)が偶数のとき(n+1)も偶数になり、(n-1)(n+1)が偶数であれば、4の倍数である

 

なので(n-1)(n+1)が奇数である場合を除けば(n-1)(n+1)4の倍数なので、2で割ればよく、

 

[式:…]を法とするときの2倍要素が残る

 

m2という素因数を除くと、(a-1)個の素因数を持つので、ある素因数を(n-1)(n+1)のどちらに入れるか。という選択が(a-1)回できるので、mの倍数となるような(n-1)(n+1)の個数が[式:…]個あり、これに2を掛けて[式:…]個である。

 

 

 

ma個の素因数を持つ8の倍数ならば、nの個数が[式:…]個であることも同様にして示せる

 

 

 

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

この投稿にフォローする

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

全件表示

No メッセージ 投稿者 日時    
1
mod mで2乗すると1になる数の個数が必ず2のべき乗個であることの証明だけなら、他のやり方がありました

ある数xが2乗すると1になるとき、-xも必ず1になるのでこれからはまとめて±xと書くことにする
±1はどんなmをとっても2乗すると1になる。±1のみが2乗すると1になる数のとき、個数は2個だ

±1の他に2乗すると1になる数±aがあって、それ以外2乗すると1になる数がないとき、個数は4個だ

±1,±aの他に2乗すると1になる数±bがあったとき、±abも2乗すると1になる数になる なぜなら、a^2=1,b^2=1なので、(ab)^2=1になるからである
ただしab=1でないことの証明が必要だが、難しくはない。a^2=1なのでab=a^2、つまりa=bとなるが、a≠bなので、abは1ではない
また、a/bやb/aも2乗すると1になる数だが、a/b=b/a=abなのでカウントする必要がない
何故a/b=abなのかと言えば、両辺にbを掛けるとa=ab^2となり、b^2=1なのでa=aとなるからである
±1,±a,±b,±ab以外2乗すると1になる数がないとき、個数は8個で、2のべき乗になっている

2乗すると1になる±1,±a,±b,±abと異なる数±cがあるとき、±ac,±bc,±abcも2乗すると1になる数なので、それ以外に2乗すると1になる数がないとき、個数は16個になる

このように考えることで2乗すると1になる数の個数が必ず2のべき乗個になることが分かる
あ・あっくん さん 2017/03/24 20:58:58 報告