Definition:Simultaneous Congruences/Linear

Definition

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 linear congruences can be found here.