# 合同式とフェルマーの小定理：余りだけの世界で計算する > 整数の合同式を同値関係として定義し、剰余環 Z/nZ とその単元群の構造を調べ、フェルマーの小定理とオイラーの定理を証明する。中国剰余定理を経由して RSA 暗号の正当性まで到達する。 > https://rikai.mugen-giken.com/mathematics/number-theory/congruences-and-fermat ## 0. この記事の要点 - 整数を「$n$ で割った余り」で分類すると、加法・減法・乗法がそのまま持ち込める。これが合同式 $a \equiv b \pmod n$ であり、商集合 $\mathbb{Z}/n\mathbb{Z}$ は可換環になる。 - 割り算は無条件にはできない。$[a]$ が $\mathbb{Z}/n\mathbb{Z}$ で逆元をもつのは $\gcd(a,n)=1$ のときに限る。この事実の根拠はベズーの等式ただ一つです。 - $n$ が素数 $p$ のとき $\mathbb{Z}/p\mathbb{Z}$ は体になり、$0$ でない元すべてが可逆になる。ここからフェルマーの小定理 $a^{p-1} \equiv 1 \pmod p$（$p \nmid a$ のとき）が出る。 - 一般の $n$ に対する拡張がオイラーの定理 $a^{\varphi(n)} \equiv 1 \pmod n$ で、証明の骨格はフェルマーの小定理と同じ「$a$ 倍写像が単元群の置換である」という一点です。 - 中国剰余定理は $\mathbb{Z}/mn\mathbb{Z} \cong \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$（$\gcd(m,n)=1$）という同型で、$\varphi$ の乗法性と RSA 暗号の正当性の両方を支えている。 - フェルマーの小定理の逆は成り立たない。$561$ のようなカーマイケル数が反例になり、これが素数判定を確率的アルゴリズムへと押しやった。 ## 1. 動機 — 時計の算術から いま $7$ 時だとして、$8$ 時間後は何時でしょうか。$7+8=15$ ですが、時計の文字盤には $15$ がないので $3$ 時と答えます。私たちは日常的に「$12$ で割った余り」の世界で足し算をしているわけです。
0 1 2 3 4 5 6 7 8 9 10 11 7 + 8 = 3 (mod 12)
この「余りだけを見る」計算法は古くから断片的に使われていました。各位の数字の和で $9$ の倍数を判定する九去法は中世の商人の検算術ですし、暦の計算も本質的に剰余の計算です。しかしこれを $\equiv$ という記号で体系化し、独立した代数系として扱ったのはガウス『整数論研究』（1801）です。ガウスはこの記号ひとつで、それまで散らばっていた整数論の技法を統一しました。 なぜ記号を導入するだけで進歩が起きるのでしょうか。理由は、合同式が等号とほとんど同じ規則で扱えるからです。「両辺に同じものを足してよい」「両辺に同じものを掛けてよい」が成り立つので、方程式を変形する感覚をそのまま持ち込めます。すると例えば $2^{100}$ の下 $2$ 桁のような、まともに計算すれば $31$ 桁の数を扱う問題が、$100$ 未満の数の掛け算数回に化けます。 一方で等号と決定的に違う点もあります。割り算が自由にできません。$2 \times 3 \equiv 2 \times 9 \pmod{12}$ ですが $3 \not\equiv 9 \pmod{12}$ です。この「割れる／割れない」の境目を正確に決めることが、この記事の技術的な核心であり、そこからフェルマーの小定理も RSA 暗号も流れ出します。 この記事は [素数の魅力 - 素数定理](/mathematics/number-theory/primes-and-prime-number-theorem) の続きにあたります。素数を「どれだけあるか」ではなく「どう振る舞うか」の側から見る回だと思ってください。 ## 2. 準備 — 除法の原理とベズーの等式 以下、$\mathbb{Z}$ は整数全体、$\mathbb{N} = \{1,2,3,\ldots\}$（$0$ を含めない）とします。$a \mid b$ は「$a$ が $b$ を割り切る」、すなわち $b = ac$ となる $c \in \mathbb{Z}$ が存在することを意味します。 $a \in \mathbb{Z}$、$n \in \mathbb{N}$ とする。このとき $$ a = qn + r, \qquad 0 \le r < n $$ を満たす整数 $q, r$ がただ一組存在する。 存在を示します。集合 $S = \{a - qn \mid q \in \mathbb{Z}\} \cap \mathbb{Z}_{\ge 0}$ を考えます。$q$ として十分小さい負の整数（例えば $q = -|a|$）を取ると $a - qn = a + |a|n \ge a + |a| \ge 0$ なので $S \ne \varnothing$ です。$S$ は非負整数の空でない部分集合なので、 により最小元 $r = a - qn$ をもちます。 もし $r \ge n$ なら $r - n = a - (q+1)n$ もまた非負で $S$ に属し、$r - n < r$ となって $r$ の最小性に反します。よって $0 \le r < n$ です。 一意性を示します。$a = qn + r = q'n + r'$（$0 \le r, r' < n$）とすると $(q - q')n = r' - r$ です。右辺は $|r' - r| < n$ を満たすので、$|q - q'| \cdot n < n$、したがって $|q - q'| < 1$、すなわち $q = q'$ です。これを戻すと $r = r'$ を得ます。 この $r$ を $a \bmod n$ と書きます。$\bmod$ を「余りを取る演算」として使うときはこの意味です（後で出る $\pmod n$ は関係を表す注記で、役割が違います）。 $a, b$ が同時に $0$ でないとき、$a$ と $b$ の公約数のうち最大のものを $\gcd(a,b)$ と書きます。$\gcd(a,b)=1$ のとき $a$ と $b$ は互いに素であるといいます（ と同じ記法です）。 $a, b$ を同時には $0$ でない整数とする。このとき $$ ax + by = \gcd(a,b) $$ を満たす整数 $x, y$ が存在する。さらに、$\{ax+by \mid x,y \in \mathbb{Z}\}$ は $\gcd(a,b)$ の倍数全体と一致する。 $I = \{ax + by \mid x, y \in \mathbb{Z}\}$ とおき、$I$ に含まれる正の整数全体を $I^{+}$ とします。$a \ne 0$ なら $a \cdot a + b \cdot 0 = a^2 > 0$ が $I^{+}$ に属し、$a = 0$ なら $b \ne 0$ より $b^2 \in I^{+}$ です。いずれにせよ $I^{+} \ne \varnothing$ なので、整列性により最小元 $d = ax_0 + by_0 > 0$ が取れます。 まず $d \mid a$ を示します。 により $a = qd + r$（$0 \le r < d$）と書くと $$ r = a - qd = a - q(ax_0 + by_0) = a(1 - qx_0) + b(-qy_0) \in I . $$ もし $r > 0$ なら $r \in I^{+}$ かつ $r < d$ となり $d$ の最小性に反します。よって $r = 0$、すなわち $d \mid a$ です。同じ議論で $d \mid b$ も出るので、$d$ は $a, b$ の公約数です。 逆に $c$ を $a, b$ の任意の公約数とすると、$d = ax_0 + by_0$ の右辺の各項が $c$ で割り切れるので $c \mid d$、したがって $c \le d$ です。ゆえに $d = \gcd(a,b)$ であり、$d = ax_0 + by_0$ が求める表示です。 最後の主張は、$I$ の任意の元 $ax+by$ が $d \mid a$, $d \mid b$ より $d$ の倍数であること、逆に $d$ の倍数 $kd = a(kx_0) + b(ky_0)$ が $I$ に属することから従います。 $\gcd(c,n) = 1$ かつ $n \mid cm$ ならば $n \mid m$ である。特に $p$ が素数で $p \mid ab$ ならば $p \mid a$ または $p \mid b$ である。 により $cx + ny = 1$ となる整数 $x, y$ が取れます。両辺に $m$ を掛けると $$ m = (cm)x + n(my) $$ です。仮定より $n \mid cm$ なので右辺の第 $1$ 項は $n$ で割り切れ、第 $2$ 項も明らかに $n$ の倍数です。よって $n \mid m$ となります。 後半は、$p \nmid a$ のとき $p$ が素数であることから $\gcd(p,a)$ は $1$ か $p$ のいずれかで、$p$ ではないので $1$ であり、前半を $c = a$, $n = p$, $m = b$ として適用すれば $p \mid b$ が出ます。 ## 3. 合同式 $n \in \mathbb{N}$ とする。整数 $a, b$ に対し $n \mid (a - b)$ が成り立つとき、$a$ と $b$ は $n$ を法として合同であるといい $$ a \equiv b \pmod n $$ と書く。$n$ をこの合同式の法という。 $n$ を法とする合同は $\mathbb{Z}$ 上の同値関係であり、その同値類はちょうど $n$ 個、すなわち $0, 1, \ldots, n-1$ の各々と合同な整数の集まりである。 反射律は $n \mid 0 = a - a$ より成り立ちます。対称律は $n \mid (a-b)$ ならば $b - a = -(a-b)$ も $n$ の倍数であることから従います。推移律は、$a - b = nk$、$b - c = nl$ とすると $a - c = n(k+l)$ となることから従います。 同値類の個数を数えます。 により任意の $a$ は $a = qn + r$（$0 \le r < n$）と書けるので $a - r = qn$、すなわち $a \equiv r \pmod n$ です。よって各同値類は $0,\ldots,n-1$ のいずれかを含みます。また $0 \le r < r' < n$ なら $0 < r' - r < n$ なので $n \nmid (r' - r)$ であり、$r$ と $r'$ は合同ではありません。ゆえに同値類はちょうど $n$ 個です。 同値関係一般については [関係と同値関係 - 「同じ」とは何か](/mathematics/foundations/equivalence-relations) を参照してください（上の命題の前半は にあたります）。$a$ を含む同値類を $[a]$ または $[a]_n$ と書き、$a$ の剰余類と呼びます。 $a \equiv b \pmod n$ かつ $c \equiv d \pmod n$ とする。このとき $$ a + c \equiv b + d, \qquad a - c \equiv b - d, \qquad ac \equiv bd \pmod n $$ が成り立つ。特に任意の $k \in \mathbb{N}$ に対し $a^k \equiv b^k \pmod n$ である。 仮定より $a - b = ns$、$c - d = nt$ となる整数 $s,t$ が取れます。加法については $$ (a+c) - (b+d) = (a-b) + (c-d) = n(s+t) $$ なので $n$ で割り切れます。減法も符号を変えるだけで同じです。乗法については $$ ac - bd = ac - bc + bc - bd = c(a-b) + b(c-d) = n(cs + bt) $$ と変形できるので $n \mid (ac - bd)$ です。ここで途中に $bc$ を足して引く操作を使いました。 べき乗は $k$ に関する数学的帰納法です。$k=1$ は仮定そのものです。$a^k \equiv b^k$ が成り立つとすると、これと $a \equiv b$ に乗法の主張を適用して $a^{k+1} \equiv b^{k+1}$ を得ます。 が、合同式を等式のように扱ってよい根拠です。これがあるおかげで、巨大なべき乗を余りだけで追跡できます。 $2^{100} \bmod 100$ を求めます。$2^{10} = 1024 \equiv 24 \pmod{100}$ です。 により両辺を $2$ 乗して $$ 2^{20} \equiv 24^2 = 576 \equiv 76 \pmod{100}. $$ さらに $76^2 = 5776 \equiv 76 \pmod{100}$ なので、$2^{40} \equiv 76$、$2^{80} \equiv 76$ です。したがって $$ 2^{100} = 2^{80} \cdot 2^{20} \equiv 76 \cdot 76 = 5776 \equiv 76 \pmod{100}. $$ $2^{100}$ は $31$ 桁の数ですが、$3$ 桁を超える掛け算を一度もせずに下 $2$ 桁が $76$ と分かりました。 $10 \equiv 1 \pmod 9$ なので より $10^k \equiv 1 \pmod 9$ です。よって $N = \sum_{k} d_k 10^k$（$d_k$ は各位の数字）に対し $$ N \equiv \sum_k d_k \pmod 9 $$ となります。これが「各位の数字の和で $9$ の倍数を判定できる」ことの証明です。例えば $N = 987654$ なら $9+8+7+6+5+4 = 39 \equiv 3+9 = 12 \equiv 3 \pmod 9$ なので $N \equiv 3 \pmod 9$ です。 一方 $10 \equiv -1 \pmod{11}$ なので $10^k \equiv (-1)^k$ となり、 $$ N \equiv \sum_k (-1)^k d_k \pmod{11} $$ です。$987654$ では下位から交互に符号を付けて $4 - 5 + 6 - 7 + 8 - 9 = -3 \equiv 8 \pmod{11}$ となります。 割り算だけは事情が違います。次の命題が、合同式で「両辺を割る」ときの正確な規則です。 $n \in \mathbb{N}$、$c \in \mathbb{Z}$、$d = \gcd(c,n)$ とする。このとき $$ ca \equiv cb \pmod n \iff a \equiv b \pmod{n/d} $$ が成り立つ。特に $\gcd(c,n)=1$ のときに限り、$ca \equiv cb \pmod n$ から $a \equiv b \pmod n$ が結論できる。 $c = dc'$、$n = dn'$ と書くと $\gcd(c', n') = 1$ です（もし $e > 1$ が両者の公約数なら $de$ が $c,n$ の公約数となり $d$ の最大性に反します）。 $(\Rightarrow)$ $ca \equiv cb \pmod n$ は $n \mid c(a-b)$、すなわち $dn' \mid dc'(a-b)$ を意味し、両辺を $d$ で割って $n' \mid c'(a-b)$ です。$\gcd(c',n')=1$ なので により $n' \mid (a-b)$、つまり $a \equiv b \pmod{n'}$ です。 $(\Leftarrow)$ $n' \mid (a-b)$ なら $n = dn' \mid dc'(a-b) = c(a-b)$ なので $ca \equiv cb \pmod n$ です。 $2 \cdot 3 = 6$、$2 \cdot 9 = 18$ で、$18 - 6 = 12$ なので $2 \cdot 3 \equiv 2 \cdot 9 \pmod{12}$ です。しかし $9 - 3 = 6$ は $12$ の倍数ではないので $3 \not\equiv 9 \pmod{12}$ です。 の通り $d = \gcd(2,12) = 2$ なので、正しく結論できるのは $3 \equiv 9 \pmod 6$ までです。実際 $9 - 3 = 6$ はこれを満たします。 ## 4. 剰余環 Z/nZ と単元群 $n \in \mathbb{N}$ とする。$n$ を法とする剰余類全体の集合を $$ \mathbb{Z}/n\mathbb{Z} = \{[0], [1], \ldots, [n-1]\} $$ と書き、演算を $$ [a] + [b] := [a+b], \qquad [a] \cdot [b] := [ab] $$ で定める。 この定義には確認すべきことがあります。$[a]$ という記号は同値類であって、代表元 $a$ の取り方には自由度があるからです。$[a] = [a']$、$[b] = [b']$ のとき $[a+b] = [a'+b']$ と $[ab] = [a'b']$ が成り立たなければ、演算は定義されたことになりません。これはまさに の主張です。したがって演算は代表元の取り方によらず定まります（商集合の言葉で同じことを述べたものが です）。 の演算により $\mathbb{Z}/n\mathbb{Z}$ は単位元 $[1]$ をもつ可換環になる。 結合律、交換律、分配律はすべて $\mathbb{Z}$ における対応する法則から直ちに従います。例えば分配律は $$ [a]([b]+[c]) = [a][b+c] = [a(b+c)] = [ab+ac] = [ab]+[ac] = [a][b]+[a][c] $$ であり、$3$ 番目の等号だけが $\mathbb{Z}$ の分配律、他は定義の書き換えです。加法の単位元は $[0]$、$[a]$ の加法逆元は $[-a]$、乗法の単位元は $[1]$ です。 環としての一般論は [環と体の基礎](/mathematics/algebra/rings-and-fields) に、$\mathbb{Z}/n\mathbb{Z}$ をイデアル $n\mathbb{Z}$ による商環と見る視点は [イデアルと剰余環](/mathematics/algebra/ideals-and-quotient-rings) の にあります。 環 $\mathbb{Z}/n\mathbb{Z}$ の元 $[a]$ が単元であるとは、$[a][b] = [1]$ となる $[b]$ が存在することをいう。単元全体の集合を $(\mathbb{Z}/n\mathbb{Z})^{\times}$ と書く。 $[a] \in \mathbb{Z}/n\mathbb{Z}$ が単元であるための必要十分条件は $\gcd(a,n) = 1$ である。また $(\mathbb{Z}/n\mathbb{Z})^{\times}$ は乗法について群をなす。 $(\Leftarrow)$ $\gcd(a,n)=1$ とすると により $ax + ny = 1$ となる整数 $x,y$ が取れます。これは $ax - 1 = -ny$、すなわち $ax \equiv 1 \pmod n$ を意味するので $[a][x] = [1]$ です。 $(\Rightarrow)$ $[a][b] = [1]$ とすると $ab - 1 = nk$ となる整数 $k$ があり、$ab - nk = 1$ です。$d = \gcd(a,n)$ は左辺の両方の項を割り切るので $d \mid 1$、よって $d = 1$ です。 群であることを確かめます。$[1]$ は単元です。単元 $[a],[b]$ の積 $[ab]$ は、$[a][x]=[1]$、$[b][y]=[1]$ とすると $[ab][xy] = [a][x][b][y] = [1]$ なので単元であり、演算は閉じています。結合律は環の乗法から、逆元の存在は単元の定義から従います。 $\mathbb{Z}/n\mathbb{Z}$ が体であるための必要十分条件は $n$ が素数であることである。 $n = p$ を素数とします。$[a] \ne [0]$ とは $p \nmid a$ ということで、$p$ が素数だから $\gcd(a,p) \in \{1,p\}$ のうち $p$ は除かれ $\gcd(a,p)=1$ です。 より $[a]$ は単元なので、$\mathbb{Z}/p\mathbb{Z}$ は体です（$p \ge 2$ より $[1] \ne [0]$ も満たされます）。 逆に $n$ が合成数なら $n = ab$（$1 < a, b < n$）と書け、$[a] \ne [0]$、$[b] \ne [0]$ でありながら $[a][b] = [n] = [0]$ です。体には零因子がない（$[a][b]=[0]$ かつ $[a]$ が可逆なら両辺に $[a]^{-1}$ を掛けて $[b]=[0]$）ので、これは体ではありません。$n = 1$ のときは $[1]=[0]$ なので体の定義を満たしません。 素数 $p$ に対する体 $\mathbb{Z}/p\mathbb{Z}$ を $\mathbb{F}_p$ と書きます。 は、素数が「割り算のできる有限世界」を作る唯一の法であることを言っています。素数の特別さがここで代数的な形をとります。同じ主張は環論の側からも として得られます。 $n \in \mathbb{N}$ に対し $$ \varphi(n) := \#\{a \in \mathbb{Z} \mid 1 \le a \le n,\ \gcd(a,n)=1\} $$ と定める。 により $\varphi(n) = \#(\mathbb{Z}/n\mathbb{Z})^{\times}$ である。 $1$ から $12$ までで $12$ と互いに素なものは $1, 5, 7, 11$ の $4$ 個なので $\varphi(12)=4$、$(\mathbb{Z}/12\mathbb{Z})^{\times} = \{[1],[5],[7],[11]\}$ です。乗法表を作ると $$ [5]^2 = [25] = [1], \quad [7]^2 = [49] = [1], \quad [11]^2 = [121] = [1], \quad [5][7] = [35] = [11] $$ となり、単位元以外のすべての元が位数 $2$ です。したがってこの群はクラインの四元群 $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$ と同型で、巡回群ではありません。一方 $p$ が素数のとき $(\mathbb{Z}/p\mathbb{Z})^{\times}$ は必ず巡回群になることが知られています（原始根の存在）。 $m, n \in \mathbb{N}$ が $\gcd(m,n)=1$ を満たすとする。このとき写像 $$ \Phi : \mathbb{Z}/mn\mathbb{Z} \longrightarrow \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}, \qquad [a]_{mn} \longmapsto ([a]_m, [a]_n) $$ は well-defined な環同型である。特に任意の整数 $r, s$ に対し連立合同式 $x \equiv r \pmod m$, $x \equiv s \pmod n$ は $mn$ を法として一意な解をもつ。 well-defined 性: $[a]_{mn} = [a']_{mn}$ なら $mn \mid (a-a')$ なので特に $m \mid (a-a')$、$n \mid (a-a')$ であり、$([a]_m,[a]_n) = ([a']_m,[a']_n)$ です。環準同型であることは、両成分での加法と乗法がともに の演算に一致することから直ちに従います。$\Phi([1]_{mn}) = ([1]_m,[1]_n)$ も明らかです。 単射性: $\Phi([a]_{mn}) = ([0]_m,[0]_n)$ とすると $m \mid a$ かつ $n \mid a$ です。$a = mk$ と書くと $n \mid mk$ で、$\gcd(n,m)=1$ なので により $n \mid k$、すなわち $k = nl$ です。よって $a = mnl$、つまり $[a]_{mn} = [0]_{mn}$ です。準同型の核が $0$ だけなので $\Phi$ は単射です。 全射性: 定義域と値域はともに有限集合で、要素数はそれぞれ $mn$ と $m \cdot n$ で等しくなります。単射な写像が有限の等濃度集合の間にあれば全射なので、$\Phi$ は全単射です。 最後の主張は $\Phi$ の全単射性そのものです。$([r]_m,[s]_n)$ の逆像がちょうど一つの剰余類 $[x]_{mn}$ であることが、解の存在と $mn$ を法とする一意性を意味します。 $\gcd(m,n)=1$ ならば $\varphi(mn) = \varphi(m)\varphi(n)$ である。さらに $n = p_1^{e_1}\cdots p_k^{e_k}$ を素因数分解とすると $$ \varphi(n) = n \prod_{i=1}^{k}\left(1 - \frac{1}{p_i}\right). $$ 環同型は単元を単元に、非単元を非単元に写します（$\Phi(u)\Phi(u^{-1}) = \Phi(1) = 1$、逆向きも $\Phi^{-1}$ について同様）。したがって の $\Phi$ は単元群の間の全単射 $$ (\mathbb{Z}/mn\mathbb{Z})^{\times} \xrightarrow{\ \sim\ } (\mathbb{Z}/m\mathbb{Z})^{\times} \times (\mathbb{Z}/n\mathbb{Z})^{\times} $$ を誘導します。両辺の要素数を数えれば $\varphi(mn)=\varphi(m)\varphi(n)$ です。 素数べき $p^e$ については、$1$ から $p^e$ までの整数のうち $p^e$ と互いに素でないものは $p$ の倍数、すなわち $p, 2p, \ldots, p^{e-1}\cdot p$ の $p^{e-1}$ 個です。よって $$ \varphi(p^e) = p^e - p^{e-1} = p^e\left(1 - \frac{1}{p}\right). $$ 異なる素数べきは互いに素なので乗法性を繰り返し使えば公式を得ます。 ## 5. フェルマーの小定理とオイラーの定理 フェルマーは 1640 年、フレニクル宛の書簡でこの定理を述べましたが「証明は長くなるので書かない」として省略しました。最初に公表された証明はオイラーによるもの（1736）です。 $p$ を素数、$a$ を $p \nmid a$ である整数とする。このとき $$ a^{p-1} \equiv 1 \pmod p . $$ $S = \{1, 2, \ldots, p-1\}$ とし、写像 $\sigma$ を「$x \in S$ に $ax \bmod p$ を対応させる」ものとして定めます。三段階で示します。 第一段階（$\sigma$ の値が $S$ に入ること）。$1 \le x \le p-1$ と $p \nmid a$ から、 の後半により $p \nmid ax$ です。よって $ax \bmod p \ne 0$、すなわち $\sigma(x) \in S$ です。 第二段階（$\sigma$ が単射であること）。$\sigma(x) = \sigma(y)$ とすると $ax \equiv ay \pmod p$ です。$p \nmid a$ より $\gcd(a,p)=1$ なので、 を $c=a$, $n=p$, $d=1$ として適用すると $x \equiv y \pmod p$ を得ます。$x,y$ はともに $1$ 以上 $p-1$ 以下なので $|x-y| < p$ であり、$x = y$ です。有限集合 $S$ から自身への単射は全単射なので、$\sigma$ は $S$ の置換です。 第三段階（積の比較）。$\sigma$ が置換であることから $$ \prod_{x \in S} \sigma(x) = \prod_{x \in S} x = (p-1)! . $$ 一方、各 $x$ について $\sigma(x) \equiv ax \pmod p$ なので、 を $p-1$ 回使って $$ \prod_{x \in S}\sigma(x) \equiv \prod_{x\in S} (ax) = a^{p-1}(p-1)! \pmod p . $$ 両者を合わせると $a^{p-1}(p-1)! \equiv (p-1)! \pmod p$ です。$1 \le x \le p-1$ の各 $x$ は $p$ で割り切れないので、 を繰り返して $p \nmid (p-1)!$、すなわち $\gcd((p-1)!,p)=1$ です。よって により $(p-1)!$ を消去でき、$a^{p-1} \equiv 1 \pmod p$ を得ます。 $p$ を素数とすると、すべての整数 $a$ に対して $a^{p} \equiv a \pmod p$ が成り立つ。 $p \nmid a$ のときは の両辺に $a$ を掛ければ $a^p \equiv a \pmod p$ です。$p \mid a$ のときは $a \equiv 0 \pmod p$ なので により $a^p \equiv 0^p = 0 \equiv a \pmod p$ です。どちらの場合も成り立ちます。 の形は $a$ に条件が付かないので使い勝手がよく、後で RSA の正当性を示すときに効きます。 $n \in \mathbb{N}$、$a \in \mathbb{Z}$ が $\gcd(a,n)=1$ を満たすとする。このとき $$ a^{\varphi(n)} \equiv 1 \pmod n . $$ の証明をそのまま持ち上げます。$U = (\mathbb{Z}/n\mathbb{Z})^{\times}$ とおき、$\#U = \varphi(n)$ です（）。$\gcd(a,n)=1$ なので より $[a] \in U$ です。 写像 $\mu_{[a]} : U \to U$, $[x] \mapsto [a][x]$ を考えます。$U$ が群であること（）から $[a][x] \in U$ であり、$\mu_{[a]}$ は $U$ から $U$ への写像です。また $\mu_{[a]^{-1}}$ が逆写像を与えるので $\mu_{[a]}$ は全単射、すなわち $U$ の置換です。 そこで $U$ の全元の積 $P = \prod_{[x]\in U}[x]$ を二通りに計算します。置換で並べ替えても積は変わらないので $$ P = \prod_{[x]\in U} \mu_{[a]}([x]) = \prod_{[x]\in U} [a][x] = [a]^{\varphi(n)} P . $$ $P$ は単元の積なので単元であり（ の群の性質）、両辺に $P^{-1}$ を掛けて $[a]^{\varphi(n)} = [1]$、すなわち $a^{\varphi(n)} \equiv 1 \pmod n$ です。 は群論の言葉では一行です。有限群 $G$ の元 $g$ に対し $g^{\#G} = e$ が成り立つ、というラグランジュの定理の系を $G = (\mathbb{Z}/n\mathbb{Z})^{\times}$ に適用しただけだからです。詳しくは [部分群と剰余類（ラグランジュの定理）](/mathematics/algebra/subgroups-and-lagrange) の を参照してください。上の証明は、その特別な場合を群論の言葉なしで書き下したものにあたります。歴史的にはこちらが先で、群という概念はこうした具体例の集積から抽出されました（[群論入門 - 群の定義と例](/mathematics/algebra/groups)）。 $p$ を素数、$p \nmid a$ とすると、$\mathbb{Z}/p\mathbb{Z}$ における $[a]$ の逆元は $[a^{p-2}]$ で与えられる。 $p \ge 2$ より $p - 2 \ge 0$ なので $a^{p-2}$ は整数です。 により $$ [a] \cdot [a^{p-2}] = [a^{p-1}] = [1] $$ です。逆元は一意なので（群の一般論、あるいは $[b],[b']$ がともに逆元なら $[b] = [b][a][b'] = [b']$）、これが $[a]^{-1}$ です。 $7$ は素数で $7 \nmid 3$ なので、 により $3^6 \equiv 1 \pmod 7$ です。$1000 = 6 \cdot 166 + 4$ なので $$ 3^{1000} = (3^{6})^{166} \cdot 3^{4} \equiv 1^{166}\cdot 3^4 = 81 \pmod 7 . $$ $81 = 7\cdot 11 + 4$ なので $3^{1000} \equiv 4 \pmod 7$ です。指数を $\varphi(7)=6$ で割った余りに置き換えられる、というのが小定理の実用的な使い方です。 ## 6. 応用 — 高速べき乗、RSA、素数判定 ### 6.1. 繰り返し二乗法 $a^e \bmod n$ を計算するのに $e$ 回の掛け算は要りません。$e$ を $2$ 進展開し、$a, a^2, a^4, \ldots$ を順に二乗しながら必要なものだけ掛ければ、掛け算は $O(\log e)$ 回で済みます。各段で $\bmod\ n$ を取るので、途中の数が $n^2$ を超えることもありません（根拠は ）。 ```python def power_mod(a, e, n): """a^e mod n を繰り返し二乗法で計算する。e >= 0, n >= 1。""" result = 1 a %= n while e > 0: if e & 1: result = result * a % n a = a * a % n e >>= 1 return result assert power_mod(2, 100, 100) == 76 # 2^100 の下 2 桁 assert power_mod(3, 1000, 7) == 4 # 3^1000 を 7 で割った余り ``` 逆元の計算には の証明を手続きに直した拡張ユークリッドの互除法を使います。 ```python def ext_gcd(a, b): """(g, x, y) を返す。g = gcd(a, b) かつ a*x + b*y = g。""" if b == 0: return (a, 1, 0) g, x, y = ext_gcd(b, a % b) return (g, y, x - (a // b) * y) def inverse_mod(a, n): g, x, _ = ext_gcd(a % n, n) if g != 1: raise ValueError("逆元が存在しません") return x % n assert inverse_mod(7, 120) == 103 ``` ### 6.2. RSA 暗号 $p \ne q$ を素数とし、$n = pq$、$\varphi(n) = (p-1)(q-1)$ とする。整数 $e, d$ が $$ ed \equiv 1 \pmod{\varphi(n)}, \qquad \gcd(e,\varphi(n)) = 1 $$ を満たすとする。このとき**すべての**整数 $m$ に対して $$ (m^{e})^{d} \equiv m \pmod n $$ が成り立つ。 仮定より $ed = 1 + k\varphi(n) = 1 + k(p-1)(q-1)$ となる整数 $k \ge 0$ が取れます（$ed \ge 1$ としてよい）。 まず $m^{ed} \equiv m \pmod p$ を示します。$p \mid m$ の場合は両辺とも $0$ と合同なので成り立ちます。$p \nmid m$ の場合、 により $m^{p-1}\equiv 1 \pmod p$ なので $$ m^{ed} = m \cdot \left(m^{p-1}\right)^{k(q-1)} \equiv m \cdot 1^{k(q-1)} = m \pmod p . $$ ここで のべき乗と乗法の性質を使いました。$p$ と $q$ を入れ替えれば同じ議論で $m^{ed}\equiv m \pmod q$ も出ます。 したがって $p \mid (m^{ed}-m)$ かつ $q \mid (m^{ed}-m)$ です。$p \ne q$ はともに素数なので $\gcd(p,q)=1$ であり、 の単射性の議論（あるいは を直接）により $pq \mid (m^{ed}-m)$、すなわち $m^{ed}\equiv m \pmod n$ です。 $\gcd(m,n)=1$ を仮定していない点が重要です。 をそのまま使うとこの仮定が要りますが、素因数ごとに分けて の形を使えば仮定なしで済みます。
B["n = pq, phi = (p-1)(q-1)"] B --> C["e を選ぶ (gcd(e, phi) = 1)"] C --> D["d = e^-1 mod phi を拡張ユークリッドで求める"] D --> E["公開鍵 (n, e)"] D --> F["秘密鍵 (n, d)"] E --> G["暗号化 c = m^e mod n"] G --> H["復号 m = c^d mod n"] F --> H`} />
$p = 11$, $q = 13$ とすると $n = 143$、$\varphi(n) = 10 \cdot 12 = 120$ です。$e = 7$ は $\gcd(7,120)=1$ を満たします。$d$ は $7d \equiv 1 \pmod{120}$ の解で、$7 \cdot 103 = 721 = 6\cdot 120 + 1$ より $d = 103$ です。 平文 $m = 5$ を暗号化します。 $$ 5^2 = 25,\quad 5^4 \equiv 25^2 = 625 = 4\cdot 143 + 53 \equiv 53 \pmod{143}, $$ $$ c = 5^7 = 5^4\cdot 5^2 \cdot 5 \equiv 53 \cdot 25 \cdot 5 \pmod{143}. $$ $53\cdot 25 = 1325 = 9\cdot 143 + 38 \equiv 38$、$38 \cdot 5 = 190 = 143 + 47 \equiv 47$ なので $c = 47$ です。 復号します。$47^{103} \bmod 143$ を直接計算する代わりに を使い、法 $11$ と法 $13$ に分けます。 法 $11$: $47 = 4\cdot 11 + 3 \equiv 3$ であり、 より $3^{10}\equiv 1 \pmod{11}$、$103 = 10\cdot 10 + 3$ なので $47^{103} \equiv 3^{3} = 27 \equiv 5 \pmod{11}$。 法 $13$: $47 = 3\cdot 13 + 8 \equiv 8$、$8^{12}\equiv 1 \pmod{13}$、$103 = 12\cdot 8 + 7$ なので $47^{103}\equiv 8^{7} \pmod{13}$。ここで $8^2 = 64 = 4\cdot 13 + 12 \equiv -1$ なので $8^7 = (8^2)^3 \cdot 8 \equiv (-1)^3\cdot 8 = -8 \equiv 5 \pmod{13}$。 $x \equiv 5 \pmod{11}$ かつ $x \equiv 5 \pmod{13}$ を満たす $143$ を法とする唯一の解は $x = 5$ です。確かに平文 $m=5$ が復元されました。 ### 6.3. フェルマー素数判定とカーマイケル数 の対偶は素数判定に使えます。ある $a$ について $a^{n-1}\not\equiv 1 \pmod n$（かつ $\gcd(a,n)=1$）なら $n$ は素数ではありません。この判定は繰り返し二乗法で高速に実行できます。 問題は逆です。$a^{n-1}\equiv 1 \pmod n$ が成り立ったからといって $n$ が素数とは限りません。 合成数 $n$ が、$\gcd(a,n)=1$ を満たすすべての整数 $a$ に対して $a^{n-1}\equiv 1 \pmod n$ を満たすとき、$n$ をカーマイケル数という。 $561 = 3\cdot 11\cdot 17$ で合成数です。$560$ は $2, 10, 16$ のいずれでも割り切れます（$560 = 2\cdot 280 = 10\cdot 56 = 16\cdot 35$）。$\gcd(a,561)=1$ とすると $a$ は $3, 11, 17$ のいずれでも割り切れないので、 より $$ a^{2}\equiv 1 \pmod 3, \qquad a^{10}\equiv 1\pmod{11}, \qquad a^{16}\equiv 1 \pmod{17}. $$ $560$ がこれらの指数の倍数なので、$a^{560} = (a^{2})^{280} \equiv 1 \pmod 3$ などが成り立ち、三つの素数すべてを法として $a^{560}\equiv 1$ です。 を二回使えば $561 \mid (a^{560}-1)$、すなわち $a^{560}\equiv 1 \pmod{561}$ を得ます。 $561$ は最小のカーマイケル数です。1994 年に Alford, Granville, Pomerance がカーマイケル数は無限に存在することを証明しました。 したがってフェルマー判定は決定的な素数判定にはなりません。この欠陥を補うのがミラー・ラビン判定で、$n-1 = 2^{s}t$（$t$ は奇数）と書いて $a^{t}, a^{2t},\ldots$ の列を見ることで「$1$ の自明でない平方根」の出現を検出します。$\mathbb{Z}/p\mathbb{Z}$ が体（）なら $x^2 = 1$ の解は $\pm 1$ に限る、という事実が原理です。合成数がミラー・ラビン判定をすり抜ける確率は各底について $1/4$ 以下なので、底をいくつも取れば実用上は十分な確実性が得られます。 この記事で扱った $\mathbb{Z}/n\mathbb{Z}$ は、数論の対象を有限の代数系に写して調べる最初の一歩です。同じ発想を推し進めると、方程式の解の個数を各素数 $p$ ごとに $\mathbb{F}_p$ で数え、それを母関数にまとめる、という手続きに至ります。楕円曲線に対してこれを行ったものがハッセ・ヴェイユ $L$ 関数で、[楕円曲線とモジュラー形式](/mathematics/number-theory/elliptic-curves-and-modular-forms) と [フェルマーの最終定理](/mathematics/number-theory/fermats-last-theorem) の主題になります。名前は似ていますが、フェルマーの小定理と最終定理の間にはこれだけの距離があります。 ## 7. 演習 $7^{2026}$ の一の位の数字を求めてください。 一の位は $10$ を法とする剰余です。$\gcd(7,10)=1$ で $\varphi(10)=\varphi(2)\varphi(5)=1\cdot 4=4$（）なので、 により $7^{4}\equiv 1 \pmod{10}$ です。$2026 = 4\cdot 506 + 2$ なので $$ 7^{2026} = (7^{4})^{506}\cdot 7^{2} \equiv 1^{506}\cdot 49 \equiv 9 \pmod{10}. $$ よって一の位は $9$ です。 $p$ を素数とするとき $(p-1)! \equiv -1 \pmod p$（ウィルソンの定理）を証明してください。 $p = 2$ のときは $1! = 1 \equiv -1 \pmod 2$ で成り立つので、以下 $p$ は奇素数とします。 $\mathbb{Z}/p\mathbb{Z}$ は体なので（）、$[1],\ldots,[p-1]$ はすべて可逆です。まず自分自身が逆元になる元を決定します。$[x]^2=[1]$ は $p \mid (x-1)(x+1)$ と同値で、 により $p \mid (x-1)$ または $p \mid (x+1)$、すなわち $x \equiv 1$ または $x\equiv -1 \pmod p$ です。$p$ が奇素数なら $1 \not\equiv -1$ なので、自己逆元は $[1]$ と $[p-1]$ の二つちょうどです。 残りの $p-3$ 個の元は、$[x]$ と $[x]^{-1}$ の相異なる二元の組に分割されます（逆元の一意性より、この対応は矛盾なく組を作ります）。各組の積は $[1]$ なので $$ (p-1)! = \prod_{x=1}^{p-1}[x] = [1]\cdot [p-1]\cdot \prod_{\text{組}} [1] = [p-1] = [-1]. $$ よって $(p-1)!\equiv -1 \pmod p$ です。 $341 = 11\cdot 31$ について、$2^{340}\equiv 1 \pmod{341}$ を示してください（$341$ は底 $2$ に関するフェルマー擬素数です）。また $3^{340} \bmod 341$ を計算し、底 $3$ では合成数と判定されることを確かめてください。 底 $2$: $2^{10}=1024 = 93\cdot 11 + 1$ なので $2^{10}\equiv 1 \pmod{11}$ であり、$340 = 10\cdot 34$ より $2^{340}\equiv 1 \pmod{11}$ です。また $2^{5}=32 = 31+1 \equiv 1 \pmod{31}$ で $340 = 5\cdot 68$ なので $2^{340}\equiv 1 \pmod{31}$ です。$\gcd(11,31)=1$ なので により $341 \mid (2^{340}-1)$、すなわち $2^{340}\equiv 1\pmod{341}$ です。 底 $3$: 法 $11$ では $3^{5}=243 = 22\cdot 11 + 1 \equiv 1$ で $340 = 5\cdot 68$ より $3^{340}\equiv 1 \pmod{11}$ です。法 $31$ では、 より $3^{30}\equiv 1$ で $340 = 30\cdot 11 + 10$ なので $3^{340}\equiv 3^{10} \pmod{31}$ です。$3^{3}=27$、$3^{5}=243 = 7\cdot 31 + 26 \equiv -5$ なので $3^{10} \equiv (-5)^2 = 25 \pmod{31}$ です。 $3^{340}\equiv 25 \not\equiv 1 \pmod{31}$ なので $3^{340}\not\equiv 1 \pmod{341}$ であり、 の対偶から $341$ は合成数と判定されます。値を求めるには $x\equiv 1 \pmod{11}$, $x \equiv 25 \pmod{31}$ を解きます。$x = 25 + 31k$ とおくと $25 \equiv 3$, $31\equiv 9 \pmod{11}$ より $3 + 9k \equiv 1$、$9k \equiv -2 \equiv 9 \pmod{11}$、$\gcd(9,11)=1$ なので により $k \equiv 1 \pmod{11}$ です。$k=1$ として $x = 56$、すなわち $3^{340}\equiv 56 \pmod{341}$ です。 合成数 $n$ がカーマイケル数（）であるならば、$n$ は平方因子をもたず、かつ $n$ のすべての素因数 $p$ について $(p-1)\mid (n-1)$ であることを示してください（コルセルトの判定条件の必要性）。 $n$ をカーマイケル数とします。 平方因子がないこと。$p^{2}\mid n$ となる素数 $p$ があったと仮定します。$n$ の素因数分解から $n = p^{e}m$（$e \ge 2$、$p \nmid m$）と書けます。$\gcd(p^{2}, m)=1$ なので により $$ a \equiv 1 + p \pmod{p^{2}}, \qquad a \equiv 1 \pmod{m} $$ を満たす整数 $a$ が取れます。この $a$ は $p$ で割り切れず（$a \equiv 1 \pmod p$）、$m$ のどの素因数でも割り切れない（$a\equiv 1 \pmod m$）ので $\gcd(a,n)=1$ です。 二項定理より $\pmod{p^{2}}$ で $$ a^{k} \equiv (1+p)^{k} \equiv 1 + kp \pmod{p^{2}} $$ です（$p^{2}$ 以上の項はすべて $p^{2}$ の倍数）。よって $a^{n-1}\equiv 1 \pmod{p^{2}}$ は $p^{2} \mid (n-1)p$、すなわち $p \mid (n-1)$ と同値です。ところが $p \mid n$ なので $p \nmid (n-1)$ であり、矛盾します。したがって $n$ は平方因子をもちません。 $(p-1)\mid(n-1)$ であること。$p$ を $n$ の素因数とします。$\mathbb{Z}/p\mathbb{Z}$ は体で、その単元群 $(\mathbb{Z}/p\mathbb{Z})^{\times}$ は位数 $p-1$ の巡回群です。その生成元 $g$ を取り、 により $a \equiv g \pmod p$ かつ $a \equiv 1 \pmod{n/p}$ を満たす $a$ を取ると $\gcd(a,n)=1$ です（$n$ は平方因子をもたないので $\gcd(p, n/p)=1$ が使えます）。 カーマイケル数の定義から $a^{n-1}\equiv 1 \pmod n$、特に $a^{n-1}\equiv 1 \pmod p$ です。すなわち $g^{n-1} = 1$ が $(\mathbb{Z}/p\mathbb{Z})^{\times}$ で成り立ちます。$g$ の位数は $p-1$ なので、$g^{k}=1$ となる $k$ は $p-1$ の倍数に限ります。よって $(p-1)\mid(n-1)$ です。 （$561$ の場合、$3-1=2$, $11-1=10$, $17-1=16$ がいずれも $560$ を割り切ることは で確認した通りです。） ## 参考文献 - 高木貞治『初等整数論講義』第 2 版、共立出版、1971 — 第 1 章・第 2 章。合同式の導入からオイラーの定理、原始根までを日本語で読める古典です。 - G. H. Hardy and E. M. Wright, *An Introduction to the Theory of Numbers*, 6th ed., Oxford University Press, 2008 — 第 5 章・第 6 章（合同式とフェルマーの定理）。 - K. Ireland and M. Rosen, *A Classical Introduction to Modern Number Theory*, 2nd ed., Springer GTM 84, 1990 — 第 3 章・第 4 章。剰余環と単元群の構造を代数的に扱っています。 - C. F. Gauss, *Disquisitiones Arithmeticae*, 1801（英訳: Springer, 1986）— 第 1 節・第 2 節に合同記号 $\equiv$ の導入とその基本性質があります。 - R. L. Rivest, A. Shamir, L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", *Communications of the ACM* 21 (1978), 120–126. [DOI: 10.1145/359340.359342](https://doi.org/10.1145/359340.359342) - W. R. Alford, A. Granville, C. Pomerance, "There are Infinitely Many Carmichael Numbers", *Annals of Mathematics* 139 (1994), 703–722. - 雪江明彦『代数学 1 群論入門』日本評論社、2010 — 第 2 章。ラグランジュの定理から を導く筋道が書かれています。 ## Appendix: フェルマーの小定理の組合せ的証明 **数える対象を用意する。** には、剰余類を一切使わない証明があります。$a \ge 1$ を整数、$p$ を素数とし、$a$ 色のビーズを $p$ 個一列に並べた列全体を $X$ とします。$\#X = a^{p}$ です。 **単色の列とそれ以外を分ける。** $X$ に「巡回シフト」を作用させます。列 $(x_1,\ldots,x_p)$ を $(x_2,\ldots,x_p,x_1)$ に写す操作 $\tau$ です。$\tau^{p}$ は恒等写像なので、$X$ は $\tau$ の軌道に分割されます。ある列の軌道の大きさを $k$ とすると、$\tau^{k}$ がその列を動かさない最小の正の整数が $k$ であり、$\tau^{p}$ も動かさないことから $k \mid p$ です。$p$ は素数なので $k = 1$ か $k = p$ しかありません。 **軌道の大きさが 1 になるのは単色のときだけ。** $k=1$ とは $\tau$ で不変、つまり $x_1 = x_2 = \cdots = x_p$ ということです。そのような列は色の数だけあるので $a$ 個です。残りの $a^{p}-a$ 個の列は、すべて大きさ $p$ の軌道に属します。 **数え上げの結論。** $X$ から単色の列を除いた集合は、大きさ $p$ の軌道の直和なので、その要素数は $p$ の倍数です。すなわち $$ p \mid (a^{p}-a), $$ これは にほかなりません。$p \nmid a$ のときは $\gcd(a,p)=1$ なので で $a$ を消去して $a^{p-1}\equiv 1 \pmod p$ を得ます。$a$ が負の整数や $0$ の場合は、$a$ を $p$ で割った余りに置き換えれば により同じ結論が従います。 **この証明の意味。** 「$p$ で割り切れる」という数論的事実を、「$p$ 個ずつの組に分けられる」という数え上げの事実として説明している点が本質です。群 $\mathbb{Z}/p\mathbb{Z}$ が集合に作用し、軌道の大きさが群の位数を割る（）、という軌道・固定点の一般論の最も単純な現れでもあります。