Cryptography Reference
In-Depth Information
CHAPTER
3
The Integers
In order to understand most of modern cryptography, it is necessary to understand
some number theory. We begin with the divisibility properties of integers.
Definition
If
a
and
b
are integers with
a
≠
0, we say that
a
divides
b
if there is an integer
c
such
that
b
=
ac
. If
a
divides
b
, we also say that
a
is a divisor, or factor, of
b
, and we write
a
|
b
. We also write
a
b
if
a
does not divide
b
.
For example, 3|27, since 27 = 3 · 9. Likewise, 5
32, because there exists no inte-
ger
c
such that 32 = 5
c
.
Using this test, we can find and list the divisors of all nonzero integers. For example, the
divisors of 9 are
1,
3, and
9. The factors of 20 are
1,
2,
4,
5,
10, and
20.
Now, we prove some properties of divisibility.
PROPOSITION 1
If
x
,
y
, and
z
are integers with
x
|
y
and
y
|
z
, then
x
|
z
.
Proof.
Say that integer
x
divides integer
y
, and
y
divides integer
z
. Then
(there exits)
an integer
c
such that
y
=
cx
, and
an integer
d
such that
z
=
dy
. Now, note that
z
=
dy
=
d
(
cx
) = (
dc
)
x
, and that
dc
is likewise an integer. Thus,
x
divides
z
.
E
XAMPLE
.
Note that 3|9, and that 9|72. By the previous theorem, this implies that 3 also
divides 72.
The next theorem is as easy to prove as the previous, and the proof is left to you.
PROPOSITION 2
If
c
,
x
,
y
,
m
, and
n
are integers such that
c
|
x
and
c
|
y
, then
c
|(
mx
+
ny
).
Search WWH ::
Custom Search