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
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} = {ai} (mod {m[i]}), Valid congruence: {ai == a[i]}") ...: 39 = 0 (mod 3), Valid congruence: True 39 = 3 (mod 4), Valid congruence: True 39 = 4 (mod 5), Valid congruence: True