中国剰余定理（CRT:Chinese remainder theorem）とは
中国の剰余定理 (Wikipedia)によると以下のような定理のことです。
\begin{align}
&k個の整数m_1,m_2,...,m_kが互いに素ならば、\\
&任意に与えられる整数 a_1,a_2,...,a_kに対して\\
&x\equiv a_1 \pmod{m_1}\\
&x\equiv a_2 \pmod{m_2}\\
& ...\\
&x\equiv a_k \pmod{m_k}\\
&を満たす整数 x が m_1*m_2*...*m_kを法として一意的に存在する。
\end{align}
これだけだと分かりづらいので例題を見てみましょう。
例題 1．7で割った余りが5かつ、11で割った余りが2となる整数を求めよ。
合同式で書くと以下の式で$x$を求めることになります。
\begin{align}
&\large x\equiv 5 \pmod{7} \\
&\large x\equiv 2 \pmod{11} \\
\end{align}
これをsympyのcrtを使って解いていきます。と言っても非常に簡単で$m_k$と$a_k$のリストをそれぞれ作って渡すだけです。
import sympy.ntheory.modular
m = [7,11]
a = [5,2]
(x, y) = sympy.ntheory.modular.crt(m,a)
print(f"x = {x}, y = {y}, x%7 = {x%7}, x%11 ={x%11}")
## x = 68, y = 77, x%7 = 5, x%11 =2
$\large x=68$が$7*11=77$を法とする解となります。検算でも正しい余りになってます。
例題２．法が合成数のケース
$n=77$のとき以下の式を満たす$x$をすべて求めよ。ただし$0<x<n$とする。
$\large x^3\equiv 1 \ (mod\ n)$
中国剰余定理を逆に考えると、$n=77=7*11$なので、素数$7$と$11$の二つの式に分解できます。
$\large x_1^3\equiv 1\ (mod\ 7)\ \ ...(1)$
$\large x_2^3\equiv 1\ (mod\ 11)\ \ ...(2)$
$\large x = x_1x_2$
各々を以下のプログラムで求めると
pl = [7,11]
fmod = [[i for i in range(1,p) if (i**3) % p == 1] for p in pl]
print(fmod)
# [[1, 2, 4], [1]]
mod 7の答えは[1, 2, 4]、mod 11は[1] となるので以下の3つのケースで中国剰余定理を計算すればよいことになります。これらをsympyのcrtに渡すと答えは(1, 23, 67) となります。
| (m1,a1) | (m2,a2) |
|---|---|
| (7,1) | (11,1) |
| (7,2) | (11,1) |
| (7,4) | (11,1) |
import itertools
for fmp in itertools.product(*fmod):
(x,y) = sympy.ntheory.modular.crt(pl, fmp)
print(x)
# 1
# 23
# 67
（開発環境：Google Colab）