  # Ken Ward's Mathematics Pages

## Number Theory Chinese Remainder Theorem Formula 1

Number Theory Contents

## Formula

The following formula can be used to solve a set of congruence equations (or, the same thing, a set of Linear Diophantine Equations)
For instance the set: [1.1]
Or equivalently, the following [1.2]
We note that the m's are not required to be relatively prime.

We define: [1.3]
And the formula is: [1.4]
Usually written in preparation for the solution: [1.5]

Where n is a solution, mod M, if d= gcd (M1+M2+... +Mn, M) divides (M1r1+M2r2+... +Mnrn). This is basically saying that there is a solution if we can divide by M1+M2+... +Mn, in modular arithmetic. If d does not divide M1+M2+... +Mn, there isn't a solution to the set of equations at all. This means that some of the equations are contradictory. The set of equations are always solvable when the m's are relatively prime, because then d=1, and 1 divides any number.

If m1, m2, ... , mn are relatively prime, then the solution is unique modulo M, and n is the solution, modulo M. Otherwise, (if the equations have a solution, according to the condition above) n is the unique solution modulo M/d. M/d is the lowest common factor of m1, m2, ... mn.

### Example of Unsolvable (Illogical) Equations

a1=1 (mod 2)
a2=2 (mod 3)
a3=4 (mod 6)
Here M=36
 k mk rk Mk Mkrk 1 2 1 18 18 2 3 2 12 24 3 6 4 6 24 Σ= 36 66

gcd(36,36)=36, which does not evenly divide 66, so there is no solution.

The equations are illogical because there is no integer which divided by 2 leaves a remainder 1, and when divided by 6 gives a remainder 4.

### Example of Simple Solvable Equations 1

a1=1 (mod 2)
a2=2 (mod 3)
a3=5 (mod 6)
a4=5 (mod 7)
Here M=252
 k mk rk Mk Mkrk 1 2 1 126 126 2 3 2 84 168 3 6 5 42 210 4 7 5 36 180 M=252 ΣMk=288 ΣMkrk=684

gcd(288,684)=4, which divides the Mkrk's, so the set is solvable:

n≡684/288 mod (252)
It is often convenient to write this as:
288n≡684 mod (252)
Dividing by 4:
72n≡171 mod (63)
Casting out 63's:
9n≡45 mod (63)
Dividing by 9:
n≡5 mod (7)
The smallest number, that suits the problem, is therefore 5 modulo 42. The next solution is 5+42=47.

### Example of Simple Solvable Equations 2

a1=1 (mod 2)
a2=2 (mod 3)
a3=4 (mod 5)
Here M=30
 k mk rk Mk Mkrk 1 2 1 15 15 2 3 2 10 20 3 5 4 6 24 M=30 ΣMk=31 ΣMkrk=59

gcd(31,30)=1, which divides the Mkrk's, so the set is solvable. (This is always true when the m's are relatively prime).
31·n≡59 (mod 30)
Casting out 30's:
n≡29 (mod 30)

The required number is therefore 29.

### Example Using Euclid

a1=1 (mod 2)
a2=2 (mod 3)
a3=3 (mod 4)
a3=4 (mod 5)
Here M=120
 k mk rk Mk Mkrk 1 2 1 60 60 2 3 2 40 80 3 4 3 30 90 4 5 2 24 48 M=120 ΣMk=154 ΣMkrk=278

gcd(120,154)=4, which divides the Mkrk's, so the set is solvable.
154n≡278 (mod 120)
Casting out 120's:
34n≡38 (mod 120)
Dividing by 2:
17n≡19 (mod 60)

As the answer isn't obvious, we use Euclid's Extended Algorithm, to solve:
17n−60l=1,
And then multiply the answer by 19, as when solving congruence equations.
 k lk xk rk qk 1 1 0 60 2 0 1 17 3 3 1 -3 9 1 4 -1 4 8 1 5 2 -7 1

So x0≡−7 (mod 60)
x≡(−7)·19=−133 (mod 60)
x≡47 (mod 60)

The solution to the equations is therefore 47

## Proof of Formula

To prove the formula, we shall first deal with the case of 3 equations, producing a single equation which satisfies them, and then introduce some definitions. We shall then go on to prove the formula by induction.

