SEA
解説
■合同式
=3のとき
+2=5,
+4=7
aとbがm を法として合同であるとき,次の関係が成り立つ。
「合同」という用語は、
図形で用いられてき
a=b(mod m) 歌のときちうるうたが,ここでは、多
a-bgmの倍数 [a-b=mk (k は整数)]
(αをmで割った余り)=(bmで割った余り)
定義
自
②
数に関する合同を考
える。
mod は, modulus
[説明 a=mg+r,b=mg'+r(0≦x<m,0≦x<m)とすると「法」という意味
a-b=m(g-g)+r-r
①, -m<r-r'<m
a=b (mod m) のとき,a-b は m の倍数であるから,r-rもの倍
数である。 ここで, ② の範囲にあるm の倍数は0のみであるから
rr=0 すなわ
逆に,r=r' のとき,① から a-b=
(大したがって, a-bはの倍数である。
例
23=3・7+2,5=3・1+2 であるから
13=7・1+6, -8=7・(-2)+6であるから
に由来している。
①の左辺はmの倍
数であり,右辺の
(g-g)もの倍
数であるから,
でなければならない。
Tecor-r's m
23=5 (mod3)
13=-8 (mod 7)