Difference between revisions 598779857 and 600429830 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)

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:
** '''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)'''
(contracted; show full)* 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 prece
eding step:
* '''x ≡ 3 (mod 5)'''
* '''x = 5a + 3, ∀a ∈ Z'''
* '''3a + 2 = 5a + 3'''
* '''-1  = 2a'''
This is where the method used in example 2 appears to have troubles, but I found a solution: Add whatever the current modulus is to the side of the equation where the variable is not, until the coefficient is able to divide it. The reason why we can do this is because of the definition of a [[Congruence class#Congruence class|congruence class]] Thus,

3. Add 5, which is our modulus, to -1, to obtain:
* '''-1 + 5 = 4'''
* '''4  = 2a'''
* '''a = 2.'''
4. Rewrite '''a = 2''' as its equivalent modular equation
* '''a = 2 becomes a = 5b + 2, ∀b ∈ Z.'''
5. Substitute our current '''a''' into the equation procured in '''step 1 '''with respect to x:
* '''x = 3a + 2 = 3 (5b + 2) + 2 = 15b + 8.'''
* '''∴ x = 15b + 8.'''
6. Finally, rewrite the third congruence, and set it equal to the equation incurred in the preceeding step, solving for '''b.'''
* '''x ≡ 2 (mod 7) '''can be rewritten''' as x = 7b + 2'''
Substituting for x, we have
* '''15b + 8 = 7b + 2'''
* '''8b = -6'''
Add our current modulus, which is 7, to -6, until a multiple of 8 is conceived:
* '''-6 + 7 = 1 + 7 = 8.'''
Thus,
(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]]