What shortcut applies when two congruences in a CRT system have the same remainder?

Conditions

• The two congruences have the identical remainder r.
• The moduli m and n are positive integers.

Reasoning, step by step

1. Identify two congruences with the same remainder r.
2. Set the particular solution $x_0 = r$.
3. Compute the LCM of the two moduli m and n.
4. Write the combined solution progression as r, r + LCM(m,n), $r + 2$*LCM(m,n), ...

Example

The video reorders the system to place x ≡ 1 (mod 4) and x ≡ 1 (mod 5) together. It states, 'With x ≡ 1 (mod 4) and x ≡ 1 (mod 5) together, the common solution is immediate: $x=1$ works for both. The combined solution set is then 1 plus multiples of LCM(4,5)... 1, 21, 41, ...'

Common misconceptions

• Assuming the solution must be found by scanning a sequence from scratch.
• Forgetting that reordering congruences is allowed and can reveal these shortcuts.

Watch the explanation

Explore next

• Why is reordering congruences allowed in a CRT system?
• How do you compute LCM(4,5) quickly?
• What is the next step after combining the first two congruences?