n-1個の自然数1,2,..,n-1から重複を許して２つの数を選び順列をつくる。順列は全部で(n-1)^2個できるが、この中に２つの数の積をnで割ったあまりが1になるものがちょうどn-1個あるとき、またそのときに限り、nは素数であることを示せ
お願いします
|
No.15708 - 2011/11/06(Sun) 18:28:45
| ☆ Re: 素数証明 / ヨッシー  | | | 補題
自然数ｎに対して、それと互いに素な自然数をｋとする。
連続するｎ個の数列
m, m+k, m+2k, ・・・, m+(n-1)k
には、ｎで割った時のあまりが
0, 1, 2, ・・・, n-1
であるものが１つずつ存在する。
証明
ｎで割った時のあまりが
0, 1, 2, ・・・, n-1
であるものが１つずつ存在しないとすると、
m, m+k, m+2k, ・・・, m+(n-1)k
の中にｎで割った時のあまりが同じものが２つ以上ある。
それらを、α、β（α＜β）とすると、
α＝m+sk＝xn＋r
β＝m+tk＝yn＋r (s,t,x,y,r は自然数)
と書けるので、
β−α＝(t-s)k＝(y-x)n
となるが、(y-x)n はｎの倍数であるのに対し、t-s＜n かつ
kはｎと互いに素なので、(t-s)k はｎの倍数となり得ず、
この式は矛盾している。
以上により、補題は証明された。
本問
ｎが素数の時
1×1, 1☓2, ・・・1×(n-1) の中にｎで割った余りが１のものが1つ。
2×1, 2☓2, ・・・2×(n-1) の中にｎで割った余りが１のものが1つ。
・・・
(n-1)×1, (n-1)☓2, ・・・(n-1)×(n-1) の中にｎで割った余りが１のものが1つ。
以上より、ｎで割った余りが１のものが合計n-1個ある。
ｎが素数でない時
ｎと互いに素なｎ以下の数ｋについて
k×1, k☓2, ・・・k×(n-1) の中には、ｎで割った余りが１のものが１つだけ存在する。
ｎの１でない約数のひとつをａとすると、
a×1, a☓2, ・・・a×(n-1) の中には、ｎで割った余りが１のものは存在しない。なぜなら、
a×m (m は n-1以下の自然数) をｎで割った余りをｒとすると、
am＝sn＋r (sは自然数)
と書けるが、左辺は a の倍数であり、sn は a の倍数なので、
右辺が a の倍数であるためには、ｒがａの倍数でなければならず、
あまりは１となりえない。
以上より、
1×1, 1☓2, ・・・1×(n-1)
2×1, 2☓2, ・・・2×(n-1)
・・・・
(n-1)×1, (n-1)☓2, ・・・(n-1)×(n-1)
の各行において、ｎで割った余りが１のものは、たかだか１個であり、
０個の行も存在するので、その個数の合計はn-1より小さい。
以上より、題意は証明された。
|
No.15712 - 2011/11/06(Sun) 23:05:48 |
| ☆ Re: 素数証明 / 攻殻ファン  | | | 分かりやすい説明ありがとうございます
補題の証明はやった方が回答が正確になるんですか？
|
No.15732 - 2011/11/09(Wed) 00:14:55 |
| ☆ Re: 素数証明 / ヨッシー | | | 私は「自明」と言いきれるほどの材料を持ち合わせていませんので、証明しました。
見方によっては、この証明こそがこの問題のポイントではないかとも思えます。
|
No.15739 - 2011/11/09(Wed) 05:54:43 |
|
