Difference between revisions 573275608 and 573275899 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 numerical-analysis method of successive substitution, a [[randomized algorithm]] used for [[root finding]], an application of [[fixed-point iteration]].

(contracted; show full)323 ''≡ '''''4 '''(mod 11)

323 = 29 * 11 + '''11.'''

Because diving 323 by each modulus renders each system's respective residue, we are finished.

The alternative method for solving this system is using the [[Chinese remainder theorem|Chinese Remainder Theorem]].

: ⏎
== 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.

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

[[Category:Modular arithmetic]]

http://en.wikibooks.org/wiki/Discrete_Mathematics/Modular_arithmetic
[[Category:Back Substitution]]
[[Category:Modular Arithmetic]]
[[Category:Modular Congruences]]