galois.chinese_remainder_theorem¶

galois.chinese_remainder_theorem(a, m)[source]¶

Solves the simultaneous system of congruences for \(x\).

\[ \begin{align}\begin{aligned}x &\equiv a_1\ (\textrm{mod}\ m_1)\\x &\equiv a_2\ (\textrm{mod}\ m_2)\\x &\equiv \ldots\\x &\equiv a_n\ (\textrm{mod}\ m_n)\end{aligned}\end{align} \]

Parameters

a (array_like) – The integer remainders \(a_i\).
m (array_like) – The integer modulii \(m_i\).

Returns

The simultaneous solution \(x\) to the system of congruences.

Return type

int

Examples

In [1]: a = [0, 3, 4]

In [2]: m = [3, 4, 5]

In [3]: x = galois.chinese_remainder_theorem(a, m); x
Out[3]: 39

In [4]: for i in range(len(a)):
   ...:     ai = x % m[i]
   ...:     print(f"{x} % {m[i]} = {ai}, Valid congruence: {ai == a[i]}")
   ...: 
39 % 3 = 0, Valid congruence: True
39 % 4 = 3, Valid congruence: True
39 % 5 = 4, Valid congruence: True