How does the remainder sequence trick avoid calculating large numbers when solving a congruence in the Chinese Remainder Theorem?
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).
Reasoning, step by step
- Take the current starting solution modulo the new target modulus m.
- Take the current step size modulo the new target modulus m.
- Generate a sequence of remainders by repeatedly adding the step size's remainder modulo m.
- Count how many additions are needed to reach the target remainder r.
- Multiply the step size by this count and add it to the starting solution to get the new particular solution.
Example
To satisfy x ≡ 3 (mod 7) with a starting solution of 21 and step size 60, the video computes 21 mod and 60 mod . It generates the remainder sequence 0, 4, 1, 5, 2, 6, 3. Reaching 3 takes 6 steps, so the solution is .
Common misconceptions
- Calculating the actual large numbers in the progression (e.g., 21, 81, 141...) and checking their remainders manually.
- Forgetting to take the modulo at each step of the remainder sequence.
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.
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).
Answers are generated from source material and independently checked. Consult the original video or creator if something is unclear.