Difference between revisions 574151016 and 574569600 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)The key to solving for the variable is to add the current modulus to the other side of the equation, until a multiple of the coefficient of the variable that is being solved for

is procured. Here is an example:
* x ≡ 2 (mod 3)
* x ≡ 3 (mod 5)
* x ≡ 2 (mod 7)

====
=PROCEDURE=====⏎
⏎

1. Rewrite the first linear congruence to its equivalent equation:
* '''x ≡ 2 (mod 3)'''
* '''x = 3a + 2, ∀a ∈ Z.'''
2. Rewrite the second congruence as an equation, and set the expression equal to the expression found in the preceeding step:
* '''x ≡ 3 (mod 5)'''
* '''x = 5a + 3, ∀a ∈ Z'''
* '''3a + 2 = 5a + 3'''
(contracted; show full)* [[simultaneous equations]]

http://en.wikibooks.org/wiki/Discrete_Mathematics/Modular_arithmetic

[[Category:Modular arithmetic]]
[[Category:Back Substitution]]
[[Category:Modular Arithmetic]]
[[Category:Modular Congruences]]