Difference between revisions 573662338 and 573762446 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]].

The method of successive substitution is also known as '''''back substitution.'''''

== Examples ==

==='''Example One'''===
Consider the simple set of simultaneous congruences
: ''x'' ≡ 3 (mod 4)
: ''x'' ≡ 5 (mod 6)

Now, for ''x'' ≡ 3 (mod 4) to be true, ''x'' = 3 + 4''j'' for some integer ''j''. Substitute this in the second equation
: 3+4''j'' ≡ 5 (mod 6)
since we are looking for a solution to ''both'' equations.
(contracted; show full)Expand:
: ''x'' = 11 + 12''k''
to obtain the solution

''x'' ≡ 11 (mod 12)

===Example 2 (An Easier Method)===
Although the method utilized in the preceding example is coherent, it is superfluous, unnecessary, and arbitrary, since it does not work for every problem.
  

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)'''
* '''x = 2a + 1 ≡ 2 (mod 3)'''
(contracted; show full)

8. Our final step is to substitute '''c''' into the '''equation with respect to x '''that we found in '''step 6:'''
* '''x = 30c + 23 '''
* '''= 30(11d + 10) + 23'''
* '''= 330d + 323.'''
'''∴ 330d + 323 '''represents all solutions that satisfies the system of congruences that we began with.

=====
'''Checking Our Work'''=====
To check that our answer is correct, we deduce whether each respective residue is conceived when we compute 223 by the modulo of each congruence:

323 ≡ '''1''' (mod 2)
* 323 = 161 * 2''' '''+ '''1'''
323 ≡ '''2''' (mod 3)
* 323 = 107 * 3 + '''2'''
323 ≡ '''3''' (mod 5)
* 323 = 64 * 5 + '''3'''
323 ≡ '''4 '''(mod 11)
* 323 = 29 * 11 + '''4'''
An alternative method would be to deduce whether each modulus divides the difference of 323 and each congruence's respective residue:

2 | (323 - 1) is true.

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.

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

[[Category:Modular arithmetic]]⏎
⏎
http://en.wikibooks.org/wiki/Discrete_Mathematics/Modular_arithmetic⏎
⏎
[[Category:Modular arithmetic]]
[[Category:Back Substitution]]
[[Category:Modular Arithmetic]]
[[Category:Modular Congruences]]