PythonのSympyを使って中国剰余定理(CRT)を解く

中国剰余定理（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）