See discussions, stats, and author profiles for this publication at: [Link]

net/publication/2135807

Algorithms for Solving Linear Congruences and Systems of Linear Congruences

Article in SSRN Electronic Journal · March 2007

DOI: 10.2139/ssrn.2725483

CITATIONS READS
5 2,782

1 author:

Florentin Smarandache
University of New Mexico
4,152 PUBLICATIONS 56,968 CITATIONS

SEE PROFILE

All content following this page was uploaded by Florentin Smarandache on 14 October 2017.

The user has requested enhancement of the downloaded file.

 ALGORITHMS FOR SOLVING LINEAR CONGRUENCES
AND SYSTEMS OF LINEAR CONGRUENCES
Florentin Smarandache
University of New Mexico
200 College Road
Gallup, NM 87301, USA
E-mail: smarand@[Link]

In this article we determine several theorems and methods for solving linear
congruences and systems of linear congruences and we find the number of distinct
solutions. Many examples of solving congruences are given.

§1. Properties for solving linear congruences.

Theorem 1. The linear congruence a1 x1 + ... + an xn ≡ b(mod m) has solutions if

and only if (a1 ,..., an , m) | b .
Proof:
a1 x1 + ... + an xn ≡ b(mod m) ⇔ a1 x1 + ... + an xn − my = b is a linear equation which
has solutions in the set of integer numbers ⇔ (a1 ,..., an , − m) | b ⇔ (a1 ,..., an , m) | b .
If m = 0 , a1 x1 + ... + an xn ≡ b(mod 0) ⇔ a1 x1 + ... + an xn = b has solutions in the
set of integer numbers ⇔ (a1 ,..., an ) | b ⇔ (a1 ,..., an , 0) | b .

Theorem 2. The congruence ax ≡ b(mod m) , m ≠ 0 , with (a, m) = d | b , has d

distinct solutions.
The proof is different of that from the number’s theory courses:
ax ≡ b(mod m ) ⇔ ax − my = b has solutions in the set of integer numbers; because
(a, m ) = d | b it results: a = a1d , m = m1d , b = b1d and (a1 , m1 ) = 1 ,
a1dx − m1dy = b1d ⇔ a1 x − m1 y = b1 . Because (a1 , m1 ) = 1 it results that the general
⎧ x = m1k1 + x0
solution of this equation is ⎨ , where k1 is a parameter and k1 ∈Z , and
⎩ y = a1k1 + y0
where (x0 , y0 ) constitutes a particular solution in the set of integer numbers of this
equation; x = m1k1 + x0 , k1 ∈ Z, m1 , x0 ∈ Z ⇒ x ≡ m1k1 + x0 (mod m) . We’ll assign
values to k1 to find all the solutions of the congruence.
It is evident that k1 ∈{0,1, 2,...,d − 1, d, d + 1,..., m − 1} which constitutes a complete
system of residues modulo m .
(Because ax ≡ b(mod m ) ⇔ ax ≡ b(mod − m ) , we suppose m > 0 .)
Let D = {0,1, 2,..., d − 1}; D ⊆ M , ∀α ∈ M , ∃β ∈ D : α ≡ β (mod d ) | m1
(because D constitutes a complete system of residues modulo d ).
It results that α m1 = β m1 (mod dm1 ) ; because x0 = x0 (mod dm1 ) , it results:
m1α + x0 ≡ m1β + x0 (mod m ) .

1
 Therefore ∀α ∈ M , ∃β ∈ D : m1α + x0 ≡ m1β + x0 (mod m ) ; thus k1 ∈ D .
∀γ , δ ∈ D , γ ≡/ δ (mod d ) | m1 ⇒ γ m1 ≡/ δ m1 (mod dm1 ) ; m1 ≠ 0 . It results that
m1γ + x0 ≡ m1δ + x0 (mod m ) is false, that is, we have exactly cardD = d distinct
solutions.
Remark 1. If m = 0 , the congruence ax ≡ b(mod 0) has one solution if a | b ;
otherwise it does not have solutions.
Proof:
ax ≡ b(mod 0) ⇔ ax = b has a solution in the set of integer numbers ⇔ a | b .

Theorem 3. (A generalization of the previous theorem)

