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)

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.

Method Of Successive Substitution

See also