Cheenta

IOQM Concepts Revisited

Created By : Topic : Linear

J V Raghunath Congruences - CRT, FLT
IOQM Concepts Revisited J V Raghunath

Overview
We will learn about,
1. Linear Congruences
2. System of Linear Congruences and CRT
3. Fermat’s Little Theorem - FLT

1 Linear Congruences
A Linear Congruence equation is of the form,
ax ≡ b (mod n), for a, b, x ∈ Z and n ∈ N, where x is the variable.
x0 is a solution ⇐⇒ ax0 ≡ b (mod n). We say that two solutions are “equal”
if both are congruent (mod n). For example, 3x ≡ 9 (mod 12), has solutions,
x = . . . , −5, −1, 3, 7, 11, 15, 19, . . .. But many of which are “equal” (mod 12), i.e.,
−5 ≡ 7 ≡ 19 (mod 12). So we say that the number of solutions to be the cardinality
of set of all mutually incongruent solutions (mod 12), that is, 3x ≡ 9 (mod 12), has
3 mutually incongruent solutions {3, 7, 11} (mod 12).
Theorem 1.1. The Linear Congruence ax ≡ b (mod n) has a solution ⇐⇒
d | b, where d = GCD(a, n). If d | b, then it has “d” mutually incongruent
solutions (mod n).

Proof. If ax ≡ b (mod n) =⇒ n | ax − b =⇒ b = ax − nk, for some k ∈ Z. Since

GCD(a, n) divides both a, n =⇒ GCD(a, n) | ax − nk =⇒ d | b.

Conversely suppose if, d | b =⇒ b = sd, for some s ∈ Z. From the Bezout’s Lemma
we know that, there exist w, y ∈ Z, such that, d = GCD(a, n) = aw + ny =⇒ sd =
a(sw) + n(sy) =⇒ n | b − a(w0 ), for some w0 ∈ Z. So aw0 ≡ b (mod n), and hence
there is a solution for the linear congruence.

Now, suppose d | b, then b = ax0 − nk0 , for some x0 , k0 ∈ Z by the preceding

argument. Let us say that there is another solution x1 , so, b = ax1 − nk1 , for
some x1 , k1 ∈ Z. So, ax0 − nk0 = ax1 − nk1 =⇒ a(x0 − x1 ) = n(k0 − k1 ). If
a = da0 , n = dn0 , then a0 (x0 − x1 ) = n0 (k0 − k1 ) =⇒ n0 | a0 (x0 − x1 ). By the
Euclid’s Lemma, since GCD( ad , nd ) = 1 =⇒ n0 | (x0 − x1 ) =⇒ x0 ≡ x1 (mod n0 ).
Also note that conversely, any x ≡ x0 (mod n0 ), is a solution of the congruence be-
cause n0 | (x − x0 ) =⇒ n | ax − ax0 =⇒ ax ≡ ax0 ≡ b (mod n). Hence, the set of
solutions of the linear congruence ax ≡ b (mod n) is the set {x | x ≡ x0 (mod n0 )}.
But to determine the number of solutions, we need the number of incongruent

1
IOQM Concepts Revisited J V Raghunath

solutions (mod n). We know that,

n n n n n
x = . . . , x 0 , x0 + , x0 + 2 , x0 + 3 , · · · , x0 + (d − 2) , x0 + (d − 1) ,
d n d d d d
n
x0 + n, x0 + (d + 1) , . . . , since n0 =
d d
So observe that, there are exactly “d” solutions that are mutually incongruent (mod n),
completing the proof.

Question 1.1. Find the solutions and the number of solutions of the linear
congruence, 18x ≡ 30 (mod 42)
Sol. Note that d = GCD(18, 42) = 6 ; a = 18 ; b = 30 =⇒ d | b, so there is
solution and the number of solutions = d = 6.
18x ≡ 30 (mod 42) =⇒ 3x ≡ 5 (mod 7) =⇒ 3x ≡ 12 (mod 7) =⇒ x ≡
4 (mod 7), is the set of solutions.

