Chinese remainder theorem for non-coprime moduli

Builds on Chinese remainder theorem Greatest common divisor Least common multiple

Statement

Let $m$ and $n$ be positive integers, and let $a$ and $b$ be integers. Let $g = \gcd(m, n)$ and $M = \operatorname{lcm}(m, n)$ . The system $x \equiv a \pmod m$ , $x \equiv b \pmod n$ has an integer solution if and only if $a \equiv b \pmod g$ . In this case, two solutions are congruent modulo $M$ .

Remarks

When $g = 1$ , this is the Chinese remainder theorem for two moduli. The condition is necessary: a solution $x$ gives $a \equiv x \equiv b \pmod g$ , since $g$ divides $m$ and $n$ . For $k$ moduli $n_1, \dots, n_k$ , the system $x \equiv a_i \pmod{n_i}$ has a solution if and only if $\gcd(n_i, n_j) \mid a_i - a_j$ for all $i \neq j$ . For example, $x \equiv 1 \pmod 4$ and $x \equiv 3 \pmod 6$ has the solutions $x \equiv 9 \pmod{12}$ . But $x \equiv 1 \pmod 4$ and $x \equiv 2 \pmod 6$ has no solution.

Reading path

To understand this page from the ground up, read these 7 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Divisibility definition
Congruence modulo n definition
Greatest common divisor definition
Least common multiple definition
Coprime integers definition
Chinese remainder theorem statement
Chinese remainder theorem for non-coprime moduli statement

Tag	`04SJTX9P4N`
URI	`m2://04SJTX9P4N`
Kind	statement, theorem
Writing	W0 stub
MSC	11A07
Status	This copy of the site has no build data. Run `m2 status 04SJTX9P4N`.
Uses	Chinese remainder theorem, Greatest common divisor, Least common multiple

Chinese remainder theorem for non-coprime moduli

Statement

Remarks

Reading path

Further reading

What this page needs for W1

What links here