The congruence a1 x1 + ... + an xn ≡ b(mod m ) , m1 ≠ 0 , with (a1 ,..., an , m ) = d | b
n −1
has d ⋅ m distinct solutions.
Proof:
Because a1 x1 + ... + an xn ≡ b(mod m ) ⇔ a1 x1 + ... + an xn ≡ b(mod − m ) , we
can consider m > 0 .
The proof is done by induction on n = the number of variables.
For n = 1 the affirmation is true in conformity with theorem 2.
Suppose that it is true for n − 1 . Let’s proof that it is true for n .
Let the congruence with n variables a1 x1 + ... + an xn ≡ b(mod m ) ,
a1 x1 + ... + an −1 xn −1 ≡ b − an xn (mod m ) . If we consider that xn is fixed, the congruence
a1 x1 + ... + an −1 xn −1 ≡ b − an xn (mod m ) is a congruence with n − 1 variables. To have
solutions we must have (a1 ,..., an −1 , m ) = δ | b − an xn ⇔ b − an xn ≡ 0(mod δ ) .
m
Because δ | m ⇒ ∈Z , therefore we can multiply the previous congruence
δ
m
with . It results that
δ
man mb m
xn ≡ (mod δ ⋅ ) (*)
δ δ δ
⎛ man m⎞ m m m m
which has ⎜⎝ , δ ⎟ = (an , δ ) = (an ,(a1 ,..., an −1 , m)) = (a1 ,..., an−1 , an , m) ⋅ d
δ δ⎠ δ δ δ δ
distinct solutions for xn . Let xn be a particular solution of the congruence (*). It results
0

that a1 x1 + ... + an −1 xn −1 ≡ b − an xn0 (mod m) has, conform to the induction’s hypothesis,

δ ⋅ m n − 2 distinct solutions for x1 ,..., xn−1 where δ = (a1 ,..., an −1 , m) .
Therefore the congruence a1 x1 + ... + an −1 xn−1 + an xn ≡ b(mod m) has
m
⋅ d ⋅ δ ⋅ m n − 2 = d ⋅ m n −1 distinct solutions for x1 ,..., xn −1 and xn .
δ

§2. A METHOD FOR SOLVING LINEAR CONGRUENCES

Let’s consider the congruence a1 x1 + ... + an xn ≡ b(mod m ) , m ≠ 0 ,

2
ai ≡ ai' (mod m) and b ≡ b ' (mod m) with 0 ≤ ai' , b ≤ m − 1 (we made the nonrestrictive
hypothesis m > 0 ). We obtain:
a1 x1 + ... + an xn ≡ b(mod m) ⇔ a1' x1 + ... + an' xn ≡ b ' (mod m) , which is a linear
equation; when it is resolved in Z it has the general solution:
⎧ x1 = α11k1 + ... + α1n kn + γ 1
⎪
⎪⎪⋅
⎨⋅
⎪ x = α k + ... + α k + γ
⎪ n n1 1 nn n n

⎪⎩ y = α n +1,1k1 + ... + α n+1,n kn + γ n +1

k j being parameters ∈Z , j = 1, n , α ij , γ i ∈ Z , constants, i = 1, n + 1 , j = 1, n .
Let’s consider α ij' ≡ α ij (mod m) and γ i' ≡ γ i (mod m) with 0 ≤ α ij' ,
γ ' ≤ m − 1; i = 1, n + 1, j = 1,n .
Therefore
⎧ x1 = α11'k1 + ... + α1n' kn + γ 1' (mod m)
⎪
⎪⋅
⎨ ; k j = parameters ∈Z, j = 1, n ; (**)
⎪⋅
⎪ xn = α n1 '
k1 + ... + α nn'
kn + γ 'n (mod m)
⎩
Let’s consider (α 1' j ,..., α nj' , m) = d j , j ∈1, n . We’ll prove that for k j it would be sufficient
m m
to only give the values 0, 1, 2,..., − 1 ; for k j = − 1 + β ' with β ' ≥ 1 we obtain
dj dj
m
kj = + β with β ≥ 0 ; β ', β ∈Z .
dj
α ' k j = α ij'' d j k j = α ij'' m + α ij'' d j β ≡ α ij'' d j β (mod m) ; we denoted α ' = α ij'' d j because d j | α ' .
ij ij ij

