Cryptography Reference
In-Depth Information
may not be possible to divide two arbitrarily chosen elements. For example, in the
ring
Z
,
+
,
·
it is possible to divide 6 by 2, but it is not possible to divide 2 by 3.
such
that
b
=
ac
. Alternatively speaking,
a
is a
divisor
of
b
and
b
is said to be a
multiple
of
a
. In the examples given earlier 2
For
a, b
∈
Z
, we say that
a
divides
b
, denoted as
a
|
b
, if there exists a
c
∈
Z
3, but 3 does not divide 2.
Also, 1 divides every integer and the largest divisor of any integer
a
|
6, because 6=2
·
∈
Z
\{
0
}
is
|
a
|
.
Furthermore, every integer
a
divides 0; thus 0 has no largest divisor. Theorem
3.2 enumerates some rules that can be used to compute with divisors.
∈
Z
Theorem 3.2
Fo r a l l
a, b, c, d, e
∈
Z
, the following rules apply:
1.
If
a
|
b
and
b
|
c
,then
a
|
c
.
2.
If
a
|
b
,then
ac
|
bc
for all
c
.
3.
If
c
|
a
and
c
|
b
,then
c
|
da
+
eb
for all
d
and
e
.
4.
If
a
|
b
and
b
=0
,then
|
a
|≤|
b
|
.
5.
If
a
|
b
and
b
|
a
,then
|
a
|
=
|
b
|
.
Proofs.
1. If
a
with
b
=
af
and
c
=
bg
. Consequently,
we can write
c
=
bg
=(
af
)
g
=
a
(
fg
) to express
c
as a multiple of
a
.The
claim (i.e.,
a
|
b
and
b
|
c
, then there exist
f, g
∈
Z
|
c
) follows directly from this equation.
2. If
a
with
b
=
af
. Consequently, we can write
bc
=(
af
)
c
=
f
(
ac
) to express
bc
as a multiple of
ac
. The claim (i.e.,
ac
|
b
, then there exists
f
∈
Z
|
bc
)
follows directly from this equation.
3. If
c
with
a
=
fc
and
b
=
gc
. Consequently,
we can write
da
+
eb
=
df c
+
egc
=(
df
+
eg
)
c
to express
da
+
eb
as
a multiple of
c
. The claim (i.e.,
c
|
a
and
c
|
b
, then there exist
f, g
∈
Z
|
da
+
eb
) follows directly from this equation.
4. If
a
|
b
and
b
=0, then there exists 0
=
f
∈
Z
with
b
=
af
. Consequently,
|
b
|
=
|
af
|≥|
a
|
and the claim (i.e.,
|
a
|≤|
b
|
) follows immediately.
5. Let us assume that
a
|
b
and
b
|
a
.If
a
=0then
b
=0, and vice versa. If
a, b
=0,
then it follows from 4. that
|
a
|≤|
b
|
and
|
b
|≤|
a
|
, and hence
|
b
|
=
|
a
|
.
Theorem 3.3 elaborates on the division operation and is commonly known as
Euclid's division theorem for integers. We don't prove the theorem in this topic.
