Cryptography Reference
In-Depth Information
Theorem 3.3 (Euclid's division theorem)
Fo r a l l
n, d
∈
Z
\{
0
}
there exist unique
and efficiently computable
q, r
∈
Z
such that
n
=
qd
+
r
and
0
≤
r<
|
d
|
.
In this setting,
d
is called the
divisor
(i.e.,
n
is divided by
d
),
q
the
quotient
,and
r
the
remainder
. The remainder
r
can also be written as
R
d
(
n
), and we sometimes
use this notation.
For example,
R
7
(16) = 2 (because 16 = 2
·
7+2),
R
7
(
−
16) = 5 (because
−
25 + 4). Obviously,
R
d
(
n
)=0means that
d
divides
n
(with remainder zero), and hence
d
is a
divisor of
n
.Furthermore,
R
d
(
n
+
id
) is equal to
R
d
(
n
) for all
i
16 =
−
3
·
7+5), and
R
25
(104) = 4 (because 104 = 4
·
∈
Z
, and hence
R
7
(1) =
R
7
(8) =
R
7
(15) =
R
7
(22) =
R
7
(29) =
...
=1.
3.2.2
Common Divisors and Multiples
Two integers can have many common divisors, but only one of them can be the
greatest. Quite naturally, this divisor is called
greatest common divisor
. It is formally
introduced in Definition 3.24.
Definition 3.24 (Common divisors and greatest common divisor)
Fo r
a, b
∈
Z
\
{
b
.Furthermore,
c
is the
greatest common divisor
, denoted
gcd
(
a, b
)
, if it is the largest integer that divides
a
and
b
.
0
}
,
c
∈
Z
is a
common divisor
of
a
and
b
if
c
|
a
and
c
|
Another possibility to define the greatest common divisor of
a
and
b
is to say
that
c
=
gcd
(
a, b
) if any common divisor of
a
and
b
also divides
c
.
gcd
(0
,
0) = 0,
and
gcd
(
a,
0) =
|
a
|
for all
a
∈
Z
\{
0
}
.If
a, b
∈
Z
\{
0
}
,then1
≤
gcd
(
a, b
)
≤
min
). Consequently, the greatest common
divisor of two integers can never be negative (even if one or both integers are
negative). Furthermore, two integers
a, b
{|
a
|
,
|
b
|}
and
gcd
(
a, b
)=
gcd
(
±|
a
|
,
±|
b
|
are
relatively prime
or
co-prime
if their greatest common divisor is 1 (i.e., if
gcd
(
a, b
)=1).
Similar to the (greatest) common divisor, it is possible to define the (least)
common multiple of two integers. This is formally introduced in Definition 3.25.
∈
Z
\{
0
}
Definition 3.25 (Common multiples and least common multiple)
Fo r
a, b
∈
Z
\
{
c
.Furthermore,
c
is the
least common multiple
, denoted
lcm
(
a, b
)
, if it is the smallest integer that is divided
by
a
and
b
.
0
}
,
c
∈
Z
is a
common multiple
of
a
and
b
if
a
|
c
and
b
|
Another possibility to define the least common multiple of
a
and
b
is to say
that
c
=
lcm
(
a, b
) if
c
divides any common multiple of
a
and
b
.
The
gcd
and
lcm
operators can be generalized to more than two arguments.
In fact,
gcd
(
a
1
,...,a
k
) is the largest integer that divides all
a
i
(
i
=1
,...,k
) and
lcm
(
a
1
,...,a
k
) is the smallest integer that is divided by all
a
i
(
i
=1
,...,k
).
