Difference between revisions 16244180 and 18226645 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.

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 be 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+ = 2 + 3''k'' for some integer ''k''. Now substitute back into 3+ + 4''j'' and we obtain
: ''x''=3+4(2+ = 3 + 4(2 + 3''k'')
Expand out:
: ''x''=11+ = 11 + 12''k''
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.

== See also ==
* [[simultaneous equations]]
[[Category:Modular arithmetic]]