Difference between revisions 573545227 and 573662338 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)Expand:
: ''x'' = 11 + 12''k''
to obtain the solution

''x'' ≡ 11 (mod 12)

===Example 2 (An Easier Method)===
Although the 
above method utilized in the preceding example is coherent, it is superfluous, unnecessary, and arbitrary, since it does not work for every problem. 

Consider these four systems of congruences:
* x ≡ 1 (mod 2)
* x ≡ 2 (mod 3)
* x ≡ 3 (mod 5)
* x ≡ 4 (mod 11)
In order to proceed in finding an expression that represents all the solutions that satisfies this system of linear congruences, it is important to know that '''a (mod b)''' has an analogous identity:
(contracted; show full)3 | (323 - 2) is true.

5 | (323 - 3) is true.

11 | (323 - 4) is true.

Another way to solve the system of linear congruences is to use the [https://en.wikipedia.org/wiki/Chinese_remainder_theorem Chinese Remainder Theorem], and it will give us the same result.

⏎
⏎
===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]]