Main Page | See live article | Alphabetical index

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+4j 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+12k for some integer k. Now substitute back into 3+4j and we obtain
x=3+4(8+12k)
Expand out
x=35+48k
to obtain the solution
x≡ 35 (mod 48)

In general: