Method of successive substitution
|
|
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.
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 be 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 out
- x=11+12k
to obtain the solution
- x ≡ 11 (mod 12)
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.