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.
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)
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)
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]
Adding the equations, we have:
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·m1m2mod (m3·m1m2)
[3.8]
Adding these gives:
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]
When n=n+1, we add equation:
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...·mnmod (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
[1.1]
[1.2]
[1.3]
[1.4]
[1.5]