m
We make the notation m = d j m j , m j = .
dj
Let’s consider η ∈Z , 0 ≤ η ≤ m − 1 such that η = α ij'' d j β (mod d j m j ) ; it results d j | η .
Therefore η = d jγ with 0 ≤ γ ≤ m j −1 because we have that
d j γ ≡ α ij'' d j (mod d j m j ) , which is equivalent to γ ≡ α ij'' β (mod m j ) .
{ }
Therefore ∀k j ∈N, ∃γ ∈ 0,1, 2,..., m j −1 : α 'ij k j ≡ d jγ (mod m) ;
analogously, if the parameter k j ∈ Z . Therefore k j takes values from 0, 1, 2,... to at
most m j − 1; j ∈1, n .
Through this parameterization for each k j in (**), we obtain the solutions of the
n −1
linear congruence. We eliminate the repetitive solutions. We obtain exactly d ⋅ m
distinct solutions.
Example 1. Let’s resolve the following linear congruence:

3
 2x + 7y − 6z ≡ −3(mod 4)
Solution: 7 ≡ 3(mod 4) , −6 ≡ 2(mod 4) , −3 ≡ 1(mod 4) .
It results that 2x + 3y + 2z ≡ 1(mod 4) ; (2, 3, 2, 4) = 1 | 1 therefore the congruence has
solutions and it has 1⋅ 4 3−1 = 16 distinct solutions.
The equation 2x + 3y + 2z − 4t = 1 resolved in integer numbers, has the general
solution:
⎧ x = 3k1 − k2 − 2k3 − 1 ≡ 3k1 + 3k2 + 2k3 + 3(mod 4)
⎪
⎨ y = −2k1 + 1 ≡ 2k1 + 1(mod 4)
⎪z = ≡ (mod 4)
⎩ k2 k2
k j are parameters ∈ Z , j = 1, 3 .
(We did not write the expression for t , because it doesn’t interest us).
We assign values to the parameters. k j takes values from 0 to at most m j − 1 ;
m 4 4
k3 takes values from 0 to m3 − 1 = −1= − 1 = − 1 = 1;
d3 (2, 0, 0) 2
⎛ x ≡ 3k1 + 3k2 + 3(mod 4) ⎞
⎜ ⎟
k3 = 0 ⇒ ⎜ y ≡ 2k1 + 1(mod 4) ⎟ ;
⎜z ≡ k2 (mod 4) ⎟⎠
⎝

⎛ 3k1 + 3k2 + 1⎞
⎜ ⎟
k3 = 1 ⇒ ⎜ 2k1 +1⎟
⎜ k2 ⎟⎠
⎝
k1 takes values from 0 to at most 3.
⎛ 3k2 + 3 ⎞ ⎛ 3k2 + 1 ⎞ ⎛ 3k2 + 2 ⎞ ⎛ 3k2 ⎞
⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
k1 = 0 ⇒ ⎜ 1⎟ , ⎜ 1⎟ ; k1 = 1 ⇒ ⎜ 3⎟ , ⎜ 3 ⎟ ;
⎜ k ⎟ ⎜ ⎟ ⎜ k ⎟ ⎜ k ⎟
⎝ 2 ⎠ ⎝ k2 ⎠ ⎝ 2 ⎠ ⎝ 2⎠
for k1 = 2 and 3 we obtain the same expressions as for k1 = 1 and 0.
k2 takes values from 0 to at most 3.

