d = a1 s1 + · · · + ak sk .

Exercise 1.22. Show that for all integers a, b, we have

gcd(a + b, lcm(a, b)) = gcd(a, b).

12 Basic properties of the integers

Exercise 1.23. Show that for integers c, a1 , . . . , ak , we have

gcd(ca1 , . . . , cak ) = |c| gcd(a1 , . . . , ak ).

2

Congruences

This chapter introduces the basic properties of congruences modulo n, along

with the related notion of congruence classes modulo n. Other items dis-

cussed include the Chinese remainder theorem, Euler™s phi function, arith-

metic functions and M¨bius inversion, and Fermat™s little theorem.

o

2.1 De¬nitions and basic properties

For positive integer n, and for a, b ∈ Z, we say that a is congruent to

b modulo n if n | (a ’ b), and we write a ≡ b (mod n). If n (a ’ b),

then we write a ≡ b (mod n). The relation a ≡ b (mod n) is called a

congruence relation, or simply, a congruence. The number n appearing

in such congruences is called the modulus of the congruence. This usage of

the “mod” notation as part of a congruence is not to be confused with the

“mod” operation introduced in §1.1.

A simple observation is that a ≡ b (mod n) if and only if there exists an

integer c such that a = b + cn. From this, and Theorem 1.4, the following

is immediate:

Theorem 2.1. Let n be a positive integer. For every integer a, there exists

a unique integer b such that a ≡ b (mod n) and 0 ¤ b < n, namely, b :=

a mod n.

If we view the modulus n as ¬xed, then the following theorem says that

the binary relation “· ≡ · (mod n)” is an equivalence relation on the set Z:

Theorem 2.2. Let n be a positive integer. For all a, b, c ∈ Z, we have:

(i) a ≡ a (mod n);

(ii) a ≡ b (mod n) implies b ≡ a (mod n);

(iii) a ≡ b (mod n) and b ≡ c (mod n) implies a ≡ c (mod n).

13

14 Congruences

Proof. For (i), observe that n divides 0 = a ’ a. For (ii), observe that if n

divides a ’ b, then it also divides ’(a ’ b) = b ’ a. For (iii), observe that if

n divides a ’ b and b ’ c, then it also divides (a ’ b) + (b ’ c) = a ’ c. 2

A key property of congruences is that they are “compatible” with integer

addition and multiplication, in the following sense:

Theorem 2.3. For all positive integers n, and all a, a , b, b ∈ Z, if a ≡

a (mod n) and b ≡ b (mod n), then

a + b ≡ a + b (mod n)

and

a · b ≡ a · b (mod n).

Proof. Suppose that a ≡ a (mod n) and b ≡ b (mod n). This means that

there exist integers c and d such that a = a + cn and b = b + dn. Therefore,

a + b = a + b + (c + d)n,

which proves the ¬rst congruence of the theorem, and

a b = (a + cn)(b + dn) = ab + (ad + bc + cdn)n,

which proves the second congruence. 2

Theorems 2.2 and 2.3 allow one to work with congruence relations mod-

ulo n much as one would with ordinary equalities: one can add to, subtract

from, or multiply both sides of a congruence modulo n by the same integer;

also, if x is congruent to y modulo n, one may substitute y for x in any sim-

ple arithmetic expression (more precisely, any polynomial in x with integer

coe¬cients) appearing in a congruence modulo n.

Example 2.1. Observe that

3 · 5 ≡ 1 (mod 7). (2.1)

Using this fact, let us ¬nd the set of solutions z to the congruence

3z + 4 ≡ 6 (mod 7). (2.2)

Suppose that z is a solution to (2.2). Subtracting 4 from both sides of (2.2),

we see that

3z ≡ 2 (mod 7). (2.3)

Now, multiplying both sides of (2.3) by 5, and using (2.1), we obtain

z ≡ 1 · z ≡ (3 · 5) · z ≡ 2 · 5 ≡ 3 (mod 7).

2.2 Solving linear congruences 15

Thus, if z is a solution to (2.2), we must have z ≡ 3 (mod 7); conversely,

one can verify that if z ≡ 3 (mod 7), then (2.2) holds. We conclude that

the integers z that are solutions to (2.2) are precisely those integers that are

congruent to 3 modulo 7, which we can list as follows:

