In modular arithmetic

Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....

, 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

Chinese remainder theorem

The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...

 are not satisfied.

There is also an unrelated method of successive substitution, a randomized algorithm

Randomized algorithm

A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...

 used for root finding, not currently discussed here.http://infohost.nmt.edu/~weinkauf/es111/ES%20111%20roots.htm

Example

For example, 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 + 4j for some integer j. Substitute this in the second equation

3+4j ≡ 5 (mod 6)

since we are looking for a solution to both equations.

Subtract 3 from both sides (this is permitted in modular arithmetic)

4j ≡ 2 (mod 6)

We simplify by dividing by the greatest common divisor

Greatest common divisor

In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...

 of 4,2 and 6. Division by 2 yields:

2j ≡ 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 + 3k for some integer k. Now substitute back into 3 + 4j and we obtain

x = 3 + 4(2 + 3k)

Expand:

x = 11 + 12k

to obtain the solution

x ≡ 11 (mod 12)

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

Coprime

In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...

, the Chinese remainder theorem

Chinese remainder theorem

The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...

gives a straightforward formula to obtain the solution.