View source for Method of successive substitution

In [[Modular arithmetic|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|randomized algorithm]] used for root finding, an application of [[Fixed-point iteration|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''&nbsp;=&nbsp;3&nbsp;+&nbsp;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.

Subtract 3 from both sides (this is permitted in modular arithmetic)
: 4''j'' ≡ 2 (mod 6)
We simplify by dividing by the greatest common divisor of 4,2 and 6. Division by 2 yields:
: 2''j'' ≡ 1 (mod 3)
The Euclidean [[Modular multiplicative inverse|modular multiplicative inverse]] of 2 mod 3 is 2. After multiplying both sides with the inverse, 
we obtain:
: ''j'' ≡ 2 × 1 (mod 3)
or
: ''j'' ≡ 2 (mod 3)

For the above to be true: ''j''&nbsp;=&nbsp;2&nbsp;+&nbsp;3''k'' for some integer ''k''. Now substitute back into 3&nbsp;+&nbsp;4''j'' and we obtain
: ''x'' = 3 + 4(2 + 3''k'')
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 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)'''
* '''2a ≡ 1 (mod 3)'''
* '''a ≡ 2<sup>−1</sup> (mod 3)'''
* '''a = -1.'''
Because '''a '''must be a [[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 '''
4. We now substitute our current value of '''a '''into our equation that we found in '''step 1''' with respect to '''x:'''
* '''x = 2a + 1'''
* ''' = 2(3b + 2) + 1, ∀b ∈ Z '''
* '''= 6b + 5.'''
'''∴ x = 6b + 5.'''

5. We now substitute our new value for '''x '''into the x in our third linear congruence, and rewrite '''3 (mod 5) '''to its equivalent expression:
* '''x ≡ 3 (mod 5)'''
* '''=''' '''6b + 5 ≡ 3 (mod 5)'''
* '''=''' '''6b + 5 = 5b + 3'''
* '''= b = -2.'''
Because '''b = -2''', we add our current to modulus to it in order to obtain '''b = 3.'''

'''∴ b = 5c + 3.'''

6. We again substitute our new value for '''b '''into our equation that we found in '''step 4''' with respect to '''x:'''
* '''x = 6b + 5'''
* '''= 6(5c + 3) + 5'''
* '''= 30c + 23'''
'''∴ x = 30c + 23, ∀c ∈ Z '''

7. We now substitute our new value for '''x''' into the x of our final linear congruence, rewriting '''4 (mod 11) '''to its equivalent expression:
* '''x ≡ 4 (mod 11)'''
* '''= 30c + 18 ≡ 4 (mod 11)'''
* '''= 30c + 23 = 11c + 4'''
* '''= 19c = -19'''
* '''= c = -1.'''
Adding our current modulus to the value that '''c''' represents, our new '''c''' '''= 10.'''

'''∴ c = 11d + 10, ∀d ∈ Z.'''

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 with which we began.

====Checking Our Work====

To check that our answer is correct, we deduce whether each respective residue is conceived when we compute 323 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 [[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 preceding 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 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 preceding 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,
* '''8b = 8'''
* '''b = 1.'''
Rewriting b in terms of its modulus, we have
* '''b = 7c + 1, ∀c ∈ Z'''
7. Substitute our new equation '''b '''for b in the equation with respect to x we conceived in '''step 6:'''
* '''x = 15b + 8'''
* '''= 15 (7c + 1) + 8'''
* '''= 105c + 23'''
* '''∴ x = 105c + 23.'''
'''∴ ''105c + 23 represents all solutions that satisfies the system of congruences with which we began.'''''

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

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

==External links==
* [http://maciejkus.com/chinese_remainder/ A method of successive substitution calculator]

[[Category:Modular arithmetic]]

{{Sourceattribution|Method of successive substitution}}