Chinese Remainder Theorem (intro): Foundations

This page builds every piece of notation the parent note quietly assumes. We go in order: nothing appears before it is defined and drawn. If you can count and divide, you can follow line one.

1. The remainder — the star of the whole show

Divide $17$ by $5$ . You get $3$ with $2$ left over. That leftover, $2$ , is the remainder.

Formally: any whole number $n$ divided by a positive whole number $m$ can be written as $n = q m + r, 0 \leq r < m$

$q$ (the quotient) is how many whole copies of $m$ fit inside $n$ .
$r$ (the remainder) is what is left over — and it is always at least $0$ and strictly less than $m$ .

Figure — Chinese Remainder Theorem (intro)

Why does the topic need this? Because CRT never asks "what is $x$ ?" directly. It only ever asks "what is $x$ 's remainder?" for several different divisors. The remainder is the only information CRT works with.

2. The congruence symbol $\equiv$ and $(mod m)$

Writing $n = q m + r$ every time is clumsy. Number theory shortens " $a$ and $b$ leave the same remainder when divided by $m$ " to: $a \equiv b (mod m)$

Read it aloud: " $a$ is congruent to $b$ , modulo $m$ ."

The wiggly $\equiv$ is not an equals sign. It means "same clock position", not "identical number".
$(mod m)$ tells you which clock we are standing at — how many marks it has.

Why the topic needs this: every single line of CRT — $x \equiv a_{1} (mod m_{1})$ , and so on — is a congruence. This is the sentence structure of the whole theorem.

Recall Quick check

Is $23 \equiv 3 (mod 5)$ ? ::: Yes: $23 - 3 = 20$ , and $5$ divides $20$ .

3. $m_{1}, m_{2}, \dots, m_{k}$ and $a_{1}, a_{2}, \dots, a_{k}$ — the subscript notation

The little number below the line is a subscript. It is just a label — a way to say "the first one", "the second one" — without inventing a new letter each time.

$m_{1}, m_{2}, \dots, m_{k}$ are the moduli (plural of modulus): the divisors, one clock per congruence. The $\dots$ means "keep going the same way", and $k$ is simply how many there are.
$a_{1}, a_{2}, \dots, a_{k}$ are the target remainders you want $x$ to hit on each clock.

Why the topic needs it: CRT is a statement about many congruences at once. Subscripts let us write "for every $i$ " instead of drawing three, four, or a hundred separate letters.

4. GCD and "coprime" — the crucial hidden condition

The greatest common divisor of two numbers, written $g cd (a, b)$ , is the largest whole number that divides both of them evenly.

$g cd (12, 18) = 6$ because $6$ divides both, and nothing bigger does.
$g cd (3, 5) = 1$ because the only positive number dividing both $3$ and $5$ is $1$ .

Why the topic needs it: coprimality is the exact condition that stops the clocks from contradicting each other. See more on this in Modular Arithmetic Basics. Without it, two congruences can demand incompatible things (like " $x$ is even" and " $x$ is odd").

5. The multiplicative inverse $M_{i}^{- 1} mod m_{i}$

On the $m$ -mark clock, there is no "divide" button. So how do we undo a multiplication? We find a number that, when multiplied in, gives $1$ .

Why the topic needs it: CRT's construction has a step "solve $k m_{1} \equiv (a_{2} - a_{1}) (mod m_{2})$ ". To isolate $k$ you must multiply both sides by $m_{1}^{- 1}$ . This inverse only exists when $g cd (m_{1}, m_{2}) = 1$ — which is exactly why coprimality is required. The tool that finds it is the Extended Euclidean Algorithm, and the guarantee it exists comes from Bezout's Identity.

Recall Quick check

What is $3^{- 1} mod 5$ ? ::: $2$ , because $3 \cdot 2 = 6 \equiv 1 (mod 5)$ .

6. Product notation $M = \prod m_{i}$ and $M_{i} = M / m_{i}$

$M$ is just the product of every modulus multiplied together: $M = m_{1} \cdot m_{2} \dots m_{k}, written compactly as M = \prod_{i = 1}^{k} m_{i} .$ The big $\prod$ (capital Greek "pi") means "multiply all of these", exactly as a big $\sum$ means "add all of these".

$M_{i}$ is $M$ with the $i$ -th modulus removed: $M_{i} = \frac{M}{m _{i}} = m_{1} \dots m_{i - 1} \cdot m_{i + 1} \dots m_{k} .$

Why the topic needs it: $M$ is the size of the range $[0, M)$ where the unique answer lives, and the $M_{i}$ are the building blocks of the solution formula $x \equiv \sum a_{i} M_{i} y_{i}$ .

17

divided by

5

, name the quotient and remainder.

Quotient

3

, remainder

2

(since

17 = 3 \cdot 5 + 2

What does

a \equiv b (mod m)

mean in plain words?

a

and

b

leave the same remainder mod

m

; equivalently

m

divides

a - b

What is a subscript

m_{i}

A label for "the

i

-th modulus" — a naming device, not a power.

Define "pairwise coprime".

Every pair from the list has GCD equal to

1

{6, 10, 15}

pairwise coprime?

No —

g cd (6, 10) = 2

What is

a^{- 1} mod m

The number

y

with

a \cdot y \equiv 1 (mod m)

; the modular stand-in for division.

When does

a^{- 1} mod m

exist?

Exactly when

g cd (a, m) = 1

What does

M_{i} = M / m_{i}

contain?

The product of all moduli except

m_{i}

; it is

0

on every other clock, invertible on clock

i

Expand

\sum_{i = 1}^{3} a_{i} M_{i} y_{i}

a_{1} M_{1} y_{1} + a_{2} M_{2} y_{2} + a_{3} M_{3} y_{3}

Foundations — Chinese Remainder Theorem (intro)

1. The remainder — the star of the whole show

2. The congruence symbol $\equiv$ and $(mod m)$

3. $m_{1}, m_{2}, \dots, m_{k}$ and $a_{1}, a_{2}, \dots, a_{k}$ — the subscript notation

4. GCD and "coprime" — the crucial hidden condition

5. The multiplicative inverse $M_{i}^{- 1} mod m_{i}$

6. Product notation $M = \prod m_{i}$ and $M_{i} = M / m_{i}$

7. The summation symbol $\sum$

How the foundations feed the theorem

Equipment checklist