Cryptography Reference
In-Depth Information
PROPOSITION 8
The gcd of integers
x
and
y
, not both zero, is the least positive inte-
ger that is a linear combination of
x
and
y
.
Proof.
Suppose
d
is the least positive integer that is a linear combination of
x
and
y
. We
know that the set of such integers must be nonempty, as at least one of the following linear
combinations must be positive:
x
+ 0 ·
y
,
x
+ 0 ·
y
,
0 ·
x
+
y
, or
0 ·
x
y
.
So, a least such element in this set, say
d
, exists. We must first show
d
is a divisor of both
x
and
y
. We have
d
=
mx
+
ny
where
m
and
n
are integers, and by the division algorithm we
can obtain
x
=
dq
+
r
where 0
≤
r
<
d
.
From this equation, and because
d
=
mx
+
ny
, we can derive
r
=
x
dq
=
x
q
(
mx
+
ny
) = (1
qm
)
x
qny
.
So we can write
r
also as a linear combination of
x
and
y
. Now, by construction,
r
is non-
negative, strictly less than
d
, and
d
is the least positive integer which may be written as a
linear combination of
x
and
y
. So
r
must be zero. This means that
d
divides
x
, which is what
we want to show. Similarly, we can show that
d
|
y
, and that
d
is therefore a common divisor
of
x
and
y
, as desired.
Now, it remains to be shown that
d
is the gcd of
x
and
y
. Suppose
c
is a common divisor
of
x
and
y
. Then, since
d
=
mx
+
ny
,
c
divides
d
by proposition 2. Hence, because
c
is arbi-
trary,
d
must be the greatest common divisor of
x
and
y
.
We now turn our attention to common divisors of more than two integers.
Definition
The greatest common divisor of a set of integers
a
1
,
a
2
, . . . ,
a
n
, not all zero, is the
largest divisor of all the integers in the set. We write this as (
a
1
,
a
2
, . . . ,
a
n
).
E
XAMPLE
.
The greatest common divisor of 20, 30, and 15 is 5.
PROPOSITION 9
(
a
1
,
a
2
,
a
3
, . . . ,
a
n
) = ((
a
1
,
a
2
),
a
3
, . . . ,
a
n
).
Proof.
Note that any common divisor of the
n
integers in the list
a
1
,
a
2
, . . . ,
a
n
is, in par-
ticular, a common divisor of the first two,
a
1
and
a
2
. This divisor then also divides the gcd
Search WWH ::
Custom Search