⎛ 3⎞ ⎛1 ⎞ ⎛ 2⎞ ⎛ 0⎞ ⎛1 ⎞ ⎛ 3⎞ ⎛ 0⎞ ⎛ 2⎞
k2 = 0 ⇒ ⎜ 1 ⎟ , ⎜1 ⎟ , ⎜ 3⎟ , ⎜ 3⎟ ; k2 = 2 ⇒ ⎜ 1 ⎟ , ⎜1 ⎟ , ⎜ 3⎟ , ⎜ 3⎟ ;
⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
⎝ 0⎠ ⎝ 0⎠ ⎝ 0⎠ ⎝ 0⎠ ⎝ 2⎠ ⎝ 2⎠ ⎝ 2⎠ ⎝ 2⎠
⎛ 2 ⎞ ⎛ 0 ⎞ ⎛ 1 ⎞ ⎛ 3⎞ ⎛ 0⎞ ⎛ 2⎞ ⎛ 3⎞ ⎛1⎞
k2 = 1 ⇒ ⎜ 1 ⎟ , ⎜ 1 ⎟ , ⎜ 3⎟ , ⎜ 3⎟ ; k2 = 3 ⇒ ⎜1 ⎟ , ⎜1 ⎟ , ⎜ 3⎟ , ⎜ 3⎟ ;
⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
⎝1 ⎠ ⎝1 ⎠ ⎝1⎠ ⎝1⎠ ⎝ 3⎠ ⎝ 3⎠ ⎝ 3⎠ ⎝ 3⎠
which represent all distinct solutions of the congruence.

4
 Remark 2. By simplification or amplification of the congruence (the division or
multiplication with a number ≠ 0, 1, − 1 ), which affects also the module, we lose
solutions, respectively foreign solutions are introduced.

Example 2.

1) The congruence 2 x − 2 y ≡ 6(mod 4) has the solutions

⎛ 3⎞ ⎛ 1 ⎞ ⎛ 0 ⎞ ⎛ 2 ⎞ ⎛ 1 ⎞ ⎛ 3⎞ ⎛ 2 ⎞ ⎛ 0 ⎞
⎜⎝ 0 ⎟⎠ , ⎜⎝ 0 ⎟⎠ , ⎜⎝ 1 ⎟⎠ , ⎜⎝ 1 ⎟⎠ , ⎜⎝ 2 ⎟⎠ , ⎜⎝ 2 ⎟⎠ , ⎜⎝ 3⎟⎠ , ⎜⎝ 3⎟⎠ ;
2) If we would simplify by 2, we would obtain the congruence x − y ≡ 3(mod 2) ,
⎛ 1 ⎞ ⎛ 0⎞
which has the solutions ⎜ ⎟ , ⎜ ⎟ ; therefore we lose solutions.
⎝ 0⎠ ⎝ 1 ⎠
3) If we would amplify with 2, we would obtain the congruence
4 x − 4 y ≡ 12(mod 4) , which has the solutions:
⎛ 3⎞ ⎛ 5 ⎞ ⎛ 7 ⎞ ⎛ 1 ⎞ ⎛ 4 ⎞ ⎛ 6 ⎞ ⎛ 0 ⎞ ⎛ 2 ⎞
⎜⎝ 0 ⎟⎠ , ⎜⎝ 0 ⎟⎠ , ⎜⎝ 0 ⎟⎠ , ⎜⎝ 0 ⎟⎠ , ⎜⎝ 1 ⎟⎠ , ⎜⎝ 1 ⎟⎠ , ⎜⎝ 1 ⎟⎠ , ⎜⎝ 1 ⎟⎠ ,

⎛ 5 ⎞ ⎛ 7 ⎞ ⎛ 1 ⎞ ⎛ 3⎞ ⎛ 6 ⎞ ⎛ 0 ⎞ ⎛ 2 ⎞ ⎛ 4 ⎞
⎜⎝ 2 ⎟⎠ , ⎜⎝ 2 ⎟⎠ , ⎜⎝ 2 ⎟⎠ , ⎜⎝ 2 ⎟⎠ , ⎜⎝ 3⎟⎠ , ⎜⎝ 3⎟⎠ , ⎜⎝ 3⎟⎠ , ⎜⎝ 3 ⎟⎠ ,

⎛ 7⎞ ⎛ 1 ⎞ ⎛ 3 ⎞ ⎛ 5 ⎞ ⎛ 0⎞ ⎛ 2⎞ ⎛ 4 ⎞ ⎛ 6⎞
⎜⎝ 4 ⎟⎠ , ⎜⎝ 4 ⎟⎠ , ⎜⎝ 4 ⎟⎠ , ⎜⎝ 4 ⎟⎠ , ⎜⎝ 5 ⎟⎠ , ⎜⎝ 5 ⎟⎠ , ⎜⎝ 5 ⎟⎠ , ⎜⎝ 5 ⎟⎠ ,

