Cryptography Reference
In-Depth Information
Definition
Let
m
be a positive integer, and
a
and
b
integers. If
m
|(
a
b
), we say that
a
is congru-
ent to
b
modulo
m
, and write
a
b
(mod
m
). If
m
(
a
b
), we say that
a
and
b
are
incongruent modulo
m
(or not congruent modulo
m
), and write
a
b
(mod
m
).
E
XAMPLES
.
Note the following:
• 23
2 (mod 7), since 7 divides 23
2 = 21.
• 45
7 (mod 13), since 13|(45
(
7) = 52).
• 10
100 modulo 4, since 4
(10
100) =
90.
The following will help us solve linear congruences by allowing us to express them as
equations.
PROPOSITION 17.
Integers
a
and
b
are congruent modulo
m
iff
∃
an integer
k
such that
a
=
b
+
km
.
Proof.
a
b
(mod
m
) iff
m
|(
a
b
) iff
∃
an integer
k
with
a
b
=
km
, or
a
=
b
+
km
.
E
XAMPLE
.
75
3 (mod 8)
iff
8|(75
3)
iff
8
k
= 75
3 for some integer
k
k
k
iff
75 = 8
+ 3 for some integer
iff
k
= 7.
Congruences have many properties similar to equations. Some of these follow in the
next proposition, and you should easily be able to prove all of them.
PROPOSITION 18.
Let
a
,
b
and
c
be integers, and let
m
be a positive integer. Then
a.
a
a
(mod
m
).
b.
a
b
(mod
m
) implies
b
a
(mod
m
).
c.
a
b
(mod
m
) and
b
c
(mod
m
) implies
a
c
(mod
m
).
Search WWH ::
Custom Search