. . . , ’18, ’11, ’4, 3, 10, 17, 24, . . . 2

In the next section, we shall give a systematic treatment of the problem

of solving linear congruences, such as the one appearing in the previous

example.

Exercise 2.1. Let x, y, n ∈ Z with n > 0 and x ≡ y (mod n). Also, let

a0 , a1 , . . . , ak be integers. Show that

a0 + a1 x + · · · + ak xk ≡ a0 + a1 y + · · · + ak y k (mod n).

Exercise 2.2. Let a, b, n, n ∈ Z with n > 0 and n | n. Show that if

a ≡ b (mod n), then a ≡ b (mod n ).

Exercise 2.3. Let a, b, n, n ∈ Z with n > 0, n > 0, and gcd(n, n ) = 1.

Show that if a ≡ b (mod n) and a ≡ b (mod n ), then a ≡ b (mod nn ).

Exercise 2.4. Let a, b, n ∈ Z such that n > 0 and a ≡ b (mod n). Show

that gcd(a, n) = gcd(b, n).

Exercise 2.5. Prove that for any prime p and integer x, if x2 ≡ 1 (mod p)

then x ≡ 1 (mod p) or x ≡ ’1 (mod p).

Exercise 2.6. Let a be a positive integer whose base-10 representation is

a = (ak’1 · · · a1 a0 )10 . Let b be the sum of the decimal digits of a; that is, let

b := a0 + a1 + · · · + ak’1 . Show that a ≡ b (mod 9). From this, justify the

usual “rules of thumb” for determining divisibility by 9 and 3: a is divisible

by 9 (respectively, 3) if and only if the sum of the decimal digits of a is

divisible by 9 (respectively, 3).

Exercise 2.7. Show that there are 14 distinct, possible, yearly (Gregorian)

calendars, and show that all 14 calendars actually occur.

2.2 Solving linear congruences

For a positive integer n, and a ∈ Z, we say that a ∈ Z is a multiplicative

inverse of a modulo n if aa ≡ 1 (mod n).

Theorem 2.4. Let a, n ∈ Z with n > 0. Then a has a multiplicative inverse

modulo n if and only if a and n are relatively prime.

16 Congruences

Proof. This follows immediately from Theorem 1.6: a and n are relatively

prime if and only if there exist s, t ∈ Z such that as + nt = 1, if and only if

there exists s ∈ Z such that as ≡ 1 (mod n). 2

Note that the existence of a multiplicative inverse of a modulo n depends

only on the value of a modulo n; that is, if b ≡ a (mod n), then a has an

inverse if and only if b does. Indeed, by Theorem 2.3, if b ≡ a (mod n), then

for any integer a , aa ≡ 1 (mod n) if and only if ba ≡ 1 (mod n). (This

fact is also implied by Theorem 2.4 together with Exercise 2.4.)

We now prove a simple “cancellation law” for congruences:

Theorem 2.5. Let a, n, z, z ∈ Z with n > 0. If a is relatively prime to n,

then az ≡ az (mod n) if and only if z ≡ z (mod n). More generally, if

d := gcd(a, n), then az ≡ az (mod n) if and only if z ≡ z (mod n/d).

Proof. For the ¬rst statement, assume that gcd(a, n) = 1, and let a be

a multiplicative inverse of a modulo n. Then, az ≡ az (mod n) implies

a az ≡ a az (mod n), which implies z ≡ z (mod n), since a a ≡ 1 (mod n).

Conversely, if z ≡ z (mod n), then trivially az ≡ az (mod n). That proves

the ¬rst statement.

For the second statement, let d = gcd(a, n). Simply from the de¬nition

of congruences, one sees that in general, az ≡ az (mod n) holds if and only

if (a/d)z ≡ (a/d)z (mod n/d). Moreover, since a/d and n/d are relatively

prime (see Exercise 1.9), the ¬rst statement of the theorem implies that

(a/d)z ≡ (a/d)z (mod n/d) holds if and only if z ≡ z (mod n/d). That

proves the second statement. 2

Theorem 2.5 implies that multiplicative inverses modulo n are uniquely

determined modulo n; indeed, if a is relatively prime to n, and if aa ≡ 1 ≡

aa (mod n), then we may cancel a from the left- and right-hand sides of

this congruence, obtaining a ≡ a (mod n).

Example 2.2. Observe that