mod の話

mod についてまとめておこう。今回は余談にならぬよう…。

前回、余りの定義を書いた。次のようなものだ。

余りの定義（自然数）
a を b で割ったときの商 q と余り r を、次式で定義する。

a＝bq ＋r（0≦r＜b）

ここで a, b は自然数、q, r は自然数または0とする。

自然数だけでなく、整数でも使えるようにしよう。ゼロ割りをしないように b≠0 として、余りの条件の不等式に b が負数のときも考えて絶対値 |b| を使う。

余りの定義（整数）
a を b で割ったときの商 q と余り r を、次式で定義する。

a＝bq ＋r（0≦r＜|b|）

a, b, q, r は整数で、b≠0 とする

商は英語で quotient、余りは remainder なので、商を q、剰余（余り）を r で表すことが多い。

mod は、剰余（余り）を求める演算である。整数での余りの定義を使って、mod を次のように定義する。

mod の定義（整数）
a, b, q, r は整数で、b≠0 とする。

a mod b ＝r　⇔　a＝bq ＋r（0≦r＜|b|）

たとえば、7 を 3 で割ると、商は 2 で、余りは 1 となる。mod を使って書くと、次のようになる。余りの定義式の方での様子も書いておく。

7 mod 3 ＝1　⇔　7＝3✕2＋1

7 を -3 で割ると、商は -2 で、余りは 1 となる。

7 mod (-3) ＝1　⇔　7＝(-3)✕(-2)＋1

10 を 3 で割ると、商は 3、余りは 1。

10 mod 3 ＝1　⇔　10＝3✕3＋1

7 と 10 は同じではないが、7 を 3 で割った余りと、10 を 3 で割った余りは等しい。このことを次のように書く。

7 ≡ 10（mod 3）

記号≡の名前（読み方）は知らないが、合同を表す。＝を使った式を等式というが、≡を使った式を合同式という。7 ≡ 10（mod 3）という合同式は「3 を法として、7 と 10 は合同である」と読む。mod は modulo の略で、法とか剰余という意味。

a ≡ b (mod m)　⇔　a mod m ＝ b mod m

である。

先の例で、7 を 3 で割った余りと、7 を -3 で割った余りが等しくなったが、7 mod 3 ＝ 7 mod (-3) という書き方は見たことがない。当然、割る数が負数であること割る数が異なるので合同式には表せない。また、mod の演算は「剰余による分類」がメインであるためであろう、負数を法とすることは稀である（調べていないのでないとは言い切れない）。

また、a mod m ＝ b mod m を次のように書くこともできる。

(a－b) mod m ＝0

m を法として合同な数同士の差は、m の倍数になることを示している。

mod の言い換え
a, b, m は整数で、m≠0 とする。
a ≡ b（mod m）　　m を法として合同
⇔　a mod m ＝ b mod m　　m で割った余りが等しい
⇔　(a-b) mod m ＝0　　差が m の倍数

合同式について、a ≡ b（mod m）のとき、以下が成り立つ。

a＋C ≡ b＋C (mod m)　　両辺に足しても合同
a－C ≡ b－C (mod m)　　両辺から引いても合同
a✕C ≡ b✕C (mod m)　　両辺に掛けても合同

しかし、等式とは異なり、除算（割り算）では成り立たない場合がある。

たとえば、12を法として、15と75は合同である。

15 ≡ 75 (mod 12)

両辺を3で割った場合は、合同ではない。

(15÷3) mod 12 ＝ 5 mod 12 ＝ 5
(75÷3) mod 12 ＝ 25 mod 12 ＝ 1

両辺を5で割った場合は、合同である。

(15÷5) mod 12 ＝ 3 mod 12 ＝ 3
(75÷5) mod 12 ＝ 15 mod 12 ＝ 3

合同式では、上の例でいうと、法となっている12と、1以外の共通の約数を持っていない場合、つまり互いに素な数であれば除算が可能である。12と3は互いに素ではない。12と5は互いに素である。

合同式と除算
a, b, C, m を整数とする。
C が m と互いに素のとき、以下が成り立つ。

