Difference between revisions 574090075 and 574151016 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)

===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'''
(contracted; show full)
23 ≡ '''2 '''(mod 3)
* 23 = 7 * 3 + '''2'''
23 ≡ '''3''' (mod 5)
* 23 = 4 * 5 + '''3'''
23 ≡ '''2 '''(mod 7)
* 23 = 3 * 7 + '''2'''

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

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

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