Revision 76560704 of "Method of successive substitution" on enwiki

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.[http://infohost.nmt.edu/~weinkauf/es111/ES%20111%20roots.htm]

== 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 + 4''j'' for some integer ''j''. Substitute this in the second equation
: 3+4''j'' ≡ 5 (mod 6)
since we are looking for a solution to ''both'' equations.

Subtract 3 from both sides (this is permitted in modular arithmetic)
: 4''j'' ≡ 2 (mod 6)
We simplify by dividing by the [[greatest common divisor]] of 4,2 and 6. Division by 2 yields:
: 2''j'' ≡ 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 + 3''k'' for some integer ''k''. Now substitute back into 3 + 4''j'' and we obtain
: ''x'' = 3 + 4(2 + 3''k'')
Expand:
: ''x'' = 11 + 12''k''
to obtain the solution
: ''x'' ≡ 11 (mod 12)

== General algorithm ==

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.

== See also ==
* [[simultaneous equations]]

[[Category:Modular arithmetic]]

[[fr:Méthode des substitutions successives]]