⎛ 1 ⎞ ⎛ 3⎞ ⎛ 5 ⎞ ⎛ 7 ⎞ ⎛ 2 ⎞ ⎛ 4 ⎞ ⎛ 6 ⎞ ⎛ 0 ⎞
⎜⎝ 6 ⎟⎠ , ⎜⎝ 6 ⎟⎠ , ⎜⎝ 6 ⎟⎠ , ⎜⎝ 6 ⎟⎠ , ⎜⎝ 7 ⎟⎠ , ⎜⎝ 7 ⎟⎠ , ⎜⎝ 7 ⎟⎠ , ⎜⎝ 7 ⎟⎠ ;
therefore we introduce foreign solutions.
Remark 3. By the division or multiplication of a congruence with a number
which is prime with the module, without dividing or multiplying the module, we obtain a
congruence which has the same solutions with the initial one.

Example 3. The congruence 2 x + 3y ≡ 2(mod 5) has the same solutions as the

congruence 6 x + 9 y ≡ 6(mod 5) as follows:
⎛ 0 ⎞ ⎛ 2 ⎞ ⎛ 3⎞ ⎛ 4 ⎞ ⎛ 0 ⎞
⎜⎝ 1 ⎟⎠ , ⎜⎝ 1 ⎟⎠ , ⎜⎝ 2 ⎟⎠ , ⎜⎝ 3 ⎟⎠ , ⎜⎝ 4 ⎟⎠ .

§2. PROPERTIES FOR SOLVING SYSTEMS OF LINEAR CONGRUENCES.

In this paragraph we will obtain some interesting theorems regarding the systems
of congruences and then a method of solving them.
Theorem 1. The system of linear congruences:
(1) ai1 x1 + ... + ain xn ≡ b(mod mi ) , i = 1, r , has solutions if and only if the system of
linear equations:

5
 (2) ai1 x1 + ... + ain xn − mi yi = b , yi unknowns ∈ Z , i = 1, r , has solutions in the set
of integer numbers.
The proof is evident.
Remark 1. From the anterior theorem it results that to solve the system of
congruences (1) is equivalent with solving in integer numbers the system of linear
equations (2).

Theorem 2. (A generalization of the theorem from p. 20, from [1]).

The system of congruences ai x ≡ bi (mod mi ) , mi ≠ 0 , i = 1, r admits solutions if
and only if: (ai , mi ) | bi , i = 1, r and (ai m j , a j mi ) divides ai b j − a j bi , i, j = 1, r .
Poof:
∀i = 1, r , ai x ≡ bi (mod mi ) ⇔ ∀i = 1, r , ai x = bi + mi yi , yi being unknowns
∈Z ; these Diophantine equations, taken separately, have solutions if and only if
(ai , mi )| bi , i = 1, r .
∀i, j = 1, r , from: ai x = bi + yi mi | a j and a j ⋅ x = b j + y j ⋅ m j | ai we obtain:
ai a j ⋅ x = a j bi + a j ⋅ mi yi = ai b j + ai ⋅ m j y j , Diophantine equations which have solution if
and only if (ai m j , a j mi ) | ai b j − a j bi , i, j = 1, r .
Consequence. (We obtain a simpler form for the theorem from p. 20 of [1]). The
system of congruences x ≡ bi (mod mi ) , mi ≠ 0 , i = 1, r has solutions if and only if
(m , m ) | b − b ,
i j i j i, j = 1, r .
Proof:
From theorem 2, ai = 1 , ∀i = 1, r and (1, mi ) = 1 | bi , i = 1, r .

§4. METHOD FOR SOLVING SYSTEMS OF LINEAR CONGRUENCES

Let’s consider the system of linear congruences:

(3) ai1x1 + ai2x2 +…+ ain ≡ bi (mod mi), i = 1, r , the system’s matrix rank being
r < n , aij , bi , mi ∈ Z , mi ≠ 0, i = 1, r , j = 1, n .
According to §1 from this chapter, we can consider:
(*) 0 ≤ aij ≤ mi − 1 , 0 ≤ bi ≤ mi − 1 , ∀i = 1, r , j = 1, n . From the theorem 1 and
the remark 1 it results that, to solve this system of congruences is equivalent with solving
in integer numbers the system of equations:
(4) ai1 x1 + ... + ain xn − mi yi = bi , i = 1, r , the system’s matrix rank being r < n .
Using the algorithm from [2], we obtain the general solution of this system:

