Chinese Remainder Theorem (intro): Question bank

Before you start, keep three plain-word anchors in mind:

A congruence $x \equiv a (mod m)$ just says " $x$ and $a$ leave the same remainder when divided by $m$ " — equivalently, $m$ divides $x - a$ .
Coprime ( $g cd = 1$ ) means two numbers share no prime factor.
"Unique modulo $M$ " means there is exactly one solution in the window $0, 1, \dots, M - 1$ , and every other solution is that one plus a whole number of $M$ 's.

The picture behind CRT — one screen so the symbols are earned

Every question below leans on three symbols: $M$ , $M_{i}$ and $y_{i}$ . Let us fix them with a picture before they appear in a trap, using the concrete system $x \equiv 2 (mod 3), x \equiv 3 (mod 5), x \equiv 2 (mod 7)$ .

The next figure shows why each of these three numbers exists: each modulus draws a repeating "remainder colouring" of the number line, and CRT asks for the one point where all three colourings agree inside $[0, 105)$ .

Figure — Chinese Remainder Theorem (intro)

Now watch a single term $a_{i} M_{i} y_{i}$ do its job. $M_{i}$ is already $0$ in every slot but the $i$ -th; multiplying by $y_{i}$ makes it $1$ in its own slot; multiplying by $a_{i}$ makes it $a_{i}$ there. The three terms are like three spotlights, each lighting exactly one congruence and staying dark on the others.

True or false — justify

CRT with coprime moduli always has at least one solution.

True. Coprimality guarantees the needed inverses exist, so the constructive formula produces a concrete

x

— existence is never in doubt when moduli are pairwise coprime.

If the moduli are pairwise coprime, the solution is unique over all integers.

False. It is unique only modulo

M = \prod m_{i}

; there are infinitely many integer solutions, all differing by multiples of

M

. Uniqueness means one per length-

M

window.

"Pairwise coprime" and "the whole product is coprime to each modulus" say the same thing.

Roughly yes for the pairwise part, but the real requirement is that each pair shares no factor.

6, 10, 15

have

g cd

of all three

= 1

yet are not pairwise coprime (

g cd (6, 10) = 2

), so CRT's basic form does not apply.

A system with non-coprime moduli can still have a solution.

True — sometimes. If the overlapping constraints happen to agree (e.g.

a_{i} \equiv a_{j} (mod g cd (m_{i}, m_{j}))

), a solution exists; it just isn't guaranteed and the modulus of uniqueness becomes

lcm

, not the product.

The number of solutions in

[0, M)

is always exactly one when moduli are coprime.

True. That is the whole content of "unique solution modulo

M

": precisely one residue class works.

g cd (m_{1}, m_{2}) = d > 1

and the constraints agree, the solution is unique modulo

m_{1} m_{2}

False. It is unique modulo

lcm (m_{1}, m_{2}) = \frac{m _{1} m _{2}}{d}

, which is smaller than the product. The overlap collapses the effective range.

Swapping the order of the congruences changes the answer.

False. The solution set is a property of the constraints, not their listing order. Reordering only reshuffles the terms in the sum

\sum a_{i} M_{i} y_{i}

; the total is the same modulo

M

Every integer

a_{i}

is a valid right-hand side, even a huge or negative one.

True. CRT places no limit on the

a_{i}

; they are just residues. A negative

a_{i}

is fine — reduce it mod

m_{i}

if you like, but you needn't.

Spot the error

"The inverse of

5

modulo

7

1/5

Wrong — there is no fraction here. A modular inverse is an integer

y

with

5 y \equiv 1 (mod 7)

; that's

y = 3

since

5 \cdot 3 = 15 \equiv 1

. Ordinary division doesn't exist in modular arithmetic.

M_{i}

M

times

m_{i}

Wrong — it's

M_{i} = M / m_{i}

, the product of all moduli except

m_{i}

