Solving Congruences – Rosen Section 4.

Anna-Simone Frank1

MNF130

Spring 2024

1
Slides created by Tom Michoel and modified by Erik Maartensson and
Anna-Simone Frank
Relatively prime

Definition
The greatest common divisor of two integers m and n not both zero,
written gcd(m, n), is the largest integer d such that d | m and d | n.

Definition
Two integers m and n are relatively prime if they have no common
positive divisor other than 1, that is, if gcd(m, n) = 1.

Theorem
For a positive integer m and integers a, b, n; if an ≡ bn (mod m) and
gcd(m, n) = 1, then a ≡ b (mod m).

3
Lemma
If a, b, c are positive integers such that gcd(a, b) = 1 and a | bc, then
a | c.

Proof.
I If gcd(a, b) = 1 then there exist integers s, t such that

sa + tb = 1
sac + tbc = c

I We have a | sac, and by the assumption that a | bc also a | tbc.

I Hence a | (sac + tbc) = c.

4
Theorem
For a positive integer m and integers a, b, n; if an ≡ bn (mod m) and
gcd(m, n) = 1, then a ≡ b (mod m).

Proof.
I If an ≡ bn (mod m), then by definition m | (an − bn) = (a − b)n.
I By the previous lemma, gcd(m, n) = 1 and m | (a − b)n implies that
m | (a − b), and hence a ≡ b (mod m).

5
Linear congruences
A linear congruence is an equation

ax ≡ b (mod m) (1)

in an integer variable x, with a positive integer m and integers a, b.

Example
The linear congruence with 2x ≡ 1 (mod 3) has the solution
x ≡ 2 (mod 3).

b b+m b + 2m b + 3m b + 4m b + 5m b + 6m

0 a 2a 3a 4a 5a 6a 7a 8a 9a 10a

Figure 1: Linear congruence with a = 2, b = 1 and m = 3.

6
Inverse modulo m
Definition
An inverse of an integer a modulo m is an integer ā such that
aā ≡ 1 (mod m).
Theorem
If integers a, m are relatively prime, gcd(a, m) = 1, then there exists a
unique inverse of a modulo m.
Proof.
I If gcd(a, m) = 1, then there exist integers s, t such that
sa + tm = 1, and hence sa + tm ≡ 1 (mod m).
I Because tm ≡ 0 (mod m), it follows that sa ≡ 1 (mod m), and s is
an inverse of a modulo m.
I Assume there exists another inverse r of a modulo m. Because
sa ≡ 1 (mod m), there exists q such that sa = qm + 1. Likewise
there exists p such that ra = pm + 1.
I Hence sa − ra = (s − r )a = (q − p)m and m | (s − r )a.
I Because gcd(a, m) = 1 it follows that m | (s − r ), or s ≡ r
(mod m). That is, s is unique modulo m.
7
Inverses modulo prime numbers

Corollary
For a prime p, all integers a, with a 6≡ 0 (mod p) have a modular inverse.
Another way of putting this is that all numbers a ∈ Zp , a 6= 0 have a
multiplicative inverse!

8
Example
Do 7 and 6 have inverses modulo 8?
I Test all possible values for an inverse:
7 mod 8 = 7 6 mod 8 = 6
2 · 7 mod 8 = 6 2 · 6 mod 8 = 4
3 · 7 mod 8 = 5 3 · 6 mod 8 = 2
4 · 7 mod 8 = 4 4 · 6 mod 8 = 0
5 · 7 mod 8 = 3
6 · 7 mod 8 = 2
7 · 7 mod 8 = 1
8 · 7 mod 8 = 0
I Once we reach 0, the numbers repeat.

Intuition
If gcd(a, m) = 1, all values 0 ≤ r < m, including r = 1, are encountered
in this process, but if gcd(a, m) > 1 the process terminates early and
r = 1 is not encountered.
9
How to compute modular inverses?

To compute an inverse of a modulo m:

1. Use the Euclidean algorithm to compute gcd(a, m).

2. If gcd(a, m) = 1, then reverse the steps of the Euclidean algorithm
to write

1 = gcd(a, m) = sa + tm

