Theorem 2.5 tells us that since gcd(5, 6) = 1, we may cancel the common

factor of 5 from both sides of (2.4), obtaining 2 ≡ ’4 (mod 6), which one

can also verify directly.

Next observe that

3 · 5 ≡ 3 · 3 (mod 6). (2.5)

We cannot simply cancel the common factor of 3 from both sides of (2.5);

2.2 Solving linear congruences 17

indeed, 5 ≡ 3 (mod 6). However, gcd(3, 6) = 3, and as Theorem 2.5 guaran-

tees, we do indeed have 5 ≡ 3 (mod 2). 2

Next, we consider the problem of determining the solutions z to congru-

ences of the form az + c ≡ b (mod n), for given integers a, b, c, n. Since

we may both add and subtract c from both sides of a congruence modulo

n, it is clear that z is a solution to the above congruence if and only if

az ≡ b ’ c (mod n). Therefore, it su¬ces to consider the problem of deter-

mining the solutions z to congruences of the form az ≡ b (mod n), for given

integers a, b, n.

Theorem 2.6. Let a, b, n ∈ Z with n > 0. If a is relatively prime to n, then

the congruence az ≡ b (mod n) has a solution z; moreover, any integer z is

a solution if and only if z ≡ z (mod n).

Proof. The integer z := ba , where a is a multiplicative inverse of a modulo

n, is clearly a solution. For any integer z , we have az ≡ b (mod n) if

and only if az ≡ az (mod n), which by Theorem 2.5 holds if and only if

z ≡ z (mod n). 2

Suppose that a, b, n ∈ Z with n > 0, a = 0, and gcd(a, n) = 1. This

theorem says that there exists a unique integer z satisfying

az ≡ b (mod n) and 0 ¤ z < n.

Setting s := b/a ∈ Q, we may generalize the “mod” operation, de¬ning

s mod n to be this value z. As the reader may easily verify, this de¬nition

of s mod n does not depend on the particular choice of fraction used to

represent the rational number s. With this notation, we can simply write

a’1 mod n to denote the unique multiplicative inverse of a modulo n that

lies in the interval 0, . . . , n ’ 1.

Theorem 2.6 may be generalized as follows:

Theorem 2.7. Let a, b, n ∈ Z with n > 0, and let d := gcd(a, n). If d | b,

then the congruence az ≡ b (mod n) has a solution z, and any integer z is

also a solution if and only if z ≡ z (mod n/d). If d b, then the congruence

az ≡ b (mod n) has no solution z.

Proof. For the ¬rst statement, suppose that d | b. In this case, by Theo-

rem 2.5, we have az ≡ b (mod n) if and only if (a/d)z ≡ (b/d) (mod n/d),

and so the statement follows immediately from Theorem 2.6, and the fact

that a/d and n/d are relatively prime.

For the second statement, we show that if az ≡ b (mod n) for some

18 Congruences

integer z, then d must divide b. To this end, assume that az ≡ b (mod n)

for some integer z. Then since d | n, we have az ≡ b (mod d). However,

az ≡ 0 (mod d), since d | a, and hence b ≡ 0 (mod d); that is, d | b. 2

Example 2.3. The following table illustrates what the above theorem says

for n = 15 and a = 1, 2, 3, 4, 5, 6.

z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

2z mod 15 0 2 4 6 8 10 12 14 1 3 5 7 9 11 13

3z mod 15 0 3 6 9 12 0 3 6 9 12 0 3 6 9 12

4z mod 15 0 4 8 12 1 5 9 13 2 6 10 14 3 7 11

5z mod 15 0 5 10 0 5 10 0 5 10 0 5 10 0 5 10

6z mod 15 0 6 12 3 9 0 6 12 3 9 0 6 12 3 9

In the second row, we are looking at the values 2z mod 15, and we see

that this row is just a permutation of the ¬rst row. So for every b, there

exists a unique z such that 2z ≡ b (mod 15). We could have inferred this

fact from the theorem, since gcd(2, 15) = 1.

