中国剰余定理 (ABC193-E Oversleeping)

ABC193のE問題は連立合同式についての問題でした。これは中国式剰余定理によって解を求めるものです。他にも拡張Eulerの定理についての証明においても中国式剰余定理は登場します。

名前と背景
定理の主張
証明(互いに素、二元のとき)
- 解の存在
- 解の一意性
証明(互いに素、$k$ 元のとき)
証明(一般、二元のとき)
- 解の存在
- 解の一意性
証明(一般、$k$ 元のとき)
解の構築

名前と背景

この定理は中国剰余定理、中国の剰余定理の他、孫子 *1の定理とも呼ばれることがあります。
孫子の定理という名前は南北朝時代の算術書『孫子算経』の下巻問28に由来します*2。

今有物、不知其數。三三數之賸二。五五數之賸三。七七數之賸二。問物幾何。
答曰、二十三。
術曰、三三数之賸二、置一百四十。五五数之賸三、置六十三。七七数之賸二、置三十。幷之、得二百三十三。以二百一十減之、即得。凡三三数之賸一、則置七十。五五数之賸一、則置二十一。七七数之賸一、則置十五。一百六以上、以一百五減之、即得。

これを現代風の書き方に改めると次のようになります。

問: 次の連立合同式をみたす最小の正整数 $x$ を求めよ。

