Cryptography Reference
In-Depth Information
E
XAMPLES
.
Note that 9
2 (mod 7). Then all of the following are true:
• (7 + 9)
(
7 + 2) (mod 7)
Check: (7 + 9)
16
2 (mod 7) and (
7 + 2)
5
2 (mod 7)
• (3
9)
(
4
2) (mod 7)
Check: (3
9)
6
1 (mod 7) and (
4
2)
6
1 (mod 7)
• (3
9)
(
4
9) (mod 7)
Check: (3
9)
27
6 (mod 7) and (
4
2)
8
6 (mod 7)
Note that a similar property for division does not appear in proposition 19 or proposition
20. This is because it isn't true in general. For example, note that 16
4 (mod 12), but that
16/2 = 8 is not congruent modulo 12 to 4/2 = 2. However, if we take the gcd of 12 and 2,
note that 8 and 2 are congruent modulo 6 = 12/(12, 2). This is true in general, and we prove
it thus:
PROPOSITION 21.
Let
a
,
b
, and
c
be integers, and let
m
be a positive integer. Let
d
=
(
c
,
m
), and suppose
ac
bc
(mod
m
). Then
a
b
(mod
m
/
d
).
Proof.
Since
ac
bc
(mod
m
),
m
|(
ac bc
) =
c
(
a b
). Thus, there is an integer
k
such
that
c
(
a b
) =
km
. Divide both sides by
d
to get (
c
/
d
)(
a b
) =
k
(
m
/
d
). Proposition 7 says
c
/
d
and
m
/
d
are relatively prime, so (
m
/
d
)|(
a b
) by proposition 13. Thus,
a
b
(mod
m
/
d
).
A special case occurs in the previous theorem when
c
and
m
are relatively prime, for
then division by the integer
c
preserves the congruence modulo
m
. For example, note that
50
15 (mod 7), and that 50 = 10
5, and 15 = 3
5. Since 5 is relatively prime to the mod-
ulus 7, we can factor it out on both sides of the congruence and still preserve it; that is, 10
3 (mod 7).
E
XAMPLES
.
• 10
4 (mod 3), so
10/2
4/2 (mod 3), or
5
2 (mod 3)
• 30
12 (mod 18), so
30/3
12/3 (mod 18/3), or
10
4 (mod 6).
Search WWH ::
Custom Search