5Modular arithmetic

IA Numbers and Sets

5.1 Modular arithmetic

Definition

(Modulo)

.

If

a, b ∈ Z

have the same remainder after division by

m

,

i.e. m | (a − b), we say a and b are congruent modulo m, and write

a ≡ b (mod m)

Example.

The check digits of the ISBN (or Hong Kong ID Card Number) are

calculated modulo 11.

Example. 9 ≡ 0 (mod 3), 11 ≡ 6 (mod 5).

Proposition. If a ≡ b (mod m), and d | m, then a ≡ b (mod d).

Proof. a ≡ b

(

mod m

) if and only if

m |

(

a − b

), hence

d |

(

a − b

), i.e.

a ≡ b

(mod d).

Observe that with

m

fixed,

a ≡ b

(

mod m

) is an equivalence relation. The

set of equivalence classes is written as Z

m

or Z/(mZ).

Example. Z

3

= {[0], [1], [2]}

Proposition.

If

a ≡ b

(

mod m

) and

u ≡ v

(

mod m

), then

a

+

u ≡ b

+

v

(mod m) and au ≡ bv (mod m).

Proof.

Since

a ≡ b

(

mod m

) and

u ≡ v

(

mod m

), we have

m |

(

a−b

)+(

u−v

) =

(a + u) − (b + v). So a + u ≡ b + v (mod m)

Since

a ≡ b

(

mod m

) and

u ≡ v

(

mod m

), we have

m |

(

a −b

)

u

+

b

(

u −v

) =

au − bv. So au ≡ bv (mod m).

This means that we can do arithmetic modulo

n

. Formally, we are doing

arithmetic with the congruence classes, i.e

Z

m

. For example, in

Z

7

, [4] + [5] =

[9] = [2].

Modular arithmetic can sometimes be used to show that equations have no

solutions.

Example.

2

a

2

+ 3

b

3

= 1 has no solutions in

Z

. If there were a solution, then

2

a

2

≡

1 (

mod

3). But 2

·

0

2

≡

0, 2

·

1

2

≡

2 and 2

·

2

2

≡

2. So there is no solution

to the congruence, and hence none to the original equation.

Observe that all odd numbers are either

≡

1 (

mod

4) or

≡

3

≡ −

1 (

mod

4).

So we can classify primes depending on their value modulo 4.

Theorem. There are infinitely many primes that are ≡ −1 (mod 4).

Proof.

Suppose not. So let

p

1

, ···p

k

be all primes

≡ −

1 (

mod

4). Let

N

=

4

p

1

p

2

···p

k

−

1. Then

N ≡ −

1 (

mod

4). Now

N

is a product of primes, say

N

=

q

1

q

2

···q

`

. But 2

- N

and

p

i

- N

for all

i

. So

q

i

≡

1 (

mod

4) for all

i

. But

then that implies N = q

1

q

2

···q

`

≡ 1 (mod 4), which is a contradiction.

Example.

Solve 7

x ≡

2 (

mod

10). Note that 3

·

7

≡

1 (

mod

10). If we multiply

the equation by 3, then we get 3

·

7

· x ≡

3

·

2 (

mod

10). So

x ≡

6 (

mod

10).

Effectively, we divided by 7.

“Division” doesn’t always work for all numbers, e.g. you cannot divide by 2

mod 10. We give a name to numbers we can divide.

Definition

(Unit (modular arithmetic))

. u

is a unit if

∃v

such that

uv ≡

1

(mod m).

Theorem. u is a unit modulo m if and only if (u, m) = 1.

Proof.

(

⇒

) Suppose

u

is a unit. Then

∃v

such that

uv ≡

1 (

mod m

). Then

uv

= 1 +

mn

for some

n

, or

uv − mn

= 1. So 1 can be written as a linear

combination of u and m. So (u, m) = 1.

(

⇐

) Suppose that (

u, m

) = 1. Then there exists

a, b

with

ua

+

mb

= 1. Thus

ua ≡ 1 (mod m).

Using the above proof, we can find the inverse of a unit efficiently by Euclid’s

algorithm.

Corollary.

If (

a, m

) = 1, then the congruence

ax ≡ b

(

mod m

) has a unique

solution (mod m).

Proof.

If

ax ≡ b

(

mod m

), and (

a, m

) = 1, then

∃a

−1

such that

a

−1

a ≡

1

(

mod m

). So

a

−1

ax ≡ a

−1

b

(

mod m

) and thus

x ≡ a

−1

b

(

mod m

). Finally we

check that

x ≡ a

−1

b

(

mod m

) is indeed a solution:

ax ≡ aa

−1

b ≡ b

(

mod m

).

Proposition. There is a solution to ax ≡ b (mod m) if and only if (a, m) | b.

If

d

= (

a, m

)

| b

, then the solution is the unique solution to

a

d

x ≡

b

d

(

mod

m

d

)

Proof.

Let

d

= (

a, m

). If there is a solution to

ax ≡ b

(

mod m

), then

m | ax −b

.

So d | ax − b and d | b.

On the contrary, if d | b, we have ax ≡ b (mod m) ⇔ ax − b = km for some

k ∈ Z

. Write

a

=

da

0

,

b

=

db

0

and

m

=

dm

0

. So

ax ≡ b

(

mod m

)

⇔ da

0

x−db

0

=

dkm

0

⇔ a

0

x − b

0

=

km

0

⇔ a

0

x ≡ b

0

(

mod m

0

). Note that (

a

0

, m

0

) = 1 since

we divided by their greatest common factor. Then this has a unique solution

modulo m

0

.

Example.

2

x ≡

3 (

mod

4) has no solution since (2

,

4) = 2 which does not

divide 3.