$x \equiv \left\{ \begin{array}{l} 2 \pmod{3}\\ 3 \pmod{5}\\ 2 \pmod{7}\\ \end{array} \right.$

答: $23$
解法: $140 + 63 + 30 = 233$ よりこの $233$ から $210$ を引いて $23$ を得る。一般に

$x \equiv \left\{ \begin{array}{l} a \pmod{3}\\ b \pmod{5}\\ c \pmod{7}\\ \end{array} \right.$

となるとき、その答えは $70a + 21b + 15c$ から $105$ の倍数を引くことで答えが求まる。

定理の主張

中国剰余定理とは次のような定理です。

中国剰余定理(互いに素な場合):

$n_1,\,n_2,\,\dots,\,n_k$ がどの2つをとっても互いに素であるとき、連立合同式
$x \equiv a_i \pmod{n_i}\hspace{2em} (i = 1,\,2,\,\dots,\,k)$
を満たすような整数 $x$ が $\displaystyle \prod_{i = 1}^{k} n_i$ を法として唯1つ存在する。

また、この定理は法が互いに素でない場合に一般化することができます。

中国剰余定理(一般の場合):

任意の $i,\,j$ について $a_i \equiv a_j \pmod{\gcd(n_i,\,n_j)}$ が成立することと
連立合同式
$x \equiv a_i \pmod{n_i}\hspace{2em} (i = 1,\,2,\,\dots,\,k)$
を満たすような整数 $x$ が $\mathrm{lcm}(n_1,\,n_2,\,\dots,\,n_k)$ を法として唯1つ存在することは同値である。

証明(互いに素、二元のとき)

解が存在することとその一意性を証明します。

解の存在

Bézout*3の補題により
$n_1x_1 + n_2x_2 = 1$ を満たす整数 $x_1,\,x_2$ が存在し(拡張Εὐκλείδης*4の互除法などで求めることができます)、このとき

$\left\{ \begin{array}{ll} n_2x_2 \equiv 1 & \pmod{n_1}\\ n_1x_1 \equiv 1 & \pmod{n_2} \end{array} \right.$

であり、 $x' = a_1n_2x_2 + a_2n_1x_1$ とすると

$x' \equiv\left\{ \begin{array}{ll} a_1 & \pmod{n_1}\\ a_2 & \pmod{n_2} \end{array} \right.$

となるため、 $x$ は $x'$ を $n_1n_2$ で割った余りとして存在します。

解の一意性

$x,\,y$ という2数が連立合同式を満たすとします。このとき2つの合同式を 2数が満たすため
$x \equiv y \pmod{n_i}\hspace{2em} (i = 1,\,2)$
より $x - y$ は $n_1$ の倍数でもあり、 $n_2$ の倍数でもあるため、 $n_1n_2$ の倍数となります。条件より $0 \leq x,\,y \lt n_1n_2$ のため $x - y = 0$ 即ち $x = y$ となり、存在するときは一意的であることが分かりました。

証明(互いに素、$k$ 元のとき)

数学的帰納法によって示します。

一元の時は自明に成立します。

$k$ 元の時に成立すると仮定し、 $k + 1$ 元の時について考えます。
この時 $x \equiv a_i \pmod{n_i}\hspace{2em} (i = 1,\,2,\,\dots,\,k)$ の解で $0 \leq x \lt \displaystyle \prod_{i = 1}^{k} n_i$ を満たすものを $b$ とすると
$x \equiv a_i \pmod{n_i}\hspace{2em} (i = 1,\,2,\,\dots,\,k + 1)$ は

$x \equiv\left\{ \begin{array}{ll} b & \displaystyle \left(\mathrm{mod}\ \prod_{i = 1}^{k} n_i\right)\\ a_{k+1} & \pmod{n_{k + 1}} \end{array} \right.$

と等価にとなります。これは二元の連立合同式であるため上の証明よりこれの解が $0 \leq x \lt \displaystyle n_{k + 1} \prod_{i = 1}^{k} n_i = \prod_{i = 1}^{k + 1} n_i$ に唯1つ存在することが導かれ、 $k + 1$ 元の時も成立します。
よって数学的帰納法により題意が示されました。

証明(一般、二元のとき)

まずは「解が唯1つ存在する $\Longrightarrow$ $a_1 \equiv a_2 \pmod{\gcd(n_1,\,n_2)}$ 」について証明します。
連立合同式の解 $x$ について
$x \equiv a_1 \pmod{n_1}$ であり、 $n_1$ は $\gcd(n_1,\,n_2)$ の倍数であるため $x \equiv a_1 \pmod{\gcd(n_1,\,n_2)}$ が成立します。
同様にして $x \equiv a_2 \pmod{\gcd(n_1,\,n_2)}$ が成立するため $a_1 \equiv a_2 \pmod{\gcd(n_1,\,n_2)}$ となります。

次に逆の「 $a_1 \equiv a_2 \pmod{\gcd(n_1,\,n_2)}$ $\Longrightarrow$ 解が唯1つ存在する」について証明します。
これも互いに素な場合と同様に存在性と一意性に分けて証明します。

解の存在

Bézoutの補題により
$n_1y_1 + n_2y_2 = \gcd(n_1,\,n_2)$ を満たす整数 $y_1,\,y_2$ が存在します。 $a_1 \equiv a_2 \pmod{\gcd(n_1,\,n_2)}$ より $a_2 - a_1$ は $\gcd(n_1,\,n_2)$ の倍数であり、 $x_1 = \displaystyle\frac{a_2 - a_1}{\gcd(n_1,\,n_2)} y_1,$ $x_2 = \displaystyle\frac{a_2 - a_1}{\gcd(n_1,\,n_2)} y_2$ も整数で、 $n_1x_1 + n_2x_2 = a_2 - a_1$ を満たします。
ここで $x' = n_1x_1 + a_1 = a_2 - n_2x_2$ とすると

$x' \equiv\left\{ \begin{array}{ll} a_1 & \pmod{n_1}\\ a_2 & \pmod{n_2} \end{array} \right.$

となるため、 $x$ は $x'$ を $\mathrm{lcm}(n_1,\,n_2)$ で割った余りとして存在します。

解の一意性

殆ど互いに素なときと同様です。
$x,\,y$ という2数が連立合同式を満たすとします。このとき2つの合同式を 2数が満たすため
$x \equiv y \pmod{n_i}\hspace{2em} (i = 1,\,2)$
より $x - y$ は $n_1$ の倍数でもあり、 $n_2$ の倍数でもあるため、 $\mathrm{lcm}(n_1,\,n_2)$ の倍数となります。条件より $0 \leq x,\,y \lt \mathrm{lcm}(n_1,\,n_2)$ のため $x - y = 0$ 即ち $x = y$ となり、存在するときは一意的であることが分かりました。

証明(一般、$k$ 元のとき)

互いに素なときとほとんど同じで総積となっているところを最小公倍数に変えればそのまま証明できます。

解の構築

条件を満たせば解が存在することが分かりました。では実際に解はどういう風に求めればいいでしょうか?
実は二元の解の存在についての証明にある構成方法で解を求めることができます。
$k$ 元の場合は数学的帰納法のように $k-1$ 元の結果と $k$ 個目の合同式について同じ方法を用いればいいでしょう。
拡張Εὐκλείδηςの互除法は $O(\log n)$ であるため、 $O(k \log n)$ で解が求まりました。
但し、計算途中のオーバーフローに注意しましょう。このとき $x'$ を計算するときは $x_1$ を $\displaystyle \frac{n_2}{\gcd(n_1,\,n_2)}$ で $\mathrm{mod}$ をとるとオーバーフローが起きにくくなります。このとき $x_1 = \displaystyle \frac{n_2}{\gcd(n_1,\,n_2)}\alpha + \beta$ とすると$$ \begin{align}
n_1\displaystyle \left(x_1 \bmod \frac{n_2}{\gcd(n_1,\,n_2)}\right) + a_1 &= n_1\beta + a_1\\
&= a_2 - n_2x_2 -\displaystyle \frac{n_1n_2}{\gcd(n_1,\,n_2)}\alpha
\end{align} $$ とちゃんと各条件を満たしていることが分かります。