We first seek to solve the equations:
N≡r1 mod (m1)           [3.1]
N≡r2 mod (m2)           [3.2]
N≡r3 mod (m3)           [3.3]
First we deal with the first two, by multiplying Equation 3.1 by m2 and Equation 3.2 by m1 (to give them the same modulus, and so we can add them):
N·m2≡r1·m2 mod (m1·m2)           [3.4]
N·m1≡r2·m1 mod (m1·m2)           [3.5]
N·(m2+m1)≡r1·m2+r2·m1 (mod m1·m2)   [3.6]
The equation 3.6 above satisfies both equations 3.1 and 3.2

We can add Equation 3.3 to this equation by converting both to modulo m1·m2·m3 by multiplying 3.6 by m3 and 3.3 by m1m2
N·(m2·m3+m1·m3)≡r1·m2·m3+r2·m1·m3 (mod m1·m2·m3)   [3.7]
N·m1m2≡r3·m1m2 mod (m3·m1m2)                               [3.8]

N·(m2·m3+m1·m3+m1m2)≡r1·m2·m3+r2·m1·m3 +r3·m1m2(mod m1·m2·m3) [3.9]

### Definitions

Let M=m1·m2·m3, that is the product of all the divisors.
Let M1=M/m1, M2=M/m2, M3=M/m3, that is the product of all the m's except the one with the same index as the M

We can therefore write equation 3.9 as:

N·(M1+M2+M3)≡r1·M1+r2·M2 +r3·M3  (mod M) [3.10]

### Proof by Induction

We seek to solve the n equations:
N≡r1 mod (m1)
N≡r2 mod (m2)
…
N≡rn mod (mn)     [3.A]
Let us generalise 3.10 for n equations, so:
M=m1·m2...·mn
M1=M/m1, M2=M/m2, ... Mn=M/mn

So Equation 3.10 is in general for n equations:

N·(M1+M2+...+Mn)≡r1·M1+r2·M2 +...+rn·Mn  (mod M)                  [3.11]

For the case when N=1, we have:
M=m1
M1=M/m1=m1/m1=1
And from 3.11:
N≡r1  (mod M)

Which is our first equation of 3.A

When n=n, then we use the formula 3.11:
N·(M1+M2+...+Mn)≡r1·M1+r2·M2 +...+rn·Mn  (mod M)                  [3.11, repeated]

N≡rn+1 mod (mn+1)    [3.12]
To the list.

To add this equation to 3.11, we multiply 3.11 by mn+1, and 3.12 by m1·m2...·mn and we get:
N·m1·m2...·mn≡rn+1·m1·m2...·mn mod (mn+1·m1·m2...·mn)    [3.13]
and
N·(M1·mn+1+M2·mn+1+...+Mn·mn+1)≡r1·M1·mn+1+r2·M2·mn+1 +...+rn·Mn·mn+1  (mod M·mn+1) [3.14]

Now we can add 3.13 and 3.14 because they have the same modulus:
N·(M1·mn+1+M2·mn+1+...+Mn·mn+1 +N·m1·m2...·mn)≡r1·M1·mn+1+r2·M2·mn+1 +...+rn·Mn·mn+1+rn+1·m1·m2...·mn  (mod M·mn+1) [3.15]
Now we note that the new M=M·mn+1, and each of the new Mi, for i=1... n are Mi·mn+1, and Mn+1=m1·m2...·mn
Therefore 3.15 can be written:
N·(M1+M2+...+Mn+Mn+1)≡r1·M1+r2·M2+...+rn·Mn+rn+1·Mn+1  (mod M) [3.16]
Which is what our equation would predict.
Therefore, if the formula is correct for n=any natural number, then it is true for n+1. It is true for n=1, so it is true for n=2. In which case, it is true for n=3, and so on for all natural numbers.

### Validity

We can compute the value of N when we can divide Equation 3.16 by (M1+M2+...+Mn+Mn+1), according to the rules of modular arithmetic. That is, when d=gcd(M1+M2+...+Mn+Mn+1,M)=1, we can always divide, but when d>1, then we can divide only when d divides r1·M1+r2·M2+...+rn·Mn+rn+1·Mn+1

Number Theory Contents

Ken Ward's Mathematics Pages

# Faster Arithmetic - by Ken Ward

Ken's book is packed with examples and explanations that enable you to discover more than 150 techniques to speed up your arithmetic and increase your understanding of numbers. Paperback and Kindle: 