a✕C ≡ b✕C (mod m)　⇒　a ≡ b (mod m)

「余り」の話

mod についてまとめておこう。

と思ったが、ここでは脱線した内容で終えている。

mod などと書いているが、簡単にいうと「余り」である。小学校の算数・割り算での「７÷３＝２…１（７割る３は２、余り１）」の「余り」である。少し難しくいうと「剰余」という。小数や分数などを学び、「余り」を意識して使うことはあまりない（と言ってみたかっただけです）。

「余り」自体を意識することはあまりないが、「剰余による分類」は無意識のうちに使っている。たとえば奇数と偶数。奇数は２で割って１余る数で、偶数は２で割り切れる数。余りの数で奇数と偶数に分類している。またたとえばワークショップなどで３つのグループに分けるときに「こっちから、１・２・３、１・２・３と番号を言ってください」と言って、１のグループと２のグループと３のグループに分けたりする。これも考えようによっては「剰余（余り）による分類」である（ただし、３で割って余り３とは言えないので少し修正は必要だが）。他にも、時間（15時を3時と言ったりする）や、数字でない例を挙げると、曜日なども「剰余による分類」と考えることができる。

今日は2019年11月7日で木曜日だが、7日後の11月14日も木曜日である。11月1日が金曜日であるため、金曜日を「1」として、「金＝1、土＝2、日＝3、月＝4、火＝5、水＝6、木＝0」とすると、11月の何日かがわかれば、7で割って余りを調べることで、何曜日なのかがわかる。たとえば、（2019年11月）20日ならば、「20÷7＝2…6」となるので水曜日である。

このとき、20÷7の答え（商という）にはあまり注目していない。商ではなく、余りに注目した演算が mod である。

割られる数を a、割る数を b、商を q、余りを r として数式を書くと、

a = bq + r (0≦r＜b)

となる（a, b, q, r は自然数または 0 とする）。r は余りなので、0≦r＜b という条件がついている。「20÷7＝1…13」のように、余り（r）が割る数（b）より大きくなってはいけない。

ちょっと思い出したが、ガロア理論を勉強している本のひとつ、中村享『ガロアの群論』の一番最初に、一次方程式の話への導入で「盗人算」の紹介があった。吉田光由の『塵劫記』（江戸時代の算数の本）に載っている次のような問題だ。

　盗賊団の会話が、橋の下から聞こえる。盗んできた反物を分配しようとしているようだ。「７反ずつ分けると８反余るし、８反ずつ分けると７反足りない。どうしたものかなあ」
さて、盗賊は何人で、反物は何反あるか。

『塵劫記』では答えとして、「盗賊は８足す７で15人、反物は15人掛ける８反に７反足りないから113反」としか載っていない。盗賊の人数を x として、方程式を立てて――と話が続く。そして『塵劫記』には（盗人算として）これ１問しか出ていないので、「盗賊の人数や盗品の数が違っても、読者は解けたのだろうか？」として、数字を変えた盗人算の例を挙げる。

　盗賊団の会話が、橋の下から聞こえる。盗んできた反物を分配しようとしているようだ。「７反ずつ分けると６反余るし、９反ずつ分けると４反足りない。どうしたものかなあ」
さて、盗賊は何人で、反物は何反あるか。

そして方程式を立てて、盗賊の人数は５人、反物は41反という答えを出す。

簡単な方程式でもあり、答えや解き方などに疑問点はないのだが、ただ１点だけ気になるところがある。それは、問題文の「７反ずつ分けると６反余る」というのはおかしいのでは？ということだ。盗賊の人数が５人なら、７反ずつ分けて６反余らせるのではなく、「８反ずつ分けて１反余る」としたほうがいいんじゃないかと思う。

これでは、「余談」である。お後がよろしいようで。
（mod についてのまとめは、また後日。）


あ、『ガロアの群論』自体は、（まだしっかりと理解できていないところもありますが、）ガロアの考えたことを丁寧にたどって、方程式が解ける条件を解説したいい本です。