Page 291 - Discrete Mathematics and Its Applications

270 4 / Number Theory and Cryptography

DEFINITION 6 If a and b are positive integers, then integers s and t such that gcd(a, b) = sa + tb are called
Bézout coefficients of a and b (after Étienne Bézout, a French mathematician of the eighteenth
century). Also, the equation gcd(a, b) = sa + tb is called Bézout’s identity.

We will not give a formal proof of Theorem 6 here (see Exercise 36 in Section 5.2 and [Ro10]
for proofs). We will provide an example of a general method that can be used to find a linear
combination of two integers equal to their greatest common divisor. (In this section, we will
assume that a linear combination has integer coefficients.) The method proceeds by working
backward through the divisions of the Euclidean algorithm, so this method requires a forward
pass and a backward pass through the steps of the Euclidean algorithm. (In the exercises we
will describe an algorithm called the extended Euclidean algorithm, which can be used to
express gcd(a, b) as a linear combination of a and b using a single pass through the steps of the
Euclidean algorithm; see the preamble to Exercise 41.)
EXAMPLE 17 Express gcd(252, 198) = 18 as a linear combination of 252 and 198.

Solution: To show that gcd(252, 198) = 18, the Euclidean algorithm uses these divisions:

252 = 1 · 198 + 54
198 = 3 · 54 + 36
54 = 1 · 36 + 18
36 = 2 · 18.
Using the next-to-last division (the third division), we can express gcd(252, 198) = 18 as a
linear combination of 54 and 36. We find that

18 = 54 − 1 · 36.

The second division tells us that

36 = 198 − 3 · 54.

Substituting this expression for 36 into the previous equation, we can express 18 as a linear
combination of 54 and 198. We have

18 = 54 − 1 · 36 = 54 − 1 · (198 − 3 · 54) = 4 · 54 − 1 · 198.

The first division tells us that

54 = 252 − 1 · 198.

Substituting this expression for 54 into the previous equation, we can express 18 as a linear
combination of 252 and 198. We conclude that

18 = 4 · (252 − 1 · 198) − 1 · 198 = 4 · 252 − 5 · 198,
completing the solution. ▲

We will use Theorem 6 to develop several useful results. One of our goals will be to prove
the part of the fundamental theorem of arithmetic asserting that a positive integer has at most
one prime factorization. We will show that if a positive integer has a factorization into primes,
where the primes are written in nondecreasing order, then this factorization is unique.