Difference between revisions 543738541 and 573275608 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.'''''⏎
⏎
== Example ==

For e'''Example, c 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.

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]] 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'' = 2 + 3''k'' for some integer ''k''. Now substitute back into 3 + 4''j'' and we obtain
: ''x'' = 3 + 4(2 + 3''k'')
Expand:
: ''x'' = 11 + 12''k''
to obtain the solution
: ''x'' ≡ 11 (mod 12)⏎
⏎
''x'' ≡ 11 (mod 12)

'''Example Two (''An Easier Method)'''''

Although the above method is correct, some of the steps are arbitrary and superfluous. If we had a problem that had these fourcongruences

x ≡ 1 (mod 2)

x ≡ 2 (mod 3)

x ≡ 3 (mod 5)

x ≡ 4 (mod 11),

the above method would prove to be inefficient. 

The only equality identity that we need is a ≡ b (mod m) is equivalent to a = m'''''k''''' + b, for every '''''k''''' belonging to the '''''set of integers'''''. 

'''PROCEDURE'''

1. Begin by rewriting the first congruence as '''''x = 2a + 1''''', where ''a belongs to the set of integers''.

2. Substitute the expression '''''2a + 1''''' for x in the next congruence to have '''''2a + 1 ≡ 2(mod 3)'''''.

3. Rewrite 2(mod 3) as '''''3a + 2 '''''and solve for a:

'''''2a + 1 = 3a + 2'''''

'''''=''''' '''''a = -1.'''''

4. '''''a = -1''''', but we cannot have a negative, because we need a [[Modular multiplicative inverse|positive nonnegative integer]] to be our inverse. Thus, we can add whatever our current modulus is to our '''a''' to obtain our new '''a'''. Adding 3 to -1 gives, '''''a = 2.'''''

5. Now we write '''''a = 2 ''''' in terms of our current modulus, which is 3, to obtain 

'''''a = 3b + 2, for every b belonging to the set of integers.'''''

6. We thus substitute our new equation for '''''a''''' into the equation that we wrote in '''''step 1 '''''for '''''x = 2a + 1:'''''

'''''x = 2a + 1'''''

'''''= 2(3b + 2) + 1 = 6b + 5 = x '''''

'''''x = 6b + 5.'''''

7. With our new equation with respect to x, we thus proceed with the third congruence:

'''''x ≡ 3 (mod 5)'''''

'''''6b + 5 ≡ 3(mod 5)'''''

'''''6b + 5 = 5b + 3'''''

'''''b = -2, which we add our current modulus to it, since we cannot have negatives: '''''

'''''b = -2 + 5 = 3.'''''

Rewriting '''''b = 3 '''''in terms of our current modulus, we therefore, conceive a new equation:

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

8. With our new equation, we substitute '''''b '''''into the equation produced in '''''step 6 '''''to incur a new equation:

'''''x = 6b + 5 = 6(5c + 3) + 5 = 30c + 18 + 5 = 30c+ 23'''''

'''''x = 30c + 23.'''''

9. With our new equation '''''x = 30c + 23''''', we proceed with our final congruence:

'''''x ≡ 4 (mod 11)'''''

'''''30c + 23 = 11c + 4  '''(substituted our new eqtn. of x and rewrote the congruence; see steps 3 and 7 for similarities)''

'''''c = -1.'''''

Since we cannot have a negative, we add our current modulus value to it, '''''c = -1 + 11 = 10.'''''

Therefore, our new equation with respect to c and in terms of our current modulus is  

'''''c = 11d + 10.'''''

10. We now substitute our new expression for c into the equation we procured in '''''step 8:'''''

'''''x = 30c + 23 = 30(11d + 10) + 23 = 330d + 323'''''

'''''x = 330d + 323.'''''

The expression '''''330d + 323 '''''represents the linear combination '''''for all solutions '''''to the four system of congruences with which we began. To check that the expression we have found is correct, see if modding 323 for each congruence will produce each system's respective [https://en.wikipedia.org/wiki/Modular_arithmetic#Residue_systems residue]. 

'''CHECK'''

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 + '''11.'''

Because diving 323 by each modulus renders each system's respective residue, we are finished.

The alternative method for solving this system is using the [[Chinese remainder theorem|Chinese Remainder Theorem]].
: 
== 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:Back Substitution]]
[[Category:Modular Arithmetic]]
[[Category:Modular Congruences]]