(in our worked case

M_{1} = 105/3 = 35

, not

105 \cdot 3

). This makes

M_{i}

divisible by every other modulus (so contributing

0

there) while staying coprime to

m_{i}

"I'll apply CRT to

x \equiv 2 (mod 4), x \equiv 3 (mod 6)

using the standard formula."

Wrong —

g cd (4, 6) = 2 \neq = 1

, so the basic formula fails:

M_{i}^{- 1} mod m_{i}

doesn't exist. Also the constraints conflict (

x

even vs

x

odd), so there's no solution at all.

"Since each term

a_{i} M_{i} y_{i}

satisfies the

i

-th congruence, the sum satisfies all of them."

Correct reasoning, actually — no error. Each other term is

\equiv 0 (mod m_{i})

, so only the

i

-th term survives mod

m_{i}

, giving

x \equiv a_{i}

. The trap is doubting a true statement.

M_{i} y_{i} \equiv 1 (mod M)

, so the term equals

a_{i}

Wrong — the inverse relation holds only

(mod m_{i})

, not

(mod M)

M_{i} y_{i}

1

mod

m_{i}

but

0

mod the other moduli; it is not

1

mod the whole

M

g cd (M_{i}, m_{i}) = 1

needs to be checked separately each time."

Unnecessary — it's automatic. Because the

m_{j}

are pairwise coprime to

m_{i}

, their product

M_{i}

shares no factor with

m_{i}

, so

g cd (M_{i}, m_{i}) = 1

for free.

"If one congruence is

x \equiv 0 (mod m_{i})

, CRT can't handle it."

Wrong —

a_{i} = 0

is a perfectly ordinary residue. The term

a_{i} M_{i} y_{i}

just vanishes; the other congruences still pin down

x

. Nothing breaks.

Why questions

Why does coprimality make the constraints "independent"?

Because two coprime moduli share no prime, no single prime power is constrained twice. Their remainder conditions carve the number line along disjoint axes, so no two conditions can ever contradict (see the non-overlapping colourings in figure s01).

Why must

M_{i}

be coprime to

m_{i}

for the construction to work?

Only a number coprime to

m_{i}

has an inverse mod

m_{i}

. Without that inverse

y_{i}

, we couldn't scale

M_{i}

to be

\equiv 1 (mod m_{i})

, and the term wouldn't deliver

a_{i}

to the

i

