Definition:Simultaneous Congruences

From ProofWiki
Jump to navigation Jump to search


A system of simultaneous congruences is a set of polynomial congruences:

$\forall i \in \left[{1 \,.\,.\, r}\right]: P_i \left({x}\right) \equiv 0 \pmod {n_i}$

That is:

\(\displaystyle P_1 \left({x}\right)\) \(=\) \(\displaystyle 0\) \(\displaystyle \pmod {n_1}\)
\(\displaystyle P_2 \left({x}\right)\) \(=\) \(\displaystyle 0\) \(\displaystyle \pmod {n_2}\)
\(\displaystyle \) \(\cdots\) \(\displaystyle \)
\(\displaystyle P_r \left({x}\right)\) \(=\) \(\displaystyle 0\) \(\displaystyle \pmod {n_r}\)

Linear Congruences

A system of simultaneous linear congruences is a set of linear congruences:

$\forall i \in \left[{1 \,.\,.\, r}\right] : a_i x \equiv b_i \pmod {n_1}$

That is:

\(\displaystyle a_1 x\) \(\equiv\) \(\displaystyle b_1\) \(\displaystyle \pmod {n_1}\)
\(\displaystyle a_2 x\) \(\equiv\) \(\displaystyle b_2\) \(\displaystyle \pmod {n_2}\)
\(\displaystyle \) \(\cdots\) \(\displaystyle \)
\(\displaystyle a_r x\) \(\equiv\) \(\displaystyle b_r\) \(\displaystyle \pmod {n_r}\)


A solution of a system of simultaneous congruences is a residue class modulo $\operatorname{lcm} \left\{{n_1, n_2, \ldots, n_r}\right\}$ such that any element of that class satisfies all the congruences.

The conditions under which this solution exists is explored in the Chinese Remainder Theorem and Solution to Simultaneous Linear Congruences.

From Solutions of Polynomial Congruences, if one such element of a congruence class satisfies the congruences, they all do.