MATHEMATICS & NATURE
Mathematics, Physics, Mechanics & Astronomy
Random Vol. 3 Sn: 202301
https://mathnature.github.io
c
Mathematics & Nature–Free Media of Eternal Truth, China, 2023 https://orcid.org/0000-0002-3644-5170
.
Article
.
Mathematics
Dongfang Brief General Solutions to Congruence Equations
—Dongfang Concise Expression of Chinese Remainder Theorem
X. D. Dongfang
Orient Research Base of Mathematics and Physics,
Wutong Mountain National Forest Park, Shenzhen, China
Abstract: The Chinese remainder theorem gives the general solution of the strongly
constrained linear congruence system of module pairwise coprime, but it can not directly
give the minimum natural number solution of the system of congruence equations. Nor
do es it clarify the necessary and sufficient conditions for the weak constrained linear
congruence equations with different modules to have a solution and the formula of weakly
constrained general solution. Here, the Chinese remainder theorem is promoted, clarifying
the conditional equations for the existence of solutions to weakly constrained systems of
linear congruence equations. The new concise formulas are utilized to express the general
solutions of strongly constrained congruence systems and weakly constrained congruence
systems, thereby improving the theory of system of congruence equations. Then, the
concise steps are provided to directly construct the general solutions of linear strongly
constrained and weakly constrained system of congruence equations, in order to promote
the popularization of congruence equation theory on a wider range. Finally, the question
of whether a universal method for solving the rational number solution of the minimum
number of digits for an indefinite system of equations exists was brought up.
Keywords: Congruence equations, module pairwise coprime, module pairwise not co-
prime, Chinese remainder theorem, elementary algebra
MSC(2020) Subject Classification: 11A07, 11R04
Contents
1 Introduction · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · 2
2 Formulaic description of the Chinese remainder theorem · · · · · · · · · · · · · · · · 2
3 Concise solutions to strongly constrained congruence equations · · · · · · · · · · · · 4
4 Concise solutions to weakly constrained congruence equations· · · · · · · · · · · · · 8
5 Pro of of solutions to weakly constrained congruence equations · · · · · · · · · · · · 11
6 Concise formats for the popularization of congruence theorems · · · · · · · · · · · · 14
7 The new application of indefinite equations in physics · · · · · · · · · · · · · · · · · · 18
Citation: Dongfang, X. D. Dongfang Brief General Solutions to Congruence Equations. Mathematics & Nature 3, 202301 (2023).
2 X. D. Dongfang Dongfang Brief General Solutions to Congruence Equations
1 Introduction
The Chinese remainder theorem
[1-3]
, also known as the Sun Tzu theorem
[4-6]
, is a very ancient
principle for solving general solutions to congruence equations. The Chinese remainder theorem
provides a general solution for a strongly constrained system of linear congruence equations that
satisfy module pairwise coprime. For hundreds of years, the application of linear congruence
equations was limited to digital games, and it was not until the rise of computer science that
linear congruence equations were applied in computer arithmetic
[7]
and information science
[8-10]
,
which sparked widespread interest in the Chinese remainder theorem.
The focus now is on discussing the most concise formulaic description of the programmatic
calculation of the Chinese remainder theorem, the conditions for the existence of solutions and
expressions for general solutions to weakly constrained system of linear congruence equations with
pairwise differences, as well as the concise steps for constructing solutions to strongly constrained
and mutually constrained system of congruence equations, so that congruence equation theory
can be popularized on a wider range. Finally, a rational number solution for the minimum number
of digits of an indefinite equation system was introduced, while the question of whether there is
a general method to obtain a rational number solution for the minimum number of digits of an
indefinite equation system of the same kind remains to be solved.
2 Formulaic description of the Chinese remainder theorem
Lemma (Chinese Remainder Theorem) Let both m
i
and a
i
be integers, where m
i
is
mutually prime, and the integer i = 1, 2, · · · , n is a congruence system of equations,
x a
1
(mod m
1
)
x a
2
(mod m
2
)
.
.
.
x a
n
(mod m
n
)
(2.1)
has countless solutions, and the expression for the general solution is
x =
r +
n
i=1
a
i
t
i
m
i
n
j=1
m
j
(2.2)
Where r is an arbitrary integer and t
i
(t
i
< m
i
) is the minimum natural number solution of the
double module arithmetic equation
mo d
t
i
mo d
m
1
i
n
j=1
m
j
, m
i
, m
i
1 (2.3)
The integer m
i
in the congruence equation system (2.1) mentioned above is called the module,
the integer a
i
is called the remainder, and t
i
is called the inverse element in the sense of the
module m
i
of m
1
i
(m
1
m
2
· · · m
n
). Using the expression method of scientific computing software,
mo d (N, M) is the remainder of integer N divided by integer M, that is, the remainder of integer
N to module M . The conditional equation (2.3) is a double congruence equation that determines
Mathematics & Nature Vol. 3 (2023) 3
the integer t
i
that is not greater than the module m
i
. First calculate the total modulus product
(m
1
m
2
· · · m
n
) of the congruence equation system divided by the quotient of module m
i
and
the remainder of module m
i
, and then solve the congruence equation that the product of this
remainder multiplied by the inverse element t
i
has a remainder of 1 for module m
i
.
The Chinese remainder theorem is the fundamental principle for solving linear congruence
equations, but it is not perfect and has two reserved problems. Firstly, the Chinese Remainder
Theorem does not clarify the conditions for the existence of solutions to weakly constrained
congruence systems with two distinct modules, nor does it provide a general solution formula
for the case where there is a solution; Secondly, the Chinese remainder theorem cannot directly
represent the minimum natural number solution of a congruence equation system, and the result
is a congruence equation with the product of all modules as modules, rather than a simplified
form where the constant part is the minimum natural number solution.
Example 1. Find the general solution of the following congruence equation system,
x 281 (mod 541)
x 313 (mod 601)
x 379 (mod 863)
x 98 (mod 3571)
(2.4)
The modulus and remainder of the congruence equation system in the proposition are
m
1
= 541, m
2
= 601, m
3
= 863, m
4
= 3571
a
1
= 281, a
2
= 313, a
3
= 379, a
4
= σ
Therefore,
n
j=1
m
j
= 1002010754993. Substitute it into (2.3) to obtain four double congruence
equations regarding the inverse element t
i
,
mo d
t
1
mo d
1002010754993
541
, 541
, 541
1
mo d
t
2
mo d
1002010754993
601
, 601
, 601
1
mo d
t
3
mo d
1002010754993
863
, 863
, 863
1
mo d
t
4
mo d
1002010754993
3571
, 3571
, 3571
1
That is,
mo d (154t
1
, 541) 1
mo d (285t
2
, 601) 1
mo d (37t
3
, 863) 1
mo d (1787
t
4
,
3571)
1
The minimum natural number solutions of the four inverse elements are
t
1
= 404, t
2
= 504, t
3
= 70, t
4
= 1191
4 X. D. Dongfang Dongfang Brief General Solutions to Congruence Equations
Substituting them into (2.2) yields the general solution of the congruence equation system (2.4),
x =
r +
4
i=1
a
i
t
i
m
i
4
j=1
m
j
=
281 × 404
541
+
313 × 504
601
+
379 × 70
863
+
98 × 1191
3571
+ r
4
j=1
m
j
(2.5)
= 536827387746612 + 1002010754993r
The constant part in the above general solution expression is much larger than the total module
product
n
j=1
m
j
, being not the minimum natural number solution. The reduced general solution
with the constant part being the minimum natural number solution is the congruence result of
(2.5) to the module
n
j=1
m
j
,
x = 751633825357 + 1002010754993k
3 Concise solutions to strongly constrained congruence equations
Now let’s solve the first reservation problem of the Chinese remainder theorem, which is to
provide a simplified general solution for the strongly constrained congruence equations with its
module pairwise coprime, so that the constant part of the general solution of the congruence
equation system is the minimum natural number solution of the congruence equation system.
Theorem 1 (Dongfang) Assumes that m
i
and a
i
are both integers, m
i
is mutually prime,
integer i = 1, 2, · · · , n, integer n > 2, then the congruence equation system
x a
1
(mod m
1
)
x a
2
(mod m
2
)
.
.
.
x a
n
(mod m
n
)
has countless solutions, and the expression for the general solution is
x =
n1
i=1
i
j=1
m
j
s
i
+ a
1
+ r
n
j=1
m
j
(3.1)
Where s
i
is the minimum natural number solution of the module arithmetic equation
mo d
l1
i=1
i
j=1
m
j
s
i
+ a
1
a
l
, m
l
0 (3.2)
where l = 2, 3, · · · , n and r is any integer.
Proof. Prove this theorem using mathematical induction
[11, 12]
. When n = 2, because (m
1
, m
2
) =
1, according to the theory of Diophantine equations, let k
1
be an integer, and the binary quadratic
indefinite equation m
1
s
1
m
2
k
1
= a
2
a
1
with respect to integer s
1
and integer k
1
has a solu-
tion, that is, there exists a minimum natural number s
1
that holds the congruence equation
Mathematics & Nature Vol. 3 (2023) 5
m
1
s
1
+ a
1
a
2
0 (mod m
2
), where r is any integer, so
x a
1
= m
1
(r m
2
+ s
1
) 0 (mod m
1
)
x a
2
= rm
1
m
2
+ (m
1
s
1
+ a
1
a
2
)
= m
1
s
1
+ a
1
a
2
0 (mod m
2
)
The simplified representations of both are exactly x a
1
(mod m
1
) and x a
2
(mod m
2
). So, the
theorem holds when n = 2.
When n = 3, the strong constraint condition (m
1
m
2
, m
3
) = 1, and it has been proven that
m
1
s
1
+ a
1
a
2
0 (mod m
2
). Assuming k
2
is an integer, the first-order indefinite equation
m
1
m
2
s
2
k
2
m
2
= a
3
a
1
m
1
s
1
with respect to integer s
2
and integer k
2
has a solution, that is, there
exists a minimum natural number s
2
that holds the congruence equation m
1
m
2
s
2
+m
1
s
1
+a
1
a
3
0 (mod m
3
). Take x = rm
1
m
2
m
3
+ m
1
m
2
s
2
+ m
1
s
1
+ a
1
, where r is any integer, so
x a
1
= rm
1
m
2
m
3
+ m
1
m
2
s
2
+ m
1
s
1
0 (mod m
1
)
x a
2
= rm
1
m
2
m
3
+ m
1
m
2
s
2
+ m
1
s
1
+ a
1
a
2
= m
1
s
1
+ a
1
a
2
0 (mod m
2
)
x a
3
= rm
1
m
2
m
3
+ m
1
m
2
s
2
+ m
1
s
1
+ a
1
a
3
= m
1
m
2
s
2
+ m
1
s
1
+ a
1
a
3
0 (mod m
3
)
In other words, x a
1
(mod m
1
), x a
2
(mod m
2
), x a
3
(mod m
3
). Therefore, the theorem
holds when n=3.
Let Theorem 1 hold for any integer n > 3, that is, if m
1
, m
2
, · · · , m
n
are mutually prime, and
the congruence equation system x a
1
(mod m
1
), x a
2
(mod m
2
),..., x a
n
(mod m
n
) has
countless solutions, the general solution is
x = r
n
j=1
m
j
+
n1
i=1
i
j=1
m
j
s
i
+ a
1
Where
n1
i=1
i
j=1
m
j
s
i
+ a
1
a
l
0 (mod m
n
) and r
is any integer. So for integer n + 1, taking
r
= rm
n+1
+ s
n
, there is
x = (rm
n+1
+ s
n
)
n
j=1
m
j
+
n1
i=1
i
j=1
m
j
s
i
+ a
1
= rm
n+1
n
j=1
m
j
+
s
k
n
j=1
m
j
+
n1
i=1
i
j=1
m
j
s
i
+ a
1
= r
n+1
j=1
m
j
+
n
i=1
i
j=1
m
j
s
i
+ a
1
Because under strong constraint condition
n
j=1
m
j
, m
n+1
= 1, let k
n
be an integer, and the
6 X. D. Dongfang Dongfang Brief General Solutions to Congruence Equations
indefinite equation
n
j=1
m
j
s
n
m
n+1
k
n
= a
n+1
a
1
n1
i=1
i
j=1
m
j
s
i
for integer s
n
and integer k
n
must have a solution, i.e
n
i=1
i
j=1
m
j
s
i
+ a
1
a
n+1
0 (mod m
n+1
)
And because r
n+1
j=1
m
j
= rm
n+1
n
j=1
m
j
0 (mod m
n+1
), there is
r
n+1
j=1
m
j
+
n
i=1
i
j=1
m
j
s
i
+ a
1
a
n+1
0 (mod m
n+1
)
or
r
n+1
j=1
m
j
+
n
i=1
i
j=1
m
j
s
i
+ a
1
a
n+1
(mod m
n+1
)
Therefore,
x a
n+1
= r
n+1
j=1
m
j
+
n
i=1
i
j=1
m
j
s
i
+ a
1
0 (mod m
n+1
)
The equivalent formula is x a
n+1
(mod m
n+1
), which proves that Theorem 1 also holds for
integers n+1.
According to mathematical induction, Theorem 1 holds for any integer n
2
. Proof completed.
The Chinese remainder theorem and Theorem 1 respectively provide two forms of expression for
the general solution of the modular pairwise coprime congruence equation system, with significant
differences between the two expressions.
The conditional equation for constructing a general solution of a congruence equation system
using the Chinese remainder theorem is a double congruence equation with respect to several
inverse elements t
i
, where the number of inverse elements is equal to the number of modules,
and the expanded congruence equations are independent of each other. The conditional equation
for constructing a general solution of a congruence equation system using Theorem 1 is a single
congruence equation with several parameters s
i
, where the number of parameters is 1 less than
the number of modules. The expanded congruence equations are not completely independent,
and the congruence equation with more parameters includes the parameters in the congruence
equation with fewer parameters. In fact, they are a set of congruence equations constrained by
each parameter s
i
.
The complexity of determining the parameter s
i
using Theorem 1 is the same as that of deter-
mining the inverse element t
i
using the Chinese remainder theorem. Indeed, Chinese remainder
theorem has a history of nearly 800 years and extensive application experience, making it easier
to accept. Unlike the expression of the general solution of the congruence equation system given
by the Chinese remainder theorem, Theorem 1 provides the expression of the general solution
of the congruence equation system (3.1), where the constant part is the minimum natural num-
ber solution of the congruence equation system, and its general solution formula is called the
simplified solution of the congruence equation system.
Mathematics & Nature Vol. 3 (2023) 7
Example 2. Find the general solution of the following congruence equation system,
x 347 (mod 449)
x 517 (mod 571)
x 601 (mod 643)
x 521 (mod 659)
x 379 (mod 739)
(3.3)
The modulus and remainder of the congruence equation system in the proposition are
m
1
= 449, m
2
= 571, m
3
= 643, m
4
= 659, m
5
= 739
a
1
= 347, a
2
= 517, a
3
= 601, a
4
= 521, a
5
= 379
(3.4)
From (3.2), take n = 2, 3, 4, 5, and obtain the congruence equation system for determining
parameters s
1
, s
2
, s
3
, s
4
,
mo d (m
1
s
1
+ a
1
a
2
, m
2
) 0
mo d (m
1
s
1
+ m
1
m
2
s
2
+ a
1
a
3
, m
3
) 0
mo d (m
1
s
1
+ m
1
m
2
s
2
+ m
1
m
2
m
3
s
3
+ a
1
a
4
, m
4
) 0
mo d [m
1
s
1
+ m
1
m
2
s
2
+ m
1
m
2
m
3
s
3
+ m
1
m
2
m
3
m
4
s
4
+ a
1
a
5
, m
n
] 0
Substitute (3.4) into the above equation system to obtain
mod (449s
1
170, 571) 0
mod (449s
1
+ 256379s
2
254, 643) 0
mod (449s
1
+ 256379s
2
+ 164851697s
3
174, 659) 0
mod [449s
1
+ 256379s
2
+ 164851697s
3
+ 108637268323s
4
32, 739] 0
Solve the above congruence equations in order, and the minimum natural number solutions for
each parameter obtained are
s
1
= 476, s
2
= 419, s
3
= 141, s
4
= 82
Substitute these parameters and (3.4) into formula (3.1) to obtain the general solution of the
congruence equation system (3.3),
x =
n1
i=1
i
j=1
m
j
s
i
+ a
1
+ r
n
j=1
m
j
= ms
1
+ m
1
m
2
s
2
+ m
1
m
2
m
3
s
3
+ m
1
m
2
m
3
m
4
s
4
+ r
5
j=1
m
j
(3.5)
= 8931607728635 + 80282941290697r
The constant part in the general solution (3.5) is smaller than the modulus product
n
j=1
m
j
, so the
constant part is the minimum natural number solution. This general solution is the simplified
8 X. D. Dongfang Dongfang Brief General Solutions to Congruence Equations
general solution of the congruence equation system (3.3).
4 Concise solutions to weakly constrained congruence equations
Next, let’s solve the second retention problem of the Chinese remainder theorem, which is to
provide a simplified general solution for weakly constrained congruence equations with different
modules, so that the constant part of the general solution of the weakly constrained congruence
equation system is the minimum natural number solution of the congruence equation system.
Theorem 2 (Dongfang) Let the integer m
1
, m
2
, · · · , m
n
be mutually exclusive, where n
2
, denote
the minimum common multiple of m
1
, m
2
, · · · , m
n
as [m
1
, · · · , m
n
], If there exists all the smallest
integers s
i
that satisfy the module arithmetic equation
mo d
l1
i=1
[m
1
, · · · , m
i
] s
i
+ a
1
a
l
, m
l
0 (4.1)
where i = 1, 2, · · · , l 1, l = 2, 3, · · · , n, then the congruence equation system
x a
1
(mod m
1
)
x a
2
(mod m
2
)
.
.
.
x a
n
(mod m
n
)
has countless solutions, and the expression for the general solution is
x = r [m
1
, · · · , m
n
] +
n1
i=1
[m
1
, · · · , m
i
] s
i
+ a
1
(4.2)
Where r is any natural numb er.
The pro cess of proving Theorem 2 using mathematical induction is similar to that of Theorem
1, which is omitted here. In the next section, we will use the construction method of the solution
of the congruence equation system to prove Theorem 2. The method of proof is also applicable to
re proving Theorem 1. Here, we will first deal with two examples of finding the simplified general
solution of weakly constrained congruence equations with two distinct modules.
Example 3. Find the general solution of the following congruence equation system,
x 7 (mod 30)
x 13 (mod 28)
x 22 (mod 75)
x 55 (mod 63)
(4.3)
The modulus and remainder of the congruence equation system in the proposition are
m
1
= 30, m
2
= 28, m
3
= 75, m
4
= 63
a
1
= 7, a
2
= 13, a
3
= 22, a
4
= 55,
(4.4)
Mathematics & Nature Vol. 3 (2023) 9
Calculate the minimum common multiple of each group of modules that sequentially increase
module
[m
1
, m
2
] = [30, 28] = 420
[m
1
, m
2
, m
3
] = [30, 28, 75] = 2100
[m
1
, m
2
, m
3
, m
4
] = [30, 28, 75, 63] = 6300
(4.5)
Substitute (4.4) and (4.5) into the three expansion equations of the conditional equation (4.1) of
Theorem 2,
m
1
s
1
+ a
1
a
2
0 (mod m
2
)
[m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
a
3
0 (mod m
3
)
[m
1
, m
2
, m
3
] s
3
+ [m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
a
3
0 (mod m
4
)
Obtaining a congruence equation system for parameters s
1
, s
2
and s
3
,
30s
1
+ 7 13 0 (mod 28)
[30, 28] s
2
+ 30s
1
+ 7 22 0 (mod 75)
[30, 28, 75] s
3
+ [30, 28] s
2
+ 30s
1
+ 7 55 0 (mod 63)
Simplify
30s
1
6 0 (mod 28)
420s
2
+ 30s
1
15 0 (mod 75)
2100s
3
+ 420s
2
+ 30s
1
42 0 (mod 63)
The minimum natural number solution is
s
1
= 3, s
2
= 0, s
3
= 1 (4.6)
Substitute (4.4) and (4.6) into the general solution formula (4.2) of Theorem 2 to obtain the
general solution of the congruence equation system (4.3),
x = [m
1
, m
2
, m
3
, m
4
] r + a
1
+ m
1
s
1
+ [m
1
, m
2
] s
2
+ [m
1
, m
2
, m
3
] s
3
= [30, 28, 75, 63] r + 7 + 30 × 3 + [30, 28] × 0 + [30, 28, 75] × 1
= 6300r + 2197
(4.7)
Because 2197<6300, the constant part 2197 of (4.7) is the minimum natural number solution of
the congruence equation system (4.3).
Example 4. Find the minimum universal remainder σ that makes the following congruence
equations solvable,
x 7 (mod 30)
x 13 (mod 28)
x 22 (mod 75)
x σ (mod 63)
(4.8)
10 X. D. Dongfang Dongfang Brief General Solutions to Congruence Equations
The modulus and remainder of the congruence equation system in the proposition are
m
1
= 30, m
2
= 28, m
3
= 75, m
4
= 63
a
1
= 7, a
2
= 13, a
3
= 22, a
4
= σ
(4.9)
Calculate the minimum common multiple of each group of modules that sequentially increase
module
[m
1
, m
2
] = [30, 28] = 420
[m
1
, m
2
, m
3
] = [30, 28, 75] = 2100
[m
1
, m
2
, m
3
, m
4
] = [30, 28, 75, 63] = 6300
(4.10)
Substitute (4.9) and (4.10) into the three expansion equations of the conditional equation (4.1)
of Theorem 2
m
1
s
1
+ a
1
a
2
0 (mod m
2
)
[m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
a
3
0 (mod m
3
)
[m
1
, m
2
, m
3
] s
3
+ [m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
a
3
0 (mod m
4
)
Obtaining a congruence equation system for parameters s
1
, s
2
and s
3
,
30s
1
+ 7 13 0 (mod 28)
[30, 28] s
2
+ 30s
1
+ 7 22 0 (mod 75)
[30, 28, 75] s
3
+ [30, 28] s
2
+ 30s
1
+ 7 σ 0 (mod 63)
Its simplified form is
30s
1
+ 7 13 0 (mod 28)
420s
2
+ 30s
1
+ 7 22 0 (mod 75)
2100s
3
+ 420s
2
+ 30s
1
+ 7 σ 0 (mod 63)
Find the minimum natural number solution from the first two congruence equations
s
1
= 3, s
2
= 0
Substituting into the third congruence equation to obtain the congruence equations for s
3
and σ
2100s
3
+ 97 σ 0 (mod 63)
According to the principle of first order indefinite equations, the minimum natural number solu-
tion is,
s
3
= 2, σ = 13
So, the minimum residue that makes the congruence equation system (4.8) solvable is σ = 13.
According to the general solution expression (4.2) of Theorem 2, the general solution of the
equation system that satisfies the condition is,
x = [m
1
, m
2
, m
3
, m
4
] r + a
1
+ m
1
s
1
+ [m
1
, m
2
] s
2
+ [m
1
, m
2
, m
3
] s
3
= [30, 28, 75, 63] r + 7 + [30] × 3 + 0 + [30 , 28, 75] × 2
= 6300r + 4297
Mathematics & Nature Vol. 3 (2023) 11
Because 4297<6300, the constant part 4297 of the above result is the minimum natural number
solution that satisfies the condition for the congruence equation system (4.8).
5 Proof of solutions to weakly constrained congruence equations
Although mathematical induction is strict in proving propositions, it often conceals the reason-
ing pro cess from conditions to conclusions, resulting in limited popularization and development
of theory. For example, using mathematical induction can effectively prove the formula for the
sum of squares or sum of cubes of continuous natural numbers. However, due to the lack of a
summation process in the proof process, beginners cannot comprehend the derivation method of
formulas for higher power sums of continuous natural numbers. Therefore, the deductive proof
method for constructing propositions conclusions should be advocated. The following uses the
method of constructing general solutions to prove Theorem 2 for solving weakly constrained linear
congruence systems, and the proof process also applies to the proof of Theorem 1.
The proof of Theorem 2. Let the general form of a congruence equation system containing
n congruence equations be
x a
1
(mod m
1
)
x a
2
(mod m
2
)
x a
3
(mod m
3
)
.
.
.
x a
n
(mod m
n
)
Among them, n modules m
i
differ from each other in pairs. In order to construct the general
solution of the congruence equation and find the conditions for its existence, the congruence
equation system is first written as an algebraic equation system
x = m
1
N
1
+ a
1
x = m
2
N
2
+ a
2
x = m
3
N
3
+ a
3
(5.1)
.
.
.
x = m
n
N
n
+ a
n
(5.2)
Where i = 1 , 2, · · · , n, N
i
are all arbitrary integers. Use [m
1
, · · · , m
n
] to represent the least common
multiple of m
1
, m
2
, · · · , m
n
.
i) Eliminating x from the first and second equations of the congruence equation system (4.10),
find N
2
, and the result is
N
2
=
m
1
N
1
+ a
1
a
2
m
2
Let r
1
be any integer, and s
1
be the smallest positive integer that appears in the conditional
formula. Because N
1
and N
2
are both arbitrary integers, one of the necessary and sufficient
12 X. D. Dongfang Dongfang Brief General Solutions to Congruence Equations
conditions for the above equation to satisfy the division relationship m
2
| (m
1
N
1
+ a
1
a
2
) is that
any integer N
1
satisfies the division equation,
N
1
=
[m
1
, m
2
]
m
1
r
1
+ s
1
(5.3)
Substitute into the aforementioned equation and simplify to obtain
N
2
=
[m
1
, m
2
]
m
2
r
1
+
m
1
s
1
+ a
1
a
2
m
2
The first item is already an integer. The second term is also an integer, which must satisfy the
condition
m
2
| (m
1
s
1
+ a
1
a
2
)
i.e
mo d (m
1
s
1
+ a
1
a
2
, m
2
) 0 (5.4)
Substitute (5.3) into x = m
1
N
1
+ a
1
of (5.1) to obtain
x = [m
1
, m
2
] r
1
+ m
1
s
1
+ a
1
(5.5)
ii) Substitute the value of x obtained above (5.5) into the third equation of the congruence
equation system (4.10), and calculate N
3
. The result is
N
3
=
[m
1
, m
2
] r
1
+ m
1
s
1
+ a
1
a
3
m
3
Let r
2
be any integer, and s
2
be the smallest positive integer that appears in the conditional
formula. Because N
3
and r
1
are both arbitrary integers, one of the necessary and sufficient
conditions for the above equation to satisfy the division relationship
m
3
| (r
1
[m
1
, m
2
] + m
1
s
1
+ a
1
a
3
)
is that any integer r
1
satisfies the division equation,
r
1
=
[m
1
, m
2
, m
3
]
[m
1
, m
2
]
r
2
+ s
2
(5.6)
Substitute into the aforementioned equation and simplify to obtain
N
3
=
[m
1
, m
2
, m
3
]
m
3
r
2
+
[m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
a
3
m
3
(5.7)
The first item is already an integer. The second term is also an integer, which must satisfy the
condition
m
3
| ([m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
a
3
)
i.e
mod ([m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
a
3
, m
3
) 0 (5.8)
Substitute (5.7) into x = m
3
N
3
+ a
3
of (5.1) to obtain
x = [m
1
, m
2
, m
3
] r
2
+ [m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
(5.9)
Mathematics & Nature Vol. 3 (2023) 13
iii) Substitute the value of x obtained above (5.9) into the third equation of the congruence
equation system (4.10), and calculate N
4
. The result is
N
4
=
[m
1
, m
2
, m
3
] r
2
m
4
+
[m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
a
4
m
4
Let r
3
be any integer, and s
3
be the smallest positive integer that appears in the conditional
formula. Because N
4
and r
2
are both arbitrary integers, one of the necessary and sufficient
conditions for the above equation to satisfy the division relationship
m
4
| ([m
1
, m
2
, m
3
] r
2
+ [m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
a
4
)
is that any integer r
2
satisfies the division equation,
r
2
=
[m
1
, · · · , m
4
]
[m
1
, m
2
, m
3
]
r
3
+ s
3
(5.10)
Substitute into the aforementioned equation and simplify to obtain
N
4
=
[m
1
, · · · , m
4
]
m
4
r
3
+
[m
1
, m
2
, m
3
] s
3
+ [m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
a
4
m
4
(5.11)
The first item is already an integer. The second term is also an integer, which must satisfy the
condition
m
4
| ([m
1
, m
2
, m
3
] s
3
+ [m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
a
4
)
i.e
mo d ([m
1
, m
2
, m
3
] s
3
+ [m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
a
4
, m
4
) 0 (5.12)
Substitute (5.11) into x = m
4
N
4
+ a
4
of (5.1) to obtain
x = [m
1
, · · · , m
4
] r
3
+ [m
1
, m
2
, m
3
] s
3
+ [m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
(5.13)
iv) Further introduce any integerr
4
, r
5
, · · · , r
n2
and the smallest positive integer s
4
, s
5
, · · · ,
s
n2
that will app ear in the conditional formula. Substitute x into the subsequent congruence
equations of the congruence equation system, eliminating x. Calculate sequentially and then
guess the necessary and sufficient conditions for N
n1
to be an integer through induction
mo d
[m
1
, · · · , m
n2
] s
n2
+ · · · + [m
1
, m
2
, m
3
] s
3
+ [m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
a
n
, m
n
0 (5.14)
as well as the finally calculated the expression for x,
x =
[m
1
, · · · , m
n1
] r
n2
+ [m
1
, · · · , m
n2
] s
n2
+ · · ·
+ [m
1
, m
2
, m
3
] s
3
+ [m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
(5.15)
v) Substitute the value of x obtained above (5.15) into the last equation of the congruence equation
14 X. D. Dongfang Dongfang Brief General Solutions to Congruence Equations
system (4.10), and calculate N
n
. The result is
N
n
=
[m
1
, · · · , m
n1
] r
n2
m
n
+
1
m
n
[m
1
, · · · , m
n2
] s
n2
+ · · ·
+ [m
1
, m
2
, m
3
] s
3
+ [m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
a
n
Let r
n1
= r be any integer, and s
n1
be the smallest positive integer that appears in the con-
ditional formula. Because N
n
and r
n1
are both arbitrary integers, one of the necessary and
sufficient conditions for the integer equation to satisfy the integer division relationship mentioned
above is that any integer r
n2
satisfies the integer division equation,
r
n2
=
[m
1
, · · · , m
n
]
[m
1
, · · · , m
n1
]
r + s
n1
(5.16)
Substitute into the aforementioned equation and simplify to obtain
N
n
=
[m
1
, · · · , m
n
]
m
n
r +
1
m
n
[m
1
, · · · , m
n1
] s
n1
+ [m
1
, · · · , m
n2
] s
n2
+ · · · + [m
1
, m
2
, m
3
] s
3
+ [m
1
, m
2
] s
2
+m
1
s
1
+ a
1
a
n
(5.17)
The first term is already an integer, and the necessary and sufficient condition for the second
term to be an integer is
mo d
[m
1
, · · · , m
n1
] s
n1
+ [m
1
, · · · , m
n2
] s
n2
+ · · ·
+ [m
1
, m
2
, m
3
] s
3
+ [m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
a
n
, m
n
0 (5.18)
Substitute (5.17) into x = m
n
N
n
+ a
n
of (5.1) to obtain
x = [m
1
, · · · , m
n
] r +
[m
1
, · · · , m
n1
] s
n1
+ [m
1
, · · · , m
n2
] s
n2
+ · · · + [m
1
, m
2
, m
3
] s
3
+ [m
1
, m
2
] s
2
+m
1
s
1
+ a
1
(5.19)
Equation (5.18) is exactly Equation (4.1) in Theorem 2, and Equation (5.19) is the general solution
expression (4.2) in Theorem 2. So, Theorem 2 holds.
6 Concise formats for the popularization of congruence theorems
Abstracting the problem-solving method into a theorem facilitates memory and simplifies the
application process. However, the abstract and strict expression of theorems often does not
facilitate the popularization of theories. The construction and expression of general solutions to
congruence equations are typical examples. The proof process of Theorem 1 and Theorem 2 is
the construction process of the general solution of the congruence equation system, but it is not
easy to understand. For a specific congruence equation system, it is very convenient to discard
the theorem of constructing a general solution and simplify the construction of the solution for
directly obtaining a general solution.
Since the theory of congruence equations has been applied in information science, it should be
Mathematics & Nature Vol. 3 (2023) 15
widely popularized. This requires a programmatic step that highlights concise logic, and a concise
and fluent expression of the mathematical principles and methods for constructing solutions to
congruence equations, making it easy to understand. Here are two examples to illustrate the
concise process of constructing general solutions for strongly and weakly constrained congruence
systems.
Example 5. Find the general solution of the congruence equation system with modulo
m
1
, m
2
, m
3
, m
4
coprime and remainder are a
1
, a
2
, a
3
, a
4
.
The standard form of the congruence equation system described by the problem is
x a
1
(mod m
1
)
x a
2
(mod m
2
)
x a
3
(mod m
3
)
x a
4
(mod m
4
)
Write it in the form of an algebraic indefinite system of equations
x = m
1
N
1
+ a
1
x = m
2
N
2
+ a
2
x = m
3
N
3
+ a
3
x = n
4
N
4
+ a
4
Among them, N
1
, N
2
, N
3
and N
4
N4 are all arbitrary integers. Let r
1
, r
2
and r
3
= r be any
integer, and s
1
, s
2
and s
3
be the smallest positive integers that appear in the conditional formula.
Eliminate x from the first and second equations and find the expression for the any integer N
2
m
2
N
2
+ a
2
= m
1
N
1
+ a
1
N
2
=
m
1
N
1
+ a
1
a
2
m
2
N
1
= m
2
r
1
+ s
1
↑⟩
=
m
1
(m
2
r
1
+ s
1
) + a
1
a
2
m
2
= m
1
r
1
+
m
1
s
1
+ a
1
a
2
m
2
mod (m
1
s
1
+ a
1
a
2
, m
2
) 0 s
1
=? ↓⟩
x = m
2
N
2
+ a
2
= m
1
m
2
r
1
+ m
1
s
1
+ a
1
Substitute the above x into the third equation to find the expression for any integer N
3
,
m
3
N
3
+ a
3
= m
1
m
2
r
1
+ m
1
s
1
+ a
1
N
3
=
m
1
m
2
r
1
+ m
1
s
1
+ a
1
a
3
m
3
r
1
= m
3
r
2
+ s
2
↑⟩
=
m
1
m
2
(m
3
r
2
+ s
2
) + m
1
s
1
+ a
1
a
3
m
3
16 X. D. Dongfang Dongfang Brief General Solutions to Congruence Equations
= m
1
m
2
r
2
+
m
1
m
2
s
2
+ m
1
s
1
+ a
1
a
3
m
3
mod (m
1
m
2
s
2
+ m
1
s
1
+ a
1
a
3
, m
3
) 0 s
2
=? ↓⟩
x = m
3
N
3
+ a
3
= m
1
m
2
m
3
r
2
+ m
1
m
2
s
2
+ m
1
s
1
+ a
1
Substitute the above x into the forth equation to find the expression for any integer N
4
,
m
4
N
4
+ a
4
= m
1
m
2
m
3
r
2
+ m
1
m
2
s
2
+ m
1
s
1
+ a
1
N
4
=
m
1
m
2
m
3
r
2
+ m
1
m
2
s
2
+ m
1
s
1
+ a
1
a
4
m
4
r
2
= m
4
r
3
+ s
3
↑⟩
=
m
1
m
2
m
3
(m
4
r
3
+ s
3
) + m
1
m
2
s
2
+ m
1
s
1
+ a
1
a
4
m
4
= m
1
m
2
m
3
r
3
+
m
1
m
2
m
3
s
3
+ m
1
m
2
s
2
+ m
1
s
1
+ a
1
a
4
m
4
mod (m
1
m
2
m
3
s
3
+ m
1
m
2
s
2
+ m
1
s
1
+ a
1
a
4
, m
4
) 0 s
3
=? ↓⟩
x = m
4
N
4
+ a
4
= m
1
m
2
m
3
m
4
r
3
+ m
1
m
2
m
3
s
3
+ m
1
m
2
s
2
+ m
1
s
1
+ a
1
The concise process for solving strongly constrained system of linear congruence equations
mentioned above is a simplified expression of congruence theorem 1. The congruence theorem 2
for weakly constrained linear congruence systems with different moduli has a similar and concise
process. The only difference is that the latter requires the concept of the least common multiple.
The concise process of solving system of linear congruence equations will be able to popularize
the knowledge of congruence theorem to the greatest extent possible.
Example 6. Find the general solution of a congruence equation system with modules m
1
, m
2
,
m
3
, m
4
that are different from each other and have remainders a
1
, a
2
, a
3
, a
4
.
The standard form of the congruence equation system described by the problem is
x a
1
(mod m
1
)
x a
2
(mod m
2
)
x a
3
(mod m
3
)
x a
4
(mod m
4
)
Write it in the form of an algebraic indefinite system of equations
x = m
1
N
1
+ a
1
x = m
2
N
2
+ a
2
x = m
3
N
3
+ a
3
x = n
4
N
4
+ a
4
Among them, N
1
, N
2
, N
3
and N
4
N4 are all arbitrary integers. Let r
1
, r
2
and r
3
= r be any
Mathematics & Nature Vol. 3 (2023) 17
integer, and s
1
, s
2
and s
3
be the smallest positive integers that appear in the conditional formula.
Eliminate x from the first and second equations and find the expression for the any integer N
2
m
2
N
2
+ a
2
= m
1
N
1
+ a
1
N
2
=
m
1
N
1
+ a
1
a
2
m
2
N
1
=
[m
1
, m
2
] r
1
m
1
+ s
1
=
m
1
m
2
[m
1
, m
2
] r
1
m
1
+ s
1
+
a
1
a
2
m
2
=
[m
1
, m
2
] r
1
+ m
1
s
1
+ a
1
a
2
m
2
=
[m
1
, m
2
]
m
2
r
1
+
m
1
s
1
+ a
1
a
2
m
2
mod (m
1
s
1
+ a
1
a
2
, m
2
) 0 s
1
=? ↓⟩
x = m
2
N
2
+ a
2
= [m
1
, m
2
] r
1
+ m
1
s
1
+ a
1
Substitute the above x into the third equation to find the expression for any integer N
3
,
m
3
N
3
+ a
3
= [m
1
, m
2
] r
1
+ m
1
s
1
+ a
1
N
3
=
[m
1
, m
2
] r
1
+ m
1
s
1
+ a
1
a
3
m
3
r
1
=
[m
1
, m
2
, m
3
] r
2
[m
1
, m
2
]
+ s
2
=
[m
1
, m
2
]
m
3
[m
1
, m
2
, m
3
] r
2
[m
1
, m
2
]
+ s
2
+
m
1
s
1
+ a
1
a
3
m
3
=
[m
1
, m
2
, m
3
] r
2
m
3
+
[m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
a
3
m
3
mod ([m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
a
3
, m
3
) 0 s
2
=? ↓⟩
x = m
3
N
3
+ a
3
= [m
1
, m
2
, m
3
] r
2
+ [m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
Substitute the above x into the forth equation to find the expression for any integer N
4
,
m
4
N
4
+ a
4
= [m
1
, m
2
, m
3
] r
2
+ [m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
N
4
=
[m
1
, m
2
, m
3
] r
2
+ [m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
a
4
m
4
r
2
=
[m
1
, · · · , m
4
]
[m
1
, m
2
, m
3
]
r
3
+ s
3
=
[m
1
, m
2
, m
3
]
m
4
[m
1
, · · · , m
4
]
[m
1
, m
2
, m
3
]
r
3
+s
3
+
[m
1
, m
2
] s
2
+m
1
s
1
+a
1
a
4
m
4
=
[m
1
, · · · , m
4
]
m
4
r
3
+
[m
1
, m
2
, m
3
] s
3
+ [m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
a
4
m
4
mod ([m
1
, m
2
, m
3
] s
3
+ [m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
a
4
, m
4
) 0 s
3
=? ↓⟩
x = m
4
N
4
+ a
4
18 X. D. Dongfang Dongfang Brief General Solutions to Congruence Equations
= [m
1
, · · · , m
4
] r
3
+ [m
1
, m
2
, m
3
] s
3
+ [m
1
, m
2
] s
2
+ m
1
s
1
+ a
1
7 The new application of indefinite equations in physics
A system of linear congruence equations is a system of equations comp osed of linear indefinite
equations. To solve linear indefinite equations, the properties of congruence equations can be
used to transform indefinite equations into congruence equations for solution.
Attempting to find a universal solution method for a class of linear indeterminate equations
[13]
,
in order to obtain the optimized rational number solution with the minimum number of digits
for macroscopic quantum theory system of indeterminate equations, this raises our attention to
the Chinese remainder theorem for solving system of linear congruence equations and provides a
simplified general solution for system of congruence equations. One of the indefinite equations in
macroscopic quantum theory
[14]
is as follows:
x
1
+ 2x
2
+ 2
2
x
3
+ 2
3
x
4
+ 2
4
x
5
2 (x
6
+ 2x
7
+ 2
2
x
8
+ 2
3
x
9
+ 2
4
)
=
1034
1625
x
1
+ 3x
2
+ 3
2
x
3
+ 3
3
x
4
+ 3
4
x
5
3 (x
6
+ 3x
7
+ 3
2
x
8
+ 3
3
x
9
+ 3
4
)
=
1975
4522
x
1
+ 4x
2
+ 4
2
x
3
+ 4
3
x
4
+ 4
4
x
5
4 (x
6
+ 4x
7
+ 4
2
x
8
+ 4
3
x
9
+ 4
4
)
=
323
966
(7.1)
x
1
+ 5x
2
+ 5
2
x
3
+ 5
3
x
4
+ 5
4
x
5
5 (x
6
+ 5x
7
+ 5
2
x
8
+ 5
3
x
9
+ 5
4
)
=
26887
99000
x
1
+ 6x
2
+ 6
2
x
3
+ 6
3
x
4
+ 6
4
x
5
6 (x
6
+ 6x
7
+ 6
2
x
8
+ 6
3
x
9
+ 6
4
)
=
2676
11687
There is a group of minimum digit rational number solutions for this system of indefinite equations
is,
x
1
=
63
16
, x
2
=
447
32
, x
3
=
69
4
,
x
4
=
69
8
, x
5
=
3
2
, x
6
=
105
32
, (7.2)
x
7
=
389
32
, x
8
=
227
16
, x
9
=
13
2
However, currently there is no universal method for obtaining the rational solution of the minimum
number of digits, nor has it been proven that the rational solution of the minimum number of
digits for the ab ove indefinite system of equations is unique. The rational solution of the minimum
number of digits has looser conditions than the integer solution, but lacks much theoretical
experience.
When analyzing observational data of quantum phenomena
[15]
, fitting a certain quantization
law through the optimal rational number solution of an indefinite equation system is similar to
the construction of a reduced general solution of a congruence equation system. The results can
unexpectedly solve certain problems in physics, which should be a new starting point
[16]
for the
Mathematics & Nature Vol. 3 (2023) 19
practical application of elementary number theory
[7]
.
Acknowledgements The authors wish to thank the polymath Andy Baker(University of Glasgow) for
testing the validity of the theorems and to Dr. Dean Rubine(Former Faculty at Carnegie Mellon School
Of Computer Science) for providing many revision suggestions .
Conflict of interest The authors declare that they have no conflict of interest.
References
[1] H. Cohen, A course in computational algebraic numb er theory, Springer Science & Business Media, 2013.
[2] A. Kondracki, The chinese remainder theorem. Formalized Mathematics 6 (1997) 573-577.
[3] D. Pei, A. Salomaa, C. Ding, Chinese remainder theorem: applications in computing, coding, cryptography,
World Scientific, 1996.
[4] J. Qin, Mathematical Treatise in Nine Chapters (in Chinese), Commercial Press, 1937.
[5] L. Hua, An introduction to the theory of numbers (in Chinese), Beijing: Science Press, 1957.
[6] J. Chen, Elementary Number Theory (in Chinese) [M], Beijing: Science Press, 1978.
[7] K.H. Rosen, Elementary number theory, Pearson Education London, 2011.
[8] J.H. Lac, Chinese remainder theorem and its applications. (2008).
[9] Grossschadl J. The Chinese Remainder Theorem and its application in a high-speed RSA crypto chip. Com-
puter Security Applications, 2000. ACSAC ’00. 16th Annual Conference. IEEE, 2001.
[10] K.K.A. Al-qader, Chinese Remainder Theorem and It’s Applications. (2014).
[11] G.H. Hardy and E. M. Wright . An Introduction to the Theory of Numbers [M] Oxford University Press ,
1979 .
[12] M. B . Nathanson . Elementary Methods in Number Theory [M] Springer - verlag , 2008 .
[13] C.C. Paige, M.A. Saunders, Solution of sparse indefinite systems of linear equations. SIAM journal on
numerical analysis 12 (1975) 617-629.
[14] Dongfang, X. D. Dongfang Com Quantum Equations of LIGO Signal. Mathematics & Nature 1, 202106
(2021).
[15] B.P. Abbott, R. Abbott, T. Abbott, M. Abernathy, F. Acernese, K. Ackley, C. Adams, T. Adams, P. Addesso,
R. Adhikari, Observation of gravitational waves from a binary black hole merger. Physical review letters 116
(2016) 061102.
[16] Dongfang, X. D. The Morbid Equation of Quantum Numbers. Mathematics & Nature 1, 202102 (2021).
Mathematics & Nature
Welcome to make more breakthrough discoveries and work together to change the scientific world!
#TEST_IGNORE_END ############# # Do not modify # MANIFEST END