Chapter 18
More Properties of
Congruences
Theorem 18.1.
Let
m
≥
2
. If
a
and
m
are relatively prime, there exists a
unique integer
a
∗
such that
aa
∗
≡
1 (mod
m
)
and
0
< a
∗
< m
.
We call
a
∗
the
inverse of
a
modulo
m
. Note that we do not denote
a
∗
by
a
−
1
since this might cause some confusion.
Of course, if
c
≡
a
∗
(mod
m
)
then
ac
≡
1 (mod
m
) so
a
∗
is not unique unless we specify that 0
< a
∗
< m
.
Proof.
If gcd(
a, m
) = 1, then by Bezout’s Lemma there exist
s
and
t
such
that
as
+
mt
= 1
.
Hence
as
−
1 =
m
(
−
t
)
,
that is,
m

as
−
1 and so
as
≡
1 (mod
m
). Let
a
∗
=
s
mod
m
. Then
a
∗
≡
s
(mod
m
) so
aa
∗
≡
1 (mod
m
) and clearly 0
< a
∗
< m
.
To show uniqueness assume that
ac
≡
1 (mod
m
) and 0
< c < m
. Then
ac
≡
aa
∗
(mod
m
). So if we multiply both sides of this congruence on the
left by
c
and use the fact that
ca
≡
1 (mod
m
) we obtain
c
≡
a
∗
(mod
m
).
It follows from Exercise 15.5 that
c
=
a
∗
.
Remark
18.1
.
From the above proof we see that Blankinship’s Method may
be used to compute the inverse of
a
when it exists, but for small
m
we may
71
72