Difference between revisions 578544860 and 587741048 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.'''''

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)
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.

===Example 3 (Similar Method Utilized Above but with a Twist)===
When solving a system of linear congruences using the method utilized in the above example, there will be situations where solving for a variable will produce a rational.

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'''
* '''-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 [https://en.wikipedia.org/wiki/[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.'''
(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]]