In the third row, the only numbers hit are the multiples of 3, which

follows from the theorem and the fact that gcd(3, 15) = 3. Also note that

the pattern in this row repeats every ¬ve columns; that is also implied by

the theorem; that is, 3z ≡ 3z (mod 15) if and only if z ≡ z (mod 5).

In the fourth row, we again see a permutation of the ¬rst row, which

follows from the theorem and the fact that gcd(4, 15) = 1.

In the ¬fth row, the only numbers hit are the multiples of 5, which follows

from the theorem and the fact that gcd(5, 15) = 5. Also note that the

pattern in this row repeats every three columns; that is also implied by the

theorem; that is, 5z ≡ 5z (mod 15) if and only if z ≡ z (mod 3).

In the sixth row, since gcd(6, 15) = 3, we see a permutation of the third

row. The pattern repeats after ¬ve columns, although the pattern is a

permutation of the pattern in the third row. 2

Next, we consider systems of linear congruences with respect to moduli

that are relatively prime in pairs. The result we state here is known as the

Chinese remainder theorem, and is extremely useful in a number of contexts.

Theorem 2.8 (Chinese remainder theorem). Let n1 , . . . , nk be pairwise

relatively prime, positive integers, and let a1 , . . . , ak be arbitrary integers.

Then there exists an integer z such that

z ≡ ai (mod ni ) (i = 1, . . . , k).

2.2 Solving linear congruences 19

Moreover, any other integer z is also a solution of these congruences if and

only if z ≡ z (mod n), where n := k ni .

i=1

k

Proof. Let n := i=1 ni , as in the statement of the theorem. Let us also

de¬ne

ni := n/ni (i = 1, . . . , k).

From the fact that n1 , . . . , nk are pairwise relatively prime, it is clear that

gcd(ni , ni ) = 1 for i = 1, . . . , k. Therefore, let

mi := (ni )’1 mod ni and wi := ni mi (i = 1, . . . , k).

By construction, one sees that for i = 1, . . . , k, we have

wi ≡ 1 (mod ni )

and

wi ≡ 0 (mod nj ) for j = 1, . . . , k with j = i.

That is to say, for i, j = 1, . . . , k, we have wi ≡ δij (mod nj ), where

1 if i = j,

δij :=

0 if i = j.

Now de¬ne

k

z := wi ai .

i=1

One then sees that

k k

z≡ wi ai ≡ δij ai ≡ aj (mod nj ) for j = 1, . . . , k.

i=1 i=1

Therefore, this z solves the given system of congruences.

Moreover, if z ≡ z (mod n), then since ni | n for i = 1, . . . , k, we see that

z ≡ z ≡ ai (mod ni ) for i = 1, . . . , k, and so z also solves the system of

congruences.

Finally, if z solves the system of congruences, then z ≡ z (mod ni )

for i = 1, . . . , k. That is, ni | (z ’ z) for i = 1, . . . , k. Since n1 , . . . , nk

are pairwise relatively prime, this implies that n | (z ’ z), or equivalently,

z ≡ z (mod n). 2

Example 2.4. The following table illustrates what the above theorem says

for n1 = 3 and n2 = 5.

20 Congruences

z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

z mod 3 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2

z mod 5 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4

We see that as z ranges from 0 to 14, the pairs (z mod 3, z mod 5) range

over all pairs (a1 , a2 ) with a1 ∈ {0, 1, 2} and a2 ∈ {0, . . . , 4}, with every pair

being hit exactly once. 2

Exercise 2.8. Let a1 , . . . , ak , n, b be integers with n > 0, and let d :=

gcd(a1 , . . . , ak , n). Show that the congruence

a1 z1 + · · · + ak zk ≡ b (mod n)

has a solution z1 , . . . , zk if and only if d | b.

Exercise 2.9. Find an integer z such that z ≡ ’1 (mod 100), z ≡

1 (mod 33), and z ≡ 2 (mod 7).

Exercise 2.10. If you want to show that you are a real nerd, here is an

age-guessing game you might play at a party. First, prepare 2 cards as