# Definition:Simultaneous Congruences

Jump to navigation
Jump to search

## Definition

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}\) |

## Solution

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.