6
 ⎧ x1 = α11k1 + ... + α1n kn + β1
⎪.........................................
⎪
⎪ xn = α n1k1 + ... + α nn kn + β n
⎨ y = α k + ... + α
⎪ 1 n + 1,1 1 n + 1, n kn + β n + 1

⎪...........................................
⎪
⎪⎩ yr = α n + r ,1k1 + ... + α n + r , n kn + β n + r
α hj , βh ∈ Z and k j are parameters ∈Z .

Let’s consider m = [ m1 ,..., mr ] > 0 ; because the variables y1 ,..., yr don’t interest us, we’ll
retain only the expressions of x1 ,..., xn .
Therefore:
(5) xi = α i1k1 + ... + α in kn + βi , i = 1, n and again we can suppose that
(**) 0 ≤ α hj ≤ m − 1 , 0 ≤ β h ≤ m − 1 , h = 1, n , j = 1, n .
We have: xi ≡ α i1k1 + ... + α in kn + βi (mod m ) , i = 1, n . Evidently k j takes the
values of at most the integer numbers from 0 to m − 1 . Conform to the same observations
m
from §1 from this chapter, for k j it is sufficient to give only the values 0,1, 2,..., − 1
dj
where
(***) d j = (α1 j ,..., α nj , m ) , for any j = 1, n .
By the parameterization of k1 ,..., kn in (5) we obtain all the solutions of the system of
m
linear congruence (1); k j takes at most the values 0,1, 2,..., − 1 ; we eliminate the
dj
repeating solutions.
Remark 2. The considerations (*), (**), and (***) have the roll of making the
calculation easier, to reduce the computational volume. This algorithm of solving the
linear congruence works also without these considerations, but it is more difficult.

Example. Let’s solve the following system of linear congruences:

⎧3x + 7 y − z ≡ 2(mod 2)
(6) ⎨
⎩ 5 y − 2 z ≡ 1(mod 3)
Solution: The system of linear congruences (6) is equivalent with:
⎧ x + y + z ≡ 0(mod 2)
(7) ⎨
⎩ 2 y + z ≡ 1(mod 3)
which is equivalent with the system of linear equations:
⎧ x + y + z − 2t1 = 0
(8) ⎨
⎩ 2 y + z − 3t 2 = 1
x, y, z , t1 , t2 unknowns ∈ Z
This has the general solution (see [2]):

7
 ⎧ x = −2k1 + 2k2 + 3k3 + 1
⎪y = k − 3k3 − 1
⎪⎪ 1

⎨ z = k1
⎪t = k2
⎪1
⎪⎩t2 = k3
where k1 , k2 , k3 are parameters ∈Z .
The values of t1 and t 2 don’t interest us; m = [2, 3] = 6 . Therefore:
⎧ x ≡ 4 k1 + 2 k2 + 3k3 + 1(mod 6)
⎪
⎨ y ≡ k1 + 3k3 + 5(mod 6)
⎪z ≡ k
⎩ 1 (mod 6)
6
k3 takes values from 0 to − 1 = 1 ; k2 from 0 to 2; k1 from 0 to at most 5.
(3, 3, 0, 6)
⎛ x ≡ 4 k1 + 2 k2 + 1(mod 6)⎞
k3 = 0 ⇒ ⎜ y ≡ k1 + 5(mod 6)⎟ ;
⎜ ⎟
⎝ z ≡ k1 (mod 6) ⎠
⎛ 4 k1 + 2 k2 + 4 ⎞
k3 = 1 ⇒ ⎜ k1 +2⎟ ;
⎜ ⎟
⎝ k1 ⎠
⎛ 4 k1 + 1 ⎞ ⎛ 4 k1 + 4 ⎞ ⎛ 4 k1 + 3⎞ ⎛ 4 k1 ⎞ ⎛ 4 k1 + 5 ⎞ ⎛ 4 k1 + 2 ⎞
k2 = 0,1, 2 ⇒ ⎜ k1 + 5 ⎟ , ⎜ k + 2⎟, ⎜ k + 5⎟ , ⎜ k + 2⎟ , ⎜ k + 5⎟ , ⎜ k + 2⎟ ;
⎜ ⎟ ⎜ 1 ⎟ ⎜ 1 ⎟ ⎜ 1 ⎟ ⎜ 1 ⎟ ⎜ 1 ⎟
⎝ k1 ⎠ ⎝ k1 ⎠ ⎝ k1 ⎠ ⎝ k1 ⎠ ⎝ k1 ⎠ ⎝ k1 ⎠

