| ■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です。
|
|