Method of successive substitution
From Wikipedia, the free encyclopedia
In modular arithmetic, the method of successive substitution is a method of solving problems of simultaneous congruences by using the definition of the congruence equation. It is commonly applied in cases where the conditions of the Chinese remainder theorem are not satisfied.
There is also an unrelated method of successive substitution, a randomized algorithm used for root finding, not currently discussed here.[1]
[edit] Example
For example, consider the simple set of simultaneous congruences
- x ≡ 3 (mod 4)
- x ≡ 5 (mod 6)
Now, for x ≡ 3 (mod 4) to be true, x = 3 + 4j for some integer j. Substitute this in the second equation
- 3+4j ≡ 5 (mod 6)
since we are looking for a solution to both equations.
Subtract 3 from both sides (this is permitted in modular arithmetic)
- 4j ≡ 2 (mod 6)
We simplify by dividing by the greatest common divisor of 4,2 and 6. Division by 2 yields:
- 2j ≡ 1 (mod 3)
The Euclidean multiplicative inverse of 2 mod 3 is 2. After multiplying both sides with the inverse, we obtain:
- j ≡ 2 × 1 (mod 3)
or
- j ≡ 2 (mod 3)
For the above to be true: j = 2 + 3k for some integer k. Now substitute back into 3 + 4j and we obtain
- x = 3 + 4(2 + 3k)
Expand:
- x = 11 + 12k
to obtain the solution
- x ≡ 11 (mod 12)
[edit] General algorithm
In general:
- write the first equation in its equivalent form
- substitute it into the next
- simplify, use the multiplicative inverse if necessary
- continue until the last equation
- back substitute, then simplify
- rewrite back in the congruence form
If the moduli are coprime, the Chinese remainder theorem gives a straightforward formula to obtain the solution.
