これは何?
問題
$3$ で割ると$2$余り、$5$ で割ると $3$ 余り、$7$ で割ると $2$ 余るような数は何か？
この問題は、「百五減算」と呼ばれていて、小学生でもわかる解法がこちらにあります。
もう少しお話っぽく書くと、
百五減算の問答
-
老人 ：そなたの歳を当てよう。 -
あなた：（えっ、うさんくさいおんさんやな。。） -
老人：$3$ で割るといくつあまるかね？
-
あなた：〇 です。
-
老人：では、$5$ で割るといくつあまるかね？
-
あなた：△ です。
-
老人：では、$7$ で割るといくつあまるかね？
-
あなた：□ です。
-
老人：なるほど、そなたの歳は $23$ じゃな。
老人の計算： $〇 \times 70 + △ \times 21 + □ \times 15$ が答え。ただし、$105$ より大きくなれば、$105$を引く。 最初の問題の場合、$2 \times 70 + 3 \times 21 + 2 \times 15 = 233$ で、$105$ を引くと $233 - 105 = 128$、さらに $105$ を引くと $128 - 105 = 23$。よって、あなたの歳は $23$。
ここで、105を引いていくことで「百五減算」と呼ぶ、という説があります。
$\newcommand{\bm}[1]{\boldsymbol{#1}}$
これを数学的に解く 中国剰余定理（Chinese Remainder Theorem） を調べていたら、そのオイラーによる解法の構造が、線形代数における直交射影（基底とその双対基底によるエンコーダ・デコーダペア）を用いた恒等写像の分解と、非常に似ていることに気づきました。これらは、並行な同じ構造（直交冪等元による単位元の分解）を共有しているのです！（何言っているか分からないですよね🤔）
この記事では、この発見を、具体的な 3, 5, 7 を用いた合同式の計算からスタートし、それが幾何学的な「直交射影」や「基底とその双対基底によるベクトルの座標展開」とどのように一対一で対応しているのかを分かりやすく解説します（わざと難しく言ってますが、以下の内容は平易です）。
具体的な合同式：3, 5, 7 の例
数式で書くと、以下の連立合同式を満たす整数 $x$ を求める問題になります。ここで、$3,5,7$はどの2つも互いに素です。
$$
\begin{cases}
x \equiv 2 \pmod 3 \\
x \equiv 3 \pmod 5 \\
x \equiv 2 \pmod 7
\end{cases}
$$
この問題を満たす $x$ をガウスの構成法で解いてみましょう。ある $x$ が解として見つかったら、$105 = 3 \times 5 \times 7$ をその解に足してもそれは解になりますね。よって、最も小さい自然数 $x \pmod{105}$ を求めることにします。
基底元の構成
では、それぞれの法について、その法だけ1で、他の法では0となる特別な元 $e_1, e_2, e_3$ を考えてみます。次のような条件を満たすものです。法を「方向」と考えると、線形代数の基底の各方向（法3軸、法5軸、法7軸）の単位ベクトルに似ています。線形代数の用語にならって基底、基底元と呼んでおきます。
$$
\begin{cases}
e_1 \equiv 1 \pmod 3 \\
e_1 \equiv 0 \pmod 5 \\
e_1 \equiv 0 \pmod 7
\end{cases} \cdots (1)
\quad
\begin{cases}
e_2 \equiv 0 \pmod 3 \\
e_2 \equiv 1 \pmod 5 \\
e_2 \equiv 0 \pmod 7
\end{cases} \cdots (2)
\quad
\begin{cases}
e_3 \equiv 0 \pmod 3 \\
e_3 \equiv 0 \pmod 5 \\
e_3 \equiv 1 \pmod 7
\end{cases} \cdots (3)
$$
これらを具体的に計算します。一般的な記述として、
| 記号 | 意味 |
|---|---|
| $m_1 = 3, m_2 = 5, m_3 = 7$ | 各法 |
| $b_1 = 2, b_2 = 3, b_3 = 2$ | 各法の剰余 |
| $M = m_1 m_2 m_3 = 105$ | 全法の積 |
| $M_1 = 35, M_2 = 21, M_3 = 15$ | 自身の法以外の法の積 |
| $e_1, e_2, e_3$ | 基底元（直交冪等元） |
という文字を使います。
$e_1$ の構成 ：
$e_1$ は他の法の最大公約数 $M_1 = 5 \times 7 = 35$ で割り切れる必要があります(式1)。よって、 $e_1 = 35y_1$ すなわち、
$$
35 y_1 \equiv 1 \pmod 3
$$ となる $y_1$ を探します。これは、「35 の法3での逆元」になります。左辺から3の倍数である $33y_1$ を引いて、
$$
2 y_1 \equiv 1 \pmod 3
$$ これを解くと、
$$
y_1 \equiv 2 \pmod 3
$$ です。解き方は、小さな数から順に入れて見つけてもいいですし、一般的には、高校で習う一次不定方程式（$ax + by = c$）を解くやり方です。この $y_1$ は、また、$M_1$ の法 $m_1$ での逆元と解釈できるので、
$$y_1 = [M_1^{-1}]_{\pmod{m_1}}$$ と書くこともできます。よって、
$$
e_1 = M_1 y_1 = 35 \times 2 = 70
$$ が求まります。
もう一度言います、 $e_1$ は他の法すべて（3および5すなわち35）で割り切れ、かつ、3で割って1余る数、すなわち、(1)の解になります。
他の法で割り切れ、3で割った余りが一般的に $b_1$ になるなら、その解は、$b_1 e_1$ になりますね。つまり、
$$ \begin{cases}
x = 1 \pmod{m_1} \\
x = 0 \pmod{m_2} \\
x = 0 \pmod{m_3}\end{cases} \text{の解が、} e_1 \qquad
\begin{cases}
x = b_1 \pmod{m_1} \\
x = 0 \pmod{m_2} \\
x = 0 \pmod{m_3}
\end{cases} \text{の解が、} b_1 e_1
$$ となります。
$e_2$ の構成:
$M_2 = 3 \times 7 = 21$ を用意します。解くべき(式2)は、
$$21y_2 \equiv 1 \pmod 5$$ すでに法 5 で 1 になっているので、21の法5での逆元は $y_2 = 1$ です。よって、
$$e_2 = M_2 y_2 = 21 \times 1 = 21$$ $e_2$ は他の法すべて（3および7すなわち21）で割り切れ、かつ、5で割って1余る数、すなわち、(式2)の解になります。
$e_3$ の構成:
$M_3 = 3 \times 5 = 15$ を用意します。解くべき(式3)は、
$$15y_3 \equiv 1 \pmod 7$$ を解きます。同様に、すでに法 7 で 1 になっているので、逆元 $y_3 = 1$ です。
$$e_3 = M_3 y_3 = 15 \times 1 = 15$$ $e_3$ は他の法すべて（3および5すなわち15）で割り切れ、かつ、7で割って1余る数、すなわち、(式3)の解になります。
ここまでで、基底元 $e_1 = 70, e_2 = 21, e_3 = 15$ が求まりました。
線形結合（解の合成）
得られた(式1,2,3)を満たす基底 $e_1, e_2, e_3$ を用いて、元の合同式の右辺の値 $(2, 3, 2)$ を重ね合わせで作ります。線形代数の「線形結合」にそっくりです。
$$
\begin{aligned}
x &\equiv 2 e_1 + 3 e_2 + 2 e_3 \pmod{105} \\
&\equiv 2(70) + 3(21) + 2(15) \\
&= 140 + 63 + 30 = 233 \equiv 23
\end{aligned}
$$ なぜこれが解かって？一行目を見てください。 $x$ を3で割ると、$e_2, e_3$ が3で割り切れるので、 $2e_1$ になります。 さらに、$e_1$ は3で割ると1なので、$2e_1 \equiv 2 \pmod 3$。他の法も同様です。
実際に確認すると、
$$
\begin{align*}
23 = 7 \times 3 + 2 \equiv 2 \pmod 3 \\
23 = 4 \times 5 + 3 \equiv 3 \pmod 5 \\
23 = 3 \times 7 + 2 \equiv 2 \pmod 7
\end{align*}
$$ となり、正しく解が求まっています。
この構成法の代数的特徴
構成した $e_1, e_2, e_3$ は $\pmod{105}$ の世界で次のようなとても整った性質を持っています。
-
直交性(Orthogonality）: 異なるもの同士を掛けると $0$ になる。
$$e_i e_j \equiv 0 \pmod{105} \quad (i \neq j)$$ 例: $e_1 e_2 = 70 \times 21 = 1470 = 14 \times 105 \equiv 0$
これは、 $e_i e_j$ が含む $M_i M_j$ が $M$ の倍数になるためです。 -
冪等性 (Idempotency): 二乗して自分自身に戻る。
$$e_i^2 \equiv e_i \pmod{105}$$ 例: $e_1^2 = 4900 = 46 \times 105 + 70 \equiv 70 = e_1$
これは、$e_i^2 = M_iy_i M_iy_i = M_i (y_i M_i)y_i \equiv M_i e_i y_i \equiv M_i y_i = e_i$ となるためです。
3. 1の分解 (Resolution of Identity): すべて足すと $1$ になる。
構成から得られた基底元を実際に計算します。
$$e_1 + e_2 + e_3 = 70 + 21 + 15 = 106$$ $M = 105$ で割った余りを求めると：
$$e_1 + e_2 + e_3 \equiv 1 \pmod{105}$$
これは、$e_1, e_2, e_3$ が(式1,2,3)を満たすように作られていることかわかるでしょう。(式1,2,3)の9つの式を、法ごとに横に足します。
$$
\begin{cases}
e_1 + e_2 + e_3 \equiv 1 + 0 + 0 = 1 \pmod{3} \\
e_1 + e_2 + e_3 \equiv 0 + 1 + 0 = 1 \pmod{5} \\
e_1 + e_2 + e_3 \equiv 0 + 0 + 1 = 1 \pmod{7}
\end{cases} $$ この和 $e_1 + e_2 + e_3$ は、3,5,7 で割った余りがすべて 1 になるので、105 で割った余りも 1 になります。
$$e_1 + e_2 + e_3 \equiv 1 \pmod{105}$$
一般的な解
問題より一般的に書くと、
$$
\begin{cases}
x \equiv b_1 \pmod{m_1} \\
x \equiv b_2 \pmod{m_2} \\
x \equiv b_3 \pmod{m_3}
\end{cases} $$ の解は、各法の剰余 $b_i$ を用いて、次のように書けます。
$$ x \equiv \sum_{i=1}^3 b_i e_i \pmod{M}$$ ここで、 $e_i = M_iy_i = M_i [(M_i)^{-1}]_{\pmod{m_i}} \cdots (4)$
$M_i [(M_i)^{-1}]_{\pmod{m_i}}$ という形（「何か」と「何かの逆」の積）を覚えておいてください。
3次元格子空間での表現（線形空間との対応）
得られた解、
$$
\begin{aligned}
x &\equiv 2 e_1 + 3 e_2 + 2 e_3 \pmod{105} \\
&\equiv 23 \pmod{105}
\end{aligned}
$$ を見ると、なんだか座標のように見えますよね？
- 原点 $0$: 3つの座標軸の起点（共通のゼロ）です。
- 外枠: $3 \times 5 \times 7$ の直方体領域の輪郭を描いており、この空間全体を示しています。
- 105個の格子点: グリッド線の各交点に薄い青色のドットとして配置されており、全空間（105で割った余の可能性105通り）に対応するすべての座標を示しています。
-
基底ベクトル $e_1, e_2, e_3$:
- $e_1 = 70 \equiv (1, 0, 0)$ （緑色の矢印）
- $e_2 = 21 \equiv (0, 1, 0)$ （オレンジ色の矢印）
- $e_3 = 15 \equiv (0, 0, 1)$ （紫色の矢印）
これらは原点から伸びる標準基底ベクトル（直交する単位ベクトル）として機能していることが視覚的に分かります。
-
解 $x = 23$:
- $x \equiv 23 \equiv 2e_1 + 3e_2 + 2e_3 \equiv (2, 3, 2)$
各基底ベクトルをそれぞれ $2, 3, 2$ 倍して線形結合した位置 $(2, 3, 2)$ を指しています。
- $x \equiv 23 \equiv 2e_1 + 3e_2 + 2e_3 \equiv (2, 3, 2)$
線形代数の類似問題
中国剰余定理の「直交冪等元による分解」は、線形代数学における恒等写像の射影への分解と並行な構造が見えます。
ここからは、この対応を見ていきます。
幾何的な問題設定
3次元のベクトル空間 $V=\mathbb{R^3}$ を考えます。通常は $x, y, z$ 軸を取ってこのベクトルを3つの実数として表現しますが、これを別の直交軸（直交基底）で表現することもできます。
ベクトル $\bm{x} \in V$があって、その座標は分からないとします。ただし、基底ベクトル３つ、$\bm{p_1}, \bm{p_2},\bm{p_3} \in V$ とし、その基底での座標成分 $b_1, b_2, b_3$ が分かっています。そこから、$\bm{x}$ を復元したいとします。
ここで、$\bm{p_i}$ はすべて長さは1であり互い直交するとします。これを行列で書くと、こうなります。 $I$ を $3 \times 3$ 単位行列として、
$$
P = \begin{bmatrix} \bm{p_1} & \bm{p_2} & \bm{p_3} \end{bmatrix}, \quad P^\top P = P P^\top = I \text{(直交行列)}
$$ $P$ は3つの基底を横に並べた $3 \times 3$ 行列です。$P^\top P$ はそれぞれのベクトルの内積を取った9つの値を並べた行列になり、$I$ になりますね。 $P$ の逆行列は $P^\top$ なのです。つまり $P$ は直交行列です。
$\bm{x}$ の $\bm{p_i}$ 軸の座標は、内積 $\bm{p_i} \cdot \bm{x}$ なので、分かっている各軸方向の座標値を書き出せば、
$$
\begin{cases}
\bm{p_1} \cdot \bm{x} = b_1 \\
\bm{p_2} \cdot \bm{x} = b_2 \\
\bm{p_3} \cdot \bm{x} = b_3
\end{cases}
$$ これを行列表記して、
$$ \bm{b} =\begin{bmatrix}
b_1 \\ b_2 \\ b_3
\end{bmatrix}
$$ と書けば、
$$
P^\top \bm{x} = \bm{b}
$$ これはまさに、先ほどの連立合同式「$x \equiv b_i \pmod{m_i}$」の線形代数版です（数学的には、基底 $\bm{p_i} \in V$ の双対基底を $\bm{p^i} \in V^*$ として考える方が正確ですがここでは内積を用いています）。
任意のベクトル $\bm{x}$ は次のように復元できます。(式4)の両辺に $P$ を掛けて、 $P P^\top = I$ を使うと、
$$
\bm{x} = P \bm{b} = b_1 \bm{p_1} + b_2 \bm{p_2} + b_3 \bm{p_3}
$$ これは、CRTにおける解の公式、
$$x \equiv b_1 e_1 + b_2 e_2 + b_3 e_3$$ と全く同じ構造です。これを計算すれば、$\bm{x}$ を復元できます。さらに、もとの内積による基底ベクトル方向の測定と合わせて書いてみると、
$$
\begin{align*}
\bm{x} &= (\bm{p_1} \cdot \bm{x}) \bm{p_1} + (\bm{p_2} \cdot \bm{x}) \bm{p_2} + (\bm{p_3} \cdot \bm{x}) \bm{p_3}\\
&= (\bm{p_1}^\top \bm{x}) \bm{p_1} + (\bm{p_2}^\top \bm{x}) \bm{p_2} + (\bm{p_3}^\top \bm{x}) \bm{p_3}\\
&= (\bm{p_1} \bm{p_1}^\top) \bm{x} + (\bm{p_2} \bm{p_2}^\top) \bm{x} + (\bm{p_3} \bm{p_3}^\top) \bm{x}\\
&= P_1 \bm{x} + P_2 \bm{x} + P_3 \bm{x}
\end{align*}
$$
$\bm{x}$ の各軸の座標成分は、$\bm{p_i}$ との内積によって求まり（エンコード）、それをその軸方向のベクトルにする（デコード）ために $\bm{p_i}$ を掛けています。この二つの操作を一度に線形変換として合わせたものが、射影行列 $P_i = \bm{p_i} \bm{p_i}^\top$ なんです。これが、中国剰余定理の $e_i$ に対応します。
データサイエンスや機械学習では、ベクトルの次元を下げることをエンコード、元の次元に戻すことをデコードと言ったりしますので、そのニュアンスで使っています。
$\bm{p_i}^\top$ を掛ける（内積）と1つの「スカラー」（座標値）が取り出せます。それに $\bm{p_i}$ を掛けるとその方向の「ベクトル」となります。この二つの操作を一度に行うのが、射影行列 $P_i = \bm{p_i} \bm{p_i}^\top$ は、$3 \times 3$ のランク1行列になります。
中国剰余定理の $e = M [M^{-1}]_{\pmod{m}}$ の形とも似ていますよね。こちらも、 $\pmod{m}$ にエンコードして、$\pmod{M}$ にデコードしています。
直交行列の性質
ここでも、
-
直交性:
$$P_i P_j = 0 \quad (i \neq j)$$ -
冪等性:
$$P_i^2 = P_i$$ -
1の分解:
$$P_1 + P_2 + P_3 = I$$
が成り立ちます。
2つの構造の並行性
中国剰余定理
$m_1=3, m_2=5, m_3=7$ により、任意の整数 $x \in \mathbb{Z}/105\mathbb{Z}$ は、次の3次元空間の格子点（座標）へと一対一に対応させることができます。
$$ \mathbb{Z}/105\mathbb{Z} \cong \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/5\mathbb{Z} \times \mathbb{Z}/7\mathbb{Z}$$ この全単射写像は、次のように書けます。
$$x \mapsto (b_1, b_2, b_3 ) = (x \bmod 3, x \bmod 5, x \bmod 7)$$
線形代数
空間 $V$ を3つの独立した1次元部分空間の直和に分解していることに相当します。
$$V = \mathrm{span}(\bm{p_1}) \oplus \mathrm{span}(\bm{p_2}) \oplus \mathrm{span}(\bm{p_3})$$ 各 $P_i$ は、この直和分解に付随する「部分空間への直交射影」となっています。
この全単射写像は、次のように書けます。
$$\bm{x} \mapsto (b_1, b_2, b_3)=P_1 \bm{x} +P_2 \bm{x} +P_3 \bm{x}$$
対応のまとめ
$$
\begin{aligned}
\text{中国剰余定理: } \quad x &\equiv b_1 e_1 + b_2 e_2 + b_3 e_3 \pmod M \\
\text{線形代数: } \quad \bm{x} &= b_1 \bm{p_1} + b_2 \bm{p_2} + b_3 \bm{p_3}\\
&= P_1 \bm{x} + P_2 \bm{x} + P_3 \bm{x}
\end{aligned}
$$
中国剰余定理と線形代数の構造的対応を一覧にまとめます。
| 概念 | 中国剰余定理 | 線形代数（双対空間と射影） |
|---|---|---|
| 全体の空間 | 環 $\mathbb{Z}/M\mathbb{Z}$ （整数を 105 で割った余り1...105） | ベクトル空間 $V$ (3次元) |
| 方向の評価（エンコード） | 各法による剰余 $b_i = x \bmod m_i$ | 内積（双対基底の作用） $b_i = \bm{p}_i^\top \bm{x}$ |
| 方向の復元（デコード） | 直交冪等元 $e_i$ による復元 $x \equiv \sum_i b_i e_i \pmod M$ | 射影作用素 $P_i$ による復元 $\bm{x} = \sum_i b_i \bm{p_i} = \sum_i P_i \bm{x}$ |
| 方向の抽出＆復元（射影子＝エンコーダ・デコーダペア） | 直交冪等元 $e_i = M_i [M_i^{-1}]_{\pmod {m_i}}$ | 射影作用素 $P_i = \bm{p_i} \bm{p_i}^\top$ |
| 直交性 | $e_i e_j \equiv 0 \pmod M \quad (i \neq j)$ | $P_i P_j = O \quad (i \neq j)$ |
| 冪等性 | $e_i^2 \equiv e_i \pmod M$ | $P_i^2 = P_i$ |
| 1の分解 | $e_1 + e_2 + e_3 \equiv 1 \pmod M$ | $P_1 + P_2 + P_3 = I$ |
| 空間の分解 | $\mathbb{Z}/M\mathbb{Z} \cong \bigotimes_i \mathbb{Z}/m_i\mathbb{Z}$ | $V \cong \bigoplus_i \mathrm{span}(\bm{p_i})$ |
| 分解の全体 | $x \equiv \sum_i b_i e_i \pmod M$ | $\bm{x} = \sum_i b_i \bm{p_i} = \sum_i P_i \bm{x}$ |
中国剰余定理の構造と、線形代数の射影作用素の構造の面白い対応関係が見えてきました。どちらも、直交性、冪等性、恒等写像の分解という共通の性質を持っています。
この話は、より数学的には環論のイディアルの言葉、線形代数の双対空間（汎関数空間）の言葉でより厳密に書くことができるでしょう。その部分は筆者も勉強中です。
興味のある方は、以下の日本語解説記事も参照してください。
- 数学の景色: 中国剰余定理とその詳しい証明
https://mathlandscape.com/chinese-remainder/ - Academaid: 【徹底解説】中国剰余定理とは
https://academ-aid.com/math/thm-chinese-remainder - AtCoder: 中国剰余定理（アルゴリズム解説）
https://info.atcoder.jp/entry/algorithm_lectures/chinese_remainder_theorem
筆者の本
こちらで本を紹介しています。
https://anagileway.com/visual-linear-algebra/
