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)