Method of successive substitution
The
method of successive substitution, in
mathematics, 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 ≡ 11 (mod 12)
Now, for
x ≡ 3 (mod 4) to be true,
x=3+4
j for some integer
j. Substitute this in the second equation
- 3+4j ≡ 11 (mod 12)
since we are looking for a solution to
both equations.
Subtract 3 from both sides (this is permitted in modular arithmetic)
- 4j ≡ 11 (mod 12)
We need to find the
multiplicative inverse of 4 mod 12, which we can find as 4. Multiply throughout to get
- j ≡ 44 (mod 12)
- j ≡ 8 (mod 12)
For the above to be true,
j=8+12
k for some integer
k. Now substitute back into 3+4
j and we obtain
- x=3+4(8+12k)
Expand out
- x=35+48k
to obtain the solution
- x≡ 35 (mod 48)
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