-th slot (this is the "turn the spotlight to

1

" step in figure s02).

Why does the term

a_{i} M_{i} y_{i}

contribute

0

to every other congruence?

Because

M_{i} = M / m_{i}

is a multiple of every

m_{j}

with

j \neq = i

. Any multiple of

m_{j}

\equiv 0 (mod m_{j})

, so those terms silently disappear when you reduce mod

m_{j}

— the dark cells in figure s02.

Why is the modulus of uniqueness the product

M

and not something smaller?

When moduli are pairwise coprime there is no shared structure to collapse, so the combined "period" is the full product. The combined constraint repeats only every

M

steps.

Why can a single congruence

x \equiv a (mod m)

be seen as CRT with

k = 1

Trivially: with one modulus,

M = m

M_{1} = 1

y_{1} = 1

, and the formula returns

x \equiv a (mod m)

. CRT is the multi-constraint generalisation of this base case.

Why does CRT underpin RSA speed-ups?

RSA works modulo

N = pq

with

p, q

distinct primes (hence coprime). CRT lets you compute mod

p

and mod

q

separately — much cheaper — then reassemble, exploiting that

x

mod

N

is determined by its pair of residues.

Why does Fermat's Little Theorem pair naturally with CRT in these applications?

Fermat gives cheap exponent reductions mod each prime (

a^{p - 1} \equiv 1

), and CRT is the machine that glues the per-prime results back into one answer mod the product. They divide and conquer together.

Why doesn't reducing each

a_{i}

modulo

m_{i}

first change the answer?

Because a congruence only cares about the remainder. Replacing

a_{i}

a_{i} mod m_{i}

gives the identical constraint, so the solution set is untouched — it just keeps the numbers small.

The general-gcd case — when moduli are not coprime

The basic theorem demands coprime moduli, but the world often hands you moduli that share factors. There is a repaired version, and these items make it precise.

Two congruences with

g cd (m_{1}, m_{2}) = d

are solvable exactly when what condition holds?

When

a_{1} \equiv a_{2} (mod d)

— the two right-hand sides must already agree on the shared part

d

. Otherwise one demands (say) even and the other odd, and no

x

can satisfy both.

When that solvability condition holds, over what modulus is the solution unique?

Modulo

lcm (m_{1}, m_{2}) = \frac{m _{1} m _{2}}{d}

, not the product. The shared factor

d

is counted once, not twice, so the combined period shrinks.

How can you reduce a non-coprime system to a coprime one?

Split each modulus into prime powers, keep one copy of each prime power (the strongest constraint), and check the overlaps agree. What remains is a set of prime-power moduli that are pairwise coprime, so basic CRT applies.

Why does gluing prime-power pieces recover the answer?

Because coprime prime powers multiply to the original modulus, and CRT says residues mod coprime factors determine the residue mod their product. Splitting and re-gluing is loss-free precisely when the factors are coprime.

x \equiv 1 (mod 4), x \equiv 3 (mod 6)

solvable, and if so mod what?

Yes:

g cd (4, 6) = 2

and

1 \equiv 3 (mod 2)

(both odd), so it's solvable, unique modulo

lcm (4, 6) = 12

. The solution is

x \equiv 9 (mod 12)

Edge cases

What if two moduli are equal, say both

5

Then

g cd (5, 5) = 5 \neq = 1

, violating coprimality. Either the two

a_{i}

agree mod

5

(redundant — drop one) or they clash (no solution). Basic CRT does not apply.

What if a modulus is

1

x \equiv a (mod 1)

is always true (everything is

\equiv 0 (mod 1)

), so it adds no information. It's harmlessly coprime to everything and can be ignored;

M

is unchanged.

What is the solution to the empty system (no congruences at all)?

Every integer works —

M = 1

(empty product) and the unique solution mod

1

is the single class containing all integers. It's the vacuous base case.

What happens if

a_{1} = a_{2} = \dots = a_{k} = 0

The unique solution is

x \equiv 0 (mod M)

— that is,

x

is a multiple of

M

. Each constraint just demands divisibility, and coprimality makes divisibility by all of them equal to divisibility by their product.

Can the CRT solution ever be

x = 0

inside

[0, M)

Yes, precisely when every

a_{i} \equiv 0 (mod m_{i})

. Then the smallest non-negative representative is

0

; all other solutions are the positive multiples of

M

What if the constraints force

x

larger than

M

They can't in the range sense — the representative is always taken in

[0, M)

. Any larger valid

x

is that representative plus a multiple of

M

, so "larger than

M

" just means a different member of the same class.

If moduli are coprime but you mistakenly use

lcm

instead of the product, what happens?

Nothing goes wrong — for coprime numbers

lcm (m_{i})

equals the product

M

. The two formulas coincide exactly here; they diverge only when moduli share factors.

Recall Quick self-test

The single fact that decides whether basic CRT applies ::: Whether the moduli are pairwise coprime ( $g cd (m_{i}, m_{j}) = 1$ for every pair). The modulus over which the CRT solution is unique ::: $M = \prod m_{i}$ , the product of all the moduli. The one true "division" in modular arithmetic ::: multiplication by a modular inverse, which exists exactly when the number is coprime to the modulus. For non-coprime $m_{1}, m_{2}$ the solution (if any) is unique modulo ::: $lcm (m_{1}, m_{2}) = m_{1} m_{2} / g cd (m_{1}, m_{2})$ .