3. We obtain

ā ≡ s (mod m)

10
Example
We have

8 = 7 + 1 ↔ −1 · 7 = 1 + (−1) · 8.
Thus, -1 and also 7 are inverses of 7 modulo 8. Also, 7−1 = 7 in Z8 .

Example
Let us find the inverse of 101 modulo 4620 (example 2 in Section 4.4.2).
By applying the extended Euclidean algorithm we find that

1 = −35 · 4620 + 1601 · 101 ↔ 1601 · 101 = 1 + 35 · 4620.

Thus 1601 is an inverse of 101 modulo 4620. Also, 101−1 = 1601 in
Z4620 .

11
Theorem
If a has an inverse ā modulo m, then the solutions to the linear
congruence ax ≡ b (mod m) are all integers x such that x ≡ āb
(mod m).

Proof.
I Let x be a solution to ax ≡ b (mod m). Then

āb mod m = (ā mod m)(b mod m) mod m

= (ā mod m)(ax mod m) mod m
= āax mod m
= (āa mod m)(x mod m) mod m
= (x mod m) mod m
= x mod m

or x ≡ āb (mod m)

12
The Chinese remainder theorem

The Chinese remainder theorem states that when the moduli of a

system of linear congruences are pairwise relatively prime, then there is a
unique solution of the system modulo the product of the moduli.

It is named after the Chinese heritage of problems involving systems of

linear congruences.

Example (Sun-Tsu, 1st century)

There are certain things whose number is unknown. When divided by 3,
the remainder is 2; when divided by 5, the remainder is 3; and when
divided by 7, the remainder is 2. What will be the number of things?

13
 The Chinese remainder theorem
er Theory and Cryptography

EM 2 THE CHINESE REMAINDER THEOREM Let m1 , m2 , . . . , mn be pairwise relatively

prime positive integers greater than one and a1 , a2 , . . . , an arbitrary integers. Then the system

x ≡ a1 (mod m1 ),
x ≡ a2 (mod m2 ),
·
·
·
x ≡ an (mod mn )

has a unique solution modulo m = m1 m2 · · · mn . (That is, there is a solution x with

0 ≤ x < m, and all other solutions are congruent modulo m to this solution.)

Proof: To establish this theorem, we need to show that a solution exists and that it is unique
modulo m. We will show that a solution exists by describing a way to construct this solution;
showing that the solution is unique modulo m is Exercise 30.
To construct a simultaneous solution, first let

Mk = m/mk 14
Constructive proof.
Introduce the notation Mk = m/mk . By construction gcd(Mk , mk ) = 1.
Thus there are integers yk such that

Mk yk ≡ 1 (mod mk ). (2)
Now, consider

x = a1 M1 y1 + · · · + an Mn yn . (3)
For all mk we get

x ≡ a1 M1 y1 + · · · + an Mn yn ≡ ak Mk yk ≡ ak (mod mk ) (4)
Thus x is a solution to the system of linear congruences!
The proof that x is unique modulo m is exercise 4.4.30 in the course
book.

15
The Sun-Tsu example

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

We have m = 3 · 5 · 7 = 105, M1 = m/3 = 5 · 7 = 35,

M2 = m/5 = 3 · 7 = 21 and M3 = m/7 = 3 · 5 = 15. Next, the modular
inverses

35y1 ≡ 1 (mod 3)
21y2 ≡ 1 (mod 5)
15y3 ≡ 1 (mod 7)

are y1 ≡ 2 (mod 3), y2 ≡ 1 (mod 5), y3 ≡ 1 (mod 7). Thus, the final
solution is (the solution can easily be verified!)

x = 2 · 35 · 2 + 3 · 21 · 1 + 2 · 15 · 1 = 233 ≡ 23 (mod 105). (5)

16
Applications of the Chinese remainder theorem

Consider the task of evaluating

f (x) mod m, (6)

where m = m1 · · · mn , and all these factors are pairwise relatively prime.
The Chinese remainder theorem says that we can calculate
f (x) mod m1 , . . . , f (x) mod mn and use the results to compute
f (x) mod m.
This is for example used in RSA to speed up the algorithm!

17