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 modular 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:

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 modular 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.