Question 1.2. Find the solutions and the number of solutions of the linear
congruence, 9x ≡ 21 (mod 30)
Sol. Note that d = GCD(9, 30) = 3 ; a = 9 ; b = 21 =⇒ d | b, so there is
solution and the number of solutions = d = 3.
9x ≡ 21 (mod 30) =⇒ 3x ≡ 7 (mod 10) =⇒ 3x ≡ −3 (mod 10) =⇒ x ≡
9 (mod 10), is the set of solutions.

2 System of Linear Congruences and CRT

Instead of one congruence equation, suppose you are given with multiple, say r simul-
taneous system of congruence equations and we are interested to find the solutions
and the number of solutions for it. Suppose the congruence equations are,

b1 x ≡ c1 (mod m1 )
b2 x ≡ c2 (mod m2 )
..
.
br x ≡ cr (mod mr )

where m1 , m2 , . . . , mr are mutually coprime. Obviously, each of the congruence

must hold true, otherwise there is no solution, and by the Theorem 1.1, we have
GCD(bi , mi ) | ci , for each i ∈ {1, 2, . . . , r}. If this is true, then we have solutions for

2
IOQM Concepts Revisited J V Raghunath

each congruence written as below,

x ≡ a1 (mod n1 )
x ≡ a2 (mod n2 )
..
.
x ≡ ar (mod nr )
mi
where ni = GCD(bi ,mi )
, which are also mutually co-prime ∀i ∈ {1, . . . , r} since mi ’s
are mutually coprime. Now we use the following Chinese Remainder Theorem, to
understand more about this,
Theorem 2.1 (Chinese Remainder Theorem). Let n1 , n2 , . . . , nr ∈ Z such that
GCD (ni , nj ) = 1 for i ̸= j. Then the system of linear congruences,

x ≡ a1 (mod n1 )
x ≡ a2 (mod n2 )
..
.
x ≡ ar (mod nr )

has a simultaneous solution, which is unique modulo the integer n1 n2 · · · nr .

Proof. We start by forming the product n = n1 n2 · · · nr . For each k = 1, 2, . . . , r,

let
n
Nk = = n1 · · · nk−1 nk+1 · · · nr
nk
In words, Nk is the product of all the integers ni with the factor nk omitted. By
hypothesis, the ni are relatively prime in pairs, so that gcd (Nk , nk ) = 1. According
to the theory of a single linear congruence, it is therefore possible to solve the
congruence Nk x ≡ 1 (mod nk ); call the unique solution xk . Our aim is to prove that
the integer
x̄ = a1 N1 x1 + a2 N2 x2 + · · · + ar Nr xr
is a simultaneous solution of the given system. First, observe that Ni ≡ 0 (mod nk )
for i ̸= k, because nk | Ni in this case. The result is

x̄ = a1 N1 x1 + · · · + ar Nr xr ≡ ak Nk xk (mod nk )

But the integer xk was chosen to satisfy the congruence Nk x ≡ 1 (mod nk ), which
forces
x̄ ≡ ak · 1 ≡ ak (mod nk )

3
IOQM Concepts Revisited J V Raghunath

This shows that a solution to the given system of congruences exists. As for the
uniqueness assertion, suppose that x′ is any other integer that satisfies these con-
gruences. Then
x̄ ≡ ak ≡ x′ (mod nk ) ∀k = 1, 2, . . . , r
and so nk | x̄ − x′ for each value of k. Because gcd (ni , nj ) = 1,
=⇒ n1 n2 · · · nr | x̄ − x′ ; hence x̄ ≡ x′ (mod nk ), completing the proof.

Question 2.1. Solve the linear congruence 17x ≡ 9 (mod 276)

Sol. 276 = 22 × 3 × 23. So,
276 | 17x − 9 ⇐⇒ 22 | 17x − 9 and 3 | 17x − 9 and 23 | 17x − 9, since these
factors are relatively coprime. Hence, we just need to solve the simultaneous
system of congruences,

17x ≡ 9 (mod 4)
17x ≡ 9 (mod 3)
17x ≡ 9 (mod 23)

