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:

\(\ds P_1 \left({x}\right)\) \(=\) \(\ds 0\) \(\ds \pmod {n_1}\)
\(\ds P_2 \left({x}\right)\) \(=\) \(\ds 0\) \(\ds \pmod {n_2}\)
\(\ds \) \(\cdots\) \(\ds \)
\(\ds P_r \left({x}\right)\) \(=\) \(\ds 0\) \(\ds \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:

\(\ds a_1 x\) \(\equiv\) \(\ds b_1\) \(\ds \pmod {n_1}\)
\(\ds a_2 x\) \(\equiv\) \(\ds b_2\) \(\ds \pmod {n_2}\)
\(\ds \) \(\cdots\) \(\ds \)
\(\ds a_r x\) \(\equiv\) \(\ds b_r\) \(\ds \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.