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

合同式ごうどうしきModular congruence

を合同式ごうどうしきModular congruenceという。

「合同ごうどう」の命名めいめい：幾何学きかがくの「合同ごうどう」（形かたちが一致いっち）から類比るいひ。n を法ほう（modulus）としてみると位置いちが同おなじ、という感覚かんかく。英語えいご congruence（一致いっち・合同ごうどう）はガウスが著書ちょしょ「数論すうろん探究たんきゅう」（1801 年ねん）で導入どうにゅう。

剰余類じょうよるいResidue class

$[a{]}_n=\{a+kn\mid k\in \mathbb{Z}\}$[a]_n = \{a + kn \mid k \in \mathbb{Z}\}（$a$a と同おなじ余あまりを持もつ整数せいすうの集合しゅうごう）を $a$a の剰余類じょうよるいResidue classという。$\mathbb{Z}/n\mathbb{Z}=\left\{\right[0],[1],\dots ,[n-1\left]\right\}$\mathbb{Z}/n\mathbb{Z} = \{[0], [1], \ldots, [n-1]\} は $n$n 個この剰余類じょうよるいからなる。

1. 余あまりと合同式ごうどうしきの等価性とうかせい

$a=q_{1}n+r$a = q_1 n + r, $b=q_{2}n+r$b = q_2 n + r（同おなじ余あまり $r$r）のとき $a-b=(q_1-q_2)n$a - b = (q_1 - q_2)n なので $n\mid (a-b)$n \mid (a-b)。逆ぎゃくに $n\mid (a-b)$n \mid (a-b) なら $a$a と $b$b の除じょの余あまりは一致いっちする。

2. 演算えんざんの整合性せいごうせい（最重要さいじゅうよう証明しょうめい）

$a\equiv a^{\prime }\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$a \equiv a' \pmod{n}, $b\equiv b^{\prime }\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$b \equiv b' \pmod{n} のとき：

和わ：$(a+b)-(a^{\prime }+b^{\prime })=(a-a^{\prime })+(b-b^{\prime })$(a+b) - (a'+b') = (a-a') + (b-b') はともに $n$n の倍数ばいすうの和わなので $n$n の倍数ばいすう。

積せき：$ab-a^{\prime }{b}^{\prime }=a(b-b^{\prime })+b^{\prime }(a-a^{\prime })$ab - a'b' = a(b-b') + b'(a-a') はともに $n$n の倍数ばいすうを含ふくむので $n$n の倍数ばいすう。

したがって代表元だいひょうげんを変かえても演算えんざん結果けっかの剰余類じょうよるいは変かわらない—これが「mod 演算えんざんが定義ていぎできる」ことの証明しょうめいである。

3. $\mathbb{Z}/n\mathbb{Z}$\mathbb{Z}/n\mathbb{Z} の構造こうぞう

4. 逆元ぎゃくげんの条件じょうけん

ユークリッド互除法ごじょほうで $\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,n)=1$\gcd(a,n)=1 のとき $ax+ny=1$ax + ny = 1 の整数解せいすうかい $(x_0,y_0)$(x_0, y_0) が得えられ、$x\equiv x_0\text{[PARSE ERROR: Undefined("Command("pmod")")]}n$x \equiv x_0 \pmod{n} が逆元ぎゃくげんである。

例れい：$3x\equiv 1\text{[PARSE ERROR: Undefined("Command("pmod")")]}7$3x \equiv 1 \pmod{7}。$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(3,7)=1$\gcd(3,7)=1 なので存在そんざい。$3\times 5=15=2\times 7+1$3 \times 5 = 15 = 2\times 7 + 1 より $x\equiv 5\text{[PARSE ERROR: Undefined("Command("pmod")")]}7$x \equiv 5 \pmod{7}。

5. フェルマーの小定理しょうていり

$p$p が素数そすうで $\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,p)=1$\gcd(a, p) = 1 のとき：

証明しょうめいの概略がいりゃく：$\{a,2a,3a,\dots ,(p-1\left)a\right\}\text{[PARSE ERROR: Undefined("Command("pmod")")]}p$\{a, 2a, 3a, \ldots, (p-1)a\} \pmod{p} は $\{1,2,\dots ,p-1\}$\{1, 2, \ldots, p-1\} の順列じゅんれつである（$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a,p)=1$\gcd(a,p)=1 のため零ぜろが現あらわれない・重複ちょうふくしない）。両辺りょうへんの積せきを比較ひかくすると

$(p-1)!$(p-1)! と $p$p は互たがいに素そなので両辺りょうへんを割わって $a^{p-1}\equiv 1$a^{p-1} \equiv 1。

応用おうよう：$2^{100}\text{[PARSE ERROR: Undefined("Command("pmod")")]}7$2^{100} \pmod{7} の計算けいさん。$p=7$p=7 なので $2^6\equiv 1\text{[PARSE ERROR: Undefined("Command("pmod")")]}7$2^6 \equiv 1 \pmod 7。$100=6\times 16+4$100 = 6 \times 16 + 4 より $2^{100}=(2^6{)}^{16}·2^4\equiv 1^{16}·16\equiv 2\text{[PARSE ERROR: Undefined("Command("pmod")")]}7$2^{100} = (2^6)^{16} \cdot 2^4 \equiv 1^{16} \cdot 16 \equiv 2 \pmod 7。

6. 冪乗べきじょうの高速こうそく計算けいさん（反復二乗法はんぷくにじょうほう）

$a^n\text{[PARSE ERROR: Undefined("Command("bmod")")]}m$a^n \bmod m の計算けいさん：

1. $n$n を 2 進数しんすう展開てんかい: $n=\sum _k{b}_k{2}^k$n = \sum_{k} b_k 2^k
2. $a^1,a^2,a^4,a^8,\dots$a^1, a^2, a^4, a^8, \ldots を順次じゅんじ mod $m$m で計算けいさん
3. $b_k=1$b_k = 1 の成分せいぶんを掛かけ合あわせる

フェルマーの小定理しょうていりで指数しすうを $p-1$p-1 で削減さくげんしてから反復二乗法はんぷくにじょうほうを使つかうと、RSA暗号あんごうの基礎きそ演算えんざんに到達とうたつする。

7. 連立合同式れんりつごうどうしき

法ほうが互たがいに素そな連立れんりつ合同ごうどう条件じょうけんは中国ちゅうごく剰余定理じょうよていり（CRT）で一意いちいに解とける。