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