合同式と剰余算 — 時計算、mod、合同

合同式と剰余算とは、法と呼ばれる固定した正の整数で割ったあとの余りに注目して計算する考え方です。2つの数が同じ余りをもつなら、その法のもとでは同じように振る舞います。これが「時計算」と呼ばれる理由です。

$12$時間制の時計では、13時は1時の位置に来ますし、29時間後も5時間後と同じ位置に来ます。この繰り返しの感覚が、合同式と剰余算の基本的なイメージです。

剰余算での Mod の意味

整数 $a$ と正の整数 $n$ に対して、$a \bmod n$ は $a$ を $n$ で割ったときの余りを表します。

例：

$$29 \bmod 12 = 5$$

なぜなら

$$29 = 12 \cdot 2 + 5$$

だからです。

法は $12$ なので、$12$ を足したり引いたりしても、この周期の中での位置は変わりません。

法 $n$ における合同の意味

合同とは、2つの整数が法 $n$ で同じように振る舞うことを表す正式な言い方です。

$$a \equiv b \pmod n$$

これは、$a$ と $b$ を $n$ で割ったときの余りが同じであることを意味します。同値な判定方法として

$$n \mid (a-b)$$

があります。これは「$n$ が $a-b$ を割り切る」という意味です。

したがって

$$29 \equiv 5 \pmod{12}$$

です。なぜなら $29 - 5 = 24$ で、$12$ は $24$ を割り切るからです。

この違いは重要です。

• $29 \bmod 12 = 5$ は余りについての式です。
• $29 \equiv 5 \pmod{12}$ は合同についての式です。

両者は関係していますが、同じものとして使うことはできません。

例題：8時の29時間後

今が8時だとして、$12$時間制の時計で29時間後が何時かを考えます。

まず、$29$ を法 $12$ で簡単にします。

$$29 \bmod 12 = 5$$

つまり、29時間足すことは5時間足すことと同じ効果をもちます。

$$8 + 29 \equiv 8 + 5 \pmod{12}$$

すると

$$8 + 29 \equiv 13 \equiv 1 \pmod{12}$$

となります。

したがって、時計は1時を指します。

重要なのは、最初に簡単にするこの操作です。法 $12$ では、$29$ を $5$ に置き換えても答えは変わらず、計算がずっと楽になります。

先に簡単にすると問題が解きやすくなる理由

大きな数は、それと合同なより小さい数に置き換えると扱いやすくなることがよくあります。

たとえば、法 $7$ では

$$100 \equiv 2 \pmod 7$$

です。なぜなら $100 - 2 = 98$ は $7$ で割り切れるからです。問題が法 $7$ での値だけを気にしているなら、$100$ の代わりに $2$ を使えます。

よくある間違い

等号と合同を混同する

$29 \equiv 5 \pmod{12}$ は $29 = 5$ という意味ではありません。法 $12$ において同じ余りの類に属する、という意味です。

法が重要だということを忘れる

$17 \equiv 5 \pmod{12}$ は正しいですが、$17 \equiv 5 \pmod{10}$ は正しくありません。合同は必ず特定の法に対して成り立ちます。

mod を普通の割り算のように扱う

$29 \bmod 12$ は余りの $5$ です。商の $2$ でもなく、分数の $29/12$ でもありません。

ソフトウェアの % がいつも同じ数学的約束に従うと思い込む

正の数では、プログラミング言語の % は多くの場合、生徒が最初に学ぶ余りの考え方と一致します。負の数では約束が異なることがあるため、多くの数学の授業で使う最小の非負剰余と結果が一致しない場合があります。

合同式と剰余算はどこで使われるか

値が周期的に繰り返す場面では、合同式と剰余算が現れます。時計、曜日、チェックディジットの仕組み、ハッシュ、そして整数論の多くの場面で使われます。

暗号でも使われますが、基本の考え方は同じです。数を余りによって分類し、合同な数をその体系の中で同等なものとして扱います。

似た問題に挑戦してみよう

月曜日の100日後は何曜日でしょうか。曜日は法 $7$ で繰り返すので、まず答える前に $100$ を法 $7$ で簡単にしてみましょう。

別の例でも比べてみたいなら、GPAI Solver で自分なりの問題を試して、先に簡単にすると計算が短くなるか確かめてみてください。