Why does the step size in the iterative CRT method update to the LCM of the combined moduli?
Conditions
- A number currently satisfies a set of congruences.
- The new step size must preserve the remainders for all those congruences.
Reasoning, step by step
- Identify the moduli of the congruences currently satisfied.
- Compute the least common multiple (LCM) of these moduli.
- Add the LCM to the current solution to generate the next candidate.
- Observe that because the LCM is divisible by each modulus, the remainder modulo each modulus remains unchanged.
Example
In the video, after finding 11 satisfies x ≡ 3 (mod 4) and x ≡ 5 (mod 6), the speaker says, 'You can increase it by something divisible by all moduli so far, 4 and 6. Least common multiple, LCM, of that is 12, and if you add to something 12, you don't change remainders modulo 6 and 4, because 12 is divisible by 6 and 4.'
Common misconceptions
- Thinking that any number added to a solution will preserve the remainders.
- Assuming the step size should be the product of the moduli, which can skip valid solutions if the moduli are not coprime.
Watch the explanation
Connected concepts
Explore next
Related questions
Because the step size and the modulus m are coprime, the sequence of remainders generated by adding the step size modulo m forms a complete cycle of length m. If the target remainder does not appear within the first m steps, it will never appear, meaning no solution exists for that specific congruence within the progression.
Conditions: The step size of the current arithmetic progression is coprime to the target modulus m.; The search is bounded by the modulus m.
If two congruences x ≡ r (mod m) and x ≡ r (mod n) share the same remainder r, then is an immediate particular solution. The full combined solution set is then r plus multiples of the LCM of the two moduli: * LCM(m, n).
Conditions: The two congruences have the identical remainder r.; The moduli m and n are positive integers.
The method solves the congruences one by one by maintaining an arithmetic progression of candidate solutions. It starts with the sequence of numbers satisfying the first congruence, tests them against the second to find a common solution, and then updates the step size to the least common multiple (LCM) of the first two moduli.
Conditions: The unknown x is an integer.; The system consists of the congruences x ≡ 3 (mod 4), x ≡ 5 (mod 6), and x ≡ 2 (mod 5).
Instead of computing large terms in the arithmetic progression, the trick computes the sequence of remainders modulo the new target modulus. It starts with the current solution's remainder and repeatedly adds the step size's remainder modulo the target, stopping when the target remainder is reached.
Conditions: You have an arithmetic progression of candidates satisfying previous congruences.; You need to find the first term satisfying a new congruence x ≡ r (mod m).
Answers are generated from source material and independently checked. Consult the original video or creator if something is unclear.