Difference between revisions 574569600 and 578544860 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)* 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:
** '''a (mod b) ⇔ b''k'' + a,  ∀k ∈ Z , ''where k is an arbitrary constant.'''''


====PROCEDURE====

1. Begin by rewriting the first congruence as an equation:
* '''x = 2a + 1, ∀a ∈ Z '''
2. Rewrite the second congruence as an equation, and set the equation found in the first step equal to this equation, since '''x '''will substitute the x in the second congruence:
* '''x ≡ 2 (mod 3)'''
* '''x = 2a + 1 ≡ 2 (mod 3)'''
* '''2a + 1 = 3a + 2   ''(Rewrite the second congruence in terms of its modulus)'''''
* '''a = -1.'''
Because '''a '''must be a [https://en.wikipedia.org/wiki/Modular_multiplicative_inverse positive nonnegative inverse], we need a positive '''a'''. '''''Thus, we add whatever our current modulus is to a, which is a = -1 + 3 = 2'''''.

3. We now rewrite '''a = 2 '''in terms of our current modulus:
* '''a = 2 (mod 3)'''
* '''∴ a = 3b + 2 '''
(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]]