Definition:Simultaneous Congruences

Definition

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

$\forall i \in \closedint 1 r: \map {P_i} x \equiv 0 \pmod {n_i}$

That is:

\(\ds \map {P_1} x\)

\(=\)

\(\ds 0\)

\(\ds \pmod {n_1}\)

\(\ds \map {P_2} x\)

\(=\)

\(\ds 0\)

\(\ds \pmod {n_2}\)

\(\ds \)

\(\cdots\)

\(\ds \)

\(\ds \map {P_r} x\)

\(=\)

\(\ds 0\)

\(\ds \pmod {n_r}\)

Linear Congruences

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

$\forall i \in \closedint 1 r : 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}\)

Solution

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

Also see

• Results about simultaneous congruences can be found here.