How does the iterative CRT method find the smallest solution to the system x ≡ 3 (mod 4), x ≡ 5 (mod 6), x ≡ 2 (mod 5)?
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).
Reasoning, step by step
- Start with the sequence of numbers satisfying x ≡ 3 (mod 4): 3, 7, 11, ...
- Test these candidates against the second congruence x ≡ 5 (mod 6). The first match is 11.
- Update the step size to the LCM of the first two moduli: LCM(4, 6) = 12.
- Generate the new sequence of simultaneous solutions: 11, 23, 35, 47, ...
- Test this new sequence against the third congruence x ≡ 2 (mod 5).
- The first term that satisfies the third congruence is 47, which is the smallest solution to the full system.
Example
The video explicitly walks through this: 'To satisfy the first requirement, we can take 3 or 7, 11, 15, and so on.' It then checks 11 against mod 6, updates the step to 12, and checks 11, 23, 35, and 47 against mod 5, concluding '47 modulo 5 is 2 indeed. So it is the smallest solution for our system of three congruences.'
Common misconceptions
- Assuming the first number that satisfies the second congruence is the final answer, forgetting to check the third.
- Thinking the step size remains 4 after satisfying the second congruence, rather than updating to the LCM of 4 and 6.
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.
The step size updates to the least common multiple (LCM) of the moduli already satisfied because adding the LCM to a current solution preserves the remainders for all those moduli. Any increment divisible by all the current moduli will not change the remainder modulo any of them, and the LCM is the smallest positive such increment.
Conditions: A number currently satisfies a set of congruences.; The new step size must preserve the remainders for all those congruences.
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.
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.