Firstly, let us solve each of the congruences and after some calculations we
get,

x ≡ 1 (mod 4)
x ≡ 0 (mod 3)
x ≡ 10 (mod 23)

Now, we know by the Chinese Remainder Theorem that there is a unique

solution (mod 276 = 4 × 3 × 23). We just need to find this unique solution
and we are done. For this, list down the numbers that are congruent to
10 (mod 23) and < 276, that is, 10, 33, 56, 79, . . .. Out these numbers, exactly
one satisfy the system of congruences which is 33. Hence x ≡ 33 (mod 276) is
the set of solutions.

4
IOQM Concepts Revisited J V Raghunath

Question 2.2. Solve the following system of linear congruences,

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

It is easily observed that x ≡ 23 (mod 105) is the solution. A rigorous solution

would be to find the solution using the proof of the Chinese Remainder
Theorem.

Remark. Think about the simultaneous system of congruences when the ni ’s

are not mutually coprime. Under what conditions do they have solution(s)
and how many solution(s)?

3 Fermat’s Little Theorem - FLT

Theorem 3.1 (Fermat’s Little Theorem). Let a ∈ Z and p be any prime number,
then
ap ≡ a (mod p)

Proof. We can use induction to prove it, i.e., 1p ≡ 1 (mod p). Suppose, ap ≡
a (mod p), then (a + 1)p = ap + pk1 + 1p , for some k1 ∈ Z, by the Binomial Theorem.
Then, (a + 1)p ≡ ap + 1 ≡ a + 1 (mod p), by the induction hypothesis. Hence,
ap ≡ a (mod p), ∀a ∈ Z by the First principle of Finite Induction.
There is as well another elegant method, which states that if GCD(a, p) ̸= 1 =⇒
p | a =⇒ ap ≡ 0 ≡ a (mod p). If GCD(a, p) = 1, then we can divide by a on both
sides to get, ap−1 ≡ 1 (mod p). Consider the set {a, 2 · a, 3 · a, . . . , (p − 1) · a}, which
is special because none of them is divisible by p and no two of them are congruent
(mod p), because if n1 · a ≡ n2 · a (mod p) =⇒ p | (n1 − n2 ), since GCD(a, p) = 1,
but this not possible unless n1 = n2 , because ni < p. So, we can observe that
the remainder set of {a, 2 · a, 3 · a, . . . , (p − 1) · a} must be {1, 2, 3, . . . , p − 1}, in
some order. Hence, (a) · (2a) · (3a) · · · ((p − 1)a) ≡ 1 · 2 · 3 · · · (p − 1) (mod p) =⇒
(p − 1)! · ap−1 ≡ (p − 1)! (mod p) =⇒ ap−1 ≡ 1 (mod p).

5
IOQM Concepts Revisited J V Raghunath

Question 3.1. Prove that 17 divides 11104 + 1

5
Sol. 1117 ≡ 11 (mod 17), by the Fermat’s Little Theorem. So, (1117 ) ≡
115 (mod 17) =⇒ 11105 ≡ 115 (mod 17) =⇒ 11104 ≡ 114 ≡ (−6)4 ≡ 362 ≡
42 ≡ −1 (mod 17). Hence 17 | 11104 + 1

One can also use the Fermat’s Little Theorem to prove that a number is not a prime.
For example, Let us prove that 117 is not a prime,

16
2117 = 27·16+5 = 27 25

and 27 = 128 ≡ 11 (mod 117), we have

2117 ≡ 1116 · 25 ≡ (121)8 25 ≡ 48 · 25 ≡ 221 (mod 117)

3
But 221 = (27 ) , which leads to

221 ≡ 113 ≡ 121 · 11 ≡ 4 · 11 ≡ 44 (mod 117)

Combining these congruences, we finally obtain

2117 ≡ 44 ̸≡ 2 (mod 117)

So, 117 doesnot follow the Fermat’s Little Theorem and hence it cannot be a prime.
Actually, 117 = 32 × 13.