合同式ごうどうしきと mod 演算えんざんの基本きほん

date2026-03-28description合同式と mod 演算を、余りの計算規則としてではなく、剰余類の上での演算として正当化しながら説明します。prerequisites整数の性質の基本 / 同値関係と剰余類の基本type講義statusactive

mathabstract-algebrahighschoolundergraduatelecture

導入どうにゅう

この講義こうぎで最重要さいじゅうようなのは、 $a \equiv b [PARSE ERROR: Undefined("Command(\"pmod\")")] n$ とは「余あまりが同おなじ」という略記りゃっきであると同時どうじに、「剰余類じょうよりるいでは同おなじ元げんを表あらわす」という意味いみを持もつことです。

高校数学こうこうすうがくでは、ふつう合同式ごうどうしきを「余あまりで計算けいさんする道具どうぐ」として使つかいます。しかし大学数学だいがくすうがくでは、なぜ足たし算ざんや掛かけ算ざんをしてよいのかを、剰余類じょうよりるいの演算えんざんとして説明せつめいします。

用語ようごと定義ていぎ

a \equiv b [PARSE ERROR: Undefined("Command(\"pmod\")")] n

とは、 $n ∣ (a - b)$ であることです。

mod $n$ 演算えんざんとは、整数せいすうを $n$ で割わった余あまりだけを見みて計算けいさんする見方みかたです。

方針ほうしん

まず合同式ごうどうしきの定義ていぎを余あまりと結むすびつけます。そのあと、足たし算ざんや掛かけ算ざんが合同式ごうどうしきと両立りょうりつすることを証明しょうめいし、最後さいごに $Z / n Z$ という見方みかたへつなげます。

data/lecture/math/abstract-algebra/同値関係と剰余類の基本-講義.n.md data/lecture/math/algebra/整数の性質の基本-講義.n.md

直感的ちょっかんてきな説明せつめい

5 時間じかんごとに繰くり返かえす時計とけいを考かんがえると、7 時じと 2 時じは同おなじ位置いちにあります。これは $7 - 2 = 5$ が 5 の倍数ばいすうだからです。合同式ごうどうしきは、この「同おなじ位置いちに戻もどる」という感覚かんかくを整数せいすうの計算けいさんへ持もち込こんだものです。

厳密げんみつな説明せつめい

1. 余あまりと合同式ごうどうしき

a \equiv b [PARSE ERROR: Undefined("Command(\"pmod\")")] n

とは

n ∣ (a - b)

です。これは、 $a - b = n k$ となる整数せいすう $k$ があるということです。

もし $a = q n + r, b = p n + r$

と同おなじ余あまり $r$ を持もつなら、

a - b = (q - p) n

で、たしかに $a \equiv b [PARSE ERROR: Undefined("Command(\"pmod\")")] n$ です。逆ぎゃくに $a \equiv b [PARSE ERROR: Undefined("Command(\"pmod\")")] n$ なら、割わり算ざんの余あまりは一致いっちします。したがって合同式ごうどうしきは「余あまりが同おなじ」を厳密げんみつに書かいたものです。

2. なぜ足たし算ざんや掛かけ算ざんをしてよいか

a \equiv b [PARSE ERROR: Undefined("Command(\"pmod\")")] n, c \equiv d [PARSE ERROR: Undefined("Command(\"pmod\")")] n

とします。すると

a - b = n k, c - d = n ℓ

です。

このとき

(a + c) - (b + d) = (a - b) + (c - d) = n (k + ℓ)

なので

a + c \equiv b + d [PARSE ERROR: Undefined("Command(\"pmod\")")] n

です。

また

a c - b d = a (c - d) + d (a - b)

と変形へんけいすると、

a c - b d = a n ℓ + d n k = n (a ℓ + d k)

だから

a c \equiv b d [PARSE ERROR: Undefined("Command(\"pmod\")")] n

です。

これで合同式ごうどうしきの両辺りょうへんに同おなじ演算えんざんをしてよい理由りゆうが分わかります。

3. mod 演算えんざんの本当ほんとうの意味いみ

data/lecture/math/abstract-algebra/同値関係と剰余類の基本-講義.n.md

剰余類じょうよりるい $[a]$ の足たし算ざんと掛かけ算ざんを

[a] + [b] = [a + b], [a] [b] = [a b]

と定さだめたいのですが、ここで代表元だいひょうげんの選えらび方かたに依存いぞんしてはいけません。

しかしさきほど証明しょうめいしたように、 $a \equiv a^{'}$ と $b \equiv b^{'}$ なら

a + b \equiv a^{'} + b^{'}, a b \equiv a^{'} b^{'}

です。したがってこの演算えんざんは代表元だいひょうげんの選えらび方かたによらず、ちゃんと定義ていぎできます。これが mod 演算えんざんの正当化せいとうかです。

4. 逆元ぎゃくげんと割わり算ざん

mod $n$ では、何なんでも割われるわけではありません。 $a$ に逆元ぎゃくげんがある、つまり

a x \equiv 1 [PARSE ERROR: Undefined("Command(\"pmod\")")] n

となる $x$ があるのは、 $a$ と $n$ が互たがいに素そのときです。だから mod 演算えんざんでは、割わり算ざんは普通ふつうの整数せいすうほど自由じゆうではありません。

この見方みかたをさらに進すすめると、mod 演算えんざんは群ぐん、環かん、体たいという構造こうぞうとして読よみ直なおせます。

data/lecture/math/abstract-algebra/群の基本-講義.n.md data/lecture/math/abstract-algebra/環の基本-講義.n.md data/lecture/math/abstract-algebra/体の基本-講義.n.md

別べつの見方みかた

高校数学こうこうすうがくの見方みかた

余あまりの計算けいさんを楽らくにする道具どうぐとして見みる見方みかたです。

大学数学だいがくすうがくの見方みかた

剰余類じょうよりるいの上うえで演算えんざんを定義ていぎした構造こうぞうとして見みる見方みかたです。こちらでは「なぜその計算けいさんが許ゆるされるか」が見みえます。

見分みわけ方かた

余あまりだけが重要じゅうような整数問題せいすうもんだいなら、合同式ごうどうしきへ移うつると整理せいりしやすくなります。
割わり算ざんが出でるときは、その数かずが mod $n$ で逆元ぎゃくげんを持もつかを先さきに確認かくにんします。

どこまで成なり立たつか

ここでの議論ぎろんは、整数せいすうとその剰余類じょうよりるいの上うえでの演算えんざんを扱あつかっています。mod 演算えんざんの感覚かんかくは多項式たこうしきや行列ぎょうれつにも広ひろがりますが、そのときは何なにを同おなじとみなすかを改あらためて確認かくにんする必要ひつようがあります。

最終形さいしゅうけい

[PARSE ERROR: Undefined("Command(\"boxed\")")] a \equiv b [PARSE ERROR: Undefined("Command(\"pmod\")")] n ⟺ n ∣ (a - b)

[PARSE ERROR: Undefined("Command(\"boxed\")")] [a] + [b] = [a + b], [a] [b] = [a b]

一言ひとことでいうと

mod 演算えんざんが正ただしいのは、余あまりで計算けいさんしているからではなく、剰余類じょうよりるいの演算えんざんがちゃんと定義ていぎできるからです。