■43054 / inTopicNo.12) |
Re[7]: m∈Nとする。x∈Zがm割り切れないなら,xy≡1(mod m)なるy∈Zが存在するを
|
□投稿者/ らすかる 大御所(959回)-(2010/11/19(Fri) 11:49:30) http://www10.plala.or.jp/rascalhp
| > > ・なぜ「y(kp+r)=lp+1」としているのに「(lp+1)÷(kp+r)=q,余りs」と > > 余りが出るのですか? > > 一応,但し0≦s<kp+r)としておりますが,,, > 余りが出ない場合はs=0という事です。
「y(kp+r)=lp+1」としたのなら余りは出ませんから「余りs」の意味がないですね。
x<0のとき、(-x)y≡1 (mod m) となるyが存在すれば x(-y)≡1 (mod m) となりますので、x>0のときだけ示せば十分です。 よって簡単のためx>0とします。 1≦k≦m-1 に対し、kxをmで割った余りをr[k]とします。 もしr[i]=r[j](1≦i<j≦m-1)とすると jx-ix=(j-i)xはmで割り切れて条件と矛盾しますので、 r[1],r[2],…,r[m-1]はすべて異なります。 1≦r[k]≦m-1 ですから、r[1]〜r[m-1]のどれかが1です。
|
|