k1 = 0,1, 2, 3, 4,5 ⇒
⎛1 ⎞ ⎛ 4⎞ ⎛ 3⎞ ⎛ 0⎞ ⎛ 5⎞ ⎛ 2⎞ ⎛ 5⎞ ⎛ 2⎞ ⎛1 ⎞ ⎛ 4⎞ ⎛ 3⎞ ⎛ 0⎞
⎜ 5⎟ , ⎜ 2⎟ , ⎜ 5⎟ , ⎜ 2⎟ , ⎜ 5⎟ , ⎜ 2⎟ , ⎜ 0⎟ , ⎜ 3⎟ , ⎜ 0⎟ , ⎜ 3⎟ , ⎜ 0⎟ , ⎜ 3⎟ ,
⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
⎝ 0⎠ ⎝ 0⎠ ⎝ 0⎠ ⎝ 0⎠ ⎝ 0⎠ ⎝ 0⎠ ⎝1 ⎠ ⎝1 ⎠ ⎝1 ⎠ ⎝1 ⎠ ⎝1 ⎠ ⎝1 ⎠
⎛ 3⎞ ⎛ 0⎞ ⎛ 5⎞ ⎛ 2⎞ ⎛1 ⎞ ⎛ 4⎞ ⎛1 ⎞ ⎛ 4⎞ ⎛ 3⎞ ⎛ 0⎞ ⎛ 5⎞ ⎛ 2⎞
⎜1 ⎟ , ⎜ 4⎟ , ⎜1 ⎟ , ⎜ 4⎟ , ⎜1 ⎟ , ⎜ 4⎟ , ⎜ 2⎟ , ⎜ 5⎟ , ⎜ 2⎟ , ⎜ 5⎟ , ⎜ 2⎟ , ⎜ 5⎟ ,
⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
⎝ 2⎠ ⎝ 2⎠ ⎝ 2⎠ ⎝ 2⎠ ⎝ 2⎠ ⎝ 2⎠ ⎝ 3⎠ ⎝ 3⎠ ⎝ 3⎠ ⎝ 3⎠ ⎝ 3⎠ ⎝ 3⎠
⎛ 5⎞ ⎛ 2⎞ ⎛1 ⎞ ⎛ 4⎞ ⎛ 3⎞ ⎛ 0⎞ ⎛ 3⎞ ⎛ 0⎞ ⎛ 5⎞ ⎛ 2⎞ ⎛1 ⎞ ⎛ 4⎞
⎜ 3⎟ , ⎜ 0⎟ , ⎜ 3⎟ , ⎜ 0⎟ , ⎜ 3⎟ , ⎜ 0⎟ , ⎜ 4⎟ , ⎜1 ⎟ , ⎜ 4⎟ , ⎜1 ⎟ , ⎜ 4⎟ , ⎜1 ⎟ ;
⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟
⎝ 4⎠ ⎝ 4⎠ ⎝ 4⎠ ⎝ 4⎠ ⎝ 4⎠ ⎝ 4⎠ ⎝ 5⎠ ⎝ 5⎠ ⎝ 5⎠ ⎝ 5⎠ ⎝ 5⎠ ⎝ 5⎠

which constitute the 36 distinct solutions of the system of linear congruences (6).

REFERENTES:

8
 [1] Constantin P. Popovici – “Curs de teoria numerelor”, EDP, Bucureşti,
1973.
[2] Florentin Smarandache – “Integer algorithms to solve linear equations and
systems”, Ed. Scientifique, Casablanca, 1984.

[Published in “Gamma”, Year X, Nos. 1-2, October 1987.]

View publication stats