剰余系
剰余系（じょうよけい）とは、整数論において「割った余り」で考える発想である。
概要[編集]
「原始ピタゴラス数の積は必ず・絶対に・例外なく六十の倍数である」みたいなことを証明するときなどに使える。わりと素朴な発想であり、「割切れない」ときにどうするか？」というので分数とか有理数とかいった発想に辿りついたらしい。
偶数・奇数などを考える偶奇性も2で割れるか否かということが出発点になっている発想なので、剰余系と言える。
「ナントカで割ったときの余り」で考えるわけだが、この「ナントカ」に入る数は「 2 以上の自然数」ということになる。このナントカを「法」と呼び、「mod」で表す。
たとえば 「 5 を法する」と 「 5 で割った余り」は {0, 1, 2, 3, 4} のどれかなので、これが n (mod 5)の世界になる。べつに負の数を法とした系を考えてもよさそうに思うが、実際やってみると嬉しいことは一つも起きなさそうなので興味を持つ人がいなくなったらしい。「最大公約数を求めるルーチンの(m,n)の少なくとも一つが 0 やマイナスだったらどうする？」みたいな話が出てきて、「 2 以上の自然数」という結論に達した。
モジュロ演算[編集]
剰余演算とも。割った余りに着目した演算。数学では「mod」、プログラミング言語では「%」を使って表記することが多い。
プログラミング言語では、負の数に対してどのように定義するかなどで異なるものがある。「 -2 % 3 」は原点から -3 まで移動してプラスの方に数えると 1 つめなので「1」だが、「2」を返す処理系もあるらしい。こういうおバカな処理系もあるので、言語処理系が変わったときはバリデーション・テストが欠かせない。
a≡b(mod p)と書いて、p を法としてaとbは合同を意味する。(つまり、a,bはpで割った余りが等しい、通常余りは0からp-1である)
加法(減法),乗法に関しては、わかりやすい性質が多い。一方、除法では計算が困難になりやすい。 プログラミング言語では割り算について、余りを考える「%」と単なる割り算の「/」を区別している。
性質[編集]
a≡b(mod p),c≡d(mod p)のとき以下が成り立つ
また、
- ak≡bk(mod p)かつkとpが互いに素ならばa≡b(mod p)(割り算)