Two Congruences with Coprime Moduli? That's a CRT Signal

Most of the trouble people have with competition number theory is not the arithmetic. It is that they stare at a problem for thirty seconds before realising which theorem it belongs to. Once you name the theorem, the rest is mechanical. This short article teaches you one of the most useful recognition reflexes in modular arithmetic: see two or more congruences, check the moduli are coprime, reach for the Chinese Remainder Theorem.

That single pattern unlocks a surprising number of problems — from exam-style remainder puzzles to the internal workings of RSA decryption. Getting the signal into your head costs ten minutes. Not having it can cost you an hour of doomed trial and error.

The signal, in one line

You are looking at a problem. Somewhere in it, you can write down two (or more) conditions of the shape

x \equiv a \pmod m, \qquad x \equiv b \pmod n.

The moduli m and n are coprime — meaning \gcd(m, n) = 1. That is the signal. The Chinese Remainder Theorem guarantees a unique x modulo mn that satisfies both conditions simultaneously. You do not need to pray that a solution exists. You do not need to wonder whether there are many or few. CRT answers both in the same breath: one solution, mod the product.

The "unique mod the product" part is the piece beginners miss. If somebody asks you to find x, the answer is not a single number — it is a residue class. For example, if the unique solution mod 15 is x = 8, then 8, 23, 38, 53, \ldots are all valid answers, and x \equiv 8 \pmod{15} captures them all.

The smallest example worth memorising

Solve

x \equiv 2 \pmod 3, \qquad x \equiv 3 \pmod 5.

\gcd(3, 5) = 1, so CRT fires. Unique solution mod 15.

Find it by scanning the first list: x \equiv 2 \pmod 3 gives \{2, 5, 8, 11, 14, \ldots\}. Check which is \equiv 3 \pmod 5: 8 \bmod 5 = 3. Done. x \equiv 8 \pmod{15}.

You should carry this example in your head the way a cricketer carries the dimensions of a pitch. Whenever you see "two congruences, coprime moduli," think "like 3 and 5 giving 15." The concrete template is what makes recognition fast.

The recognition flowchart

Two conditions, coprime moduli — and you are on the CRT rail. The uniqueness guarantee means the answer exists and is determined, which is usually the hardest step of the problem taken care of for free.

What the signal looks like in disguise

Competition problems rarely hand you x \equiv a \pmod m in that neat form. The signal often arrives in natural-language dressing. Train yourself to translate the following phrases:

"A number leaves remainder 2 when divided by 3 and remainder 3 when divided by 5." Immediate CRT: \gcd(3, 5) = 1.
"Find an integer that is 1 more than a multiple of 4 and 2 more than a multiple of 7." Rewrite as x \equiv 1 \pmod 4, x \equiv 2 \pmod 7. \gcd(4, 7) = 1. CRT.
"A general arranges his soldiers in rows of 5, 7, 11 and is short by 1, 2, 3 respectively." Three coprime moduli. Bigger CRT.
"Find the smallest positive integer divisible by neither 2 nor 3 that is \ldots" — this is not a CRT signal; it is a divisibility condition, not a congruence. Keep your pattern-matcher calibrated.

Recognise the signal by shape, not by words: anywhere a problem describes the value of x through its remainders against several different moduli, you are in CRT territory.

Worked example: troop count puzzle

A general tells you his army has an unknown size $x$, and

when arranged in pairs, one soldier is left over (x \equiv 1 \pmod 2);
when arranged in rows of 3, two are left over (x \equiv 2 \pmod 3);
when arranged in rows of 5, three are left over (x \equiv 3 \pmod 5).

Find the smallest possible army size.

Step 1 — recognise the signal. Three congruences; moduli 2, 3, 5. Pairwise gcds are all 1. CRT applies. The unique solution lives mod 2 \cdot 3 \cdot 5 = 30.

Step 2 — collapse two at a time. Combine the first two: x \equiv 1 \pmod 2 and x \equiv 2 \pmod 3. Scan: x \in \{1, 3, 5, 7, 9, \ldots\} from the odd condition; first one that is \equiv 2 \pmod 3 is 5. So x \equiv 5 \pmod 6.

Step 3 — bring in the third. Combine x \equiv 5 \pmod 6 and x \equiv 3 \pmod 5. Scan: \{5, 11, 17, 23, 29, \ldots\}; check each mod 5: 5 \bmod 5 = 0, 11 \bmod 5 = 1, 17 \bmod 5 = 2, 23 \bmod 5 = 3. Match. So x \equiv 23 \pmod{30}.

Answer. The smallest possible army is 23 soldiers. The next possibility is 53, then 83, and so on.

Why the answer is "23 mod 30" and not just "23": the theorem promised uniqueness modulo 30. 23 is the smallest positive representative, but 53, 83, 113, \ldots are equally valid — a real general would probably pick the one that matches the rough head count he already has.

What if the moduli are not coprime?

The CRT signal requires pairwise coprime moduli. When the moduli share a factor, two things can happen — and you have to check which:

The conditions contradict each other on the shared factor. Then no solution exists. Example: x \equiv 1 \pmod 6 and x \equiv 2 \pmod 4. Since \gcd(6, 4) = 2, both conditions impose a parity demand. The first says x is odd; the second says x is even. Contradiction. No solution.
The conditions agree on the shared factor. Then a solution exists, and it is unique modulo the lcm, not the product. Example: x \equiv 2 \pmod 6 and x \equiv 4 \pmod{10}. Both say x is even and x \equiv 2 \pmod 2, consistent. The solution lives mod \operatorname{lcm}(6, 10) = 30. Scanning: \{2, 8, 14, 20, 26, \ldots\} from the first condition; check mod 10: 14 \bmod 10 = 4. So x \equiv 14 \pmod{30}.

That is the full shape of the signal: coprime moduli → CRT; shared factor → check consistency and reduce to lcm. Most problems that are designed to reward CRT keep the moduli coprime on purpose so the full machinery works. If you spot a non-coprime pair, the problem is usually trying to catch you out — and the extra consistency check is the point of the question.

The signal summarised

See two or more congruences. Check the gcd of the moduli. If the gcd is 1, apply CRT: the answer is unique modulo the product. That is the reflex. Everything else — the construction by scanning, the Bezout formula, the generalisation to k moduli — follows once you have made the recognition.