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.