Number Theory • Topic 12

Bézout's Identity

Bézout's Identity provides the theoretical foundation for linear Diophantine equations.

Statement

Theorem (Bézout's Identity)

Let

a

and

b

be integers with greatest common divisor

d

. The set of all linear combinations

a x + b y

(where

x, y \in Z

) is exactly the set of multiples of

d

S = {a x + b y ∣ x, y \in Z} = {k d ∣ k \in Z}

Corollary: $d$ is the smallest positive integer that can be written as $a x + b y$ .

The equation

a x + b y = c

has integer solutions if and only if

d ∣ c

. If

(x_{0}, y_{0})

is one particular solution, the general solution is:

x = x_{0} + \frac{b}{d} k

y = y_{0} - \frac{a}{d} k

for any integer

k

For coprime positive integers

a, b

The largest number that cannot be written as $a x + b y$ (with $x, y \geq 0$ ) is $ab - a - b$ .
There are exactly $\frac{( a - 1 ) ( b - 1 )}{2}$ non-representable positive integers.

Exercise (Problem 1)

Find the general solution to

6 x + 15 y = 9

Exercise (Problem 2)

What is the largest amount of money that cannot be paid using only 5-cent and 7-cent coins?

Exercise (Problem 3)

Prove that if

g cd (a, b) = 1

, then

g cd (a + b, a - b)

is 1 or 2. (Use Bézout linear combinations).