×

# Bezout's Lemma

Given integers $$x$$ and $$y$$, a linear combination of $$x$$ and $$y$$ has the form $$ax + by$$. Bezout's Lemma relates the question of finding the greatest common divisor of $$x$$ and $$y$$ to the question of finding linear combinations of $$x$$ and $$y$$.

## Technique

Applying the Euclidean Algorithm backwards gives an algorithm to obtain the integer values of $$a$$ and $$b$$. We show how to obtain integers $$a$$ and $$b$$ such that $$16457a + 1638b = 7$$. These numbers are calculated in Euclidean Algorithm.

$\begin{array} {llllllllll} 7 & = & 21 &- & 14 \times 1 \\ & = & 21 \times 1 & - & 14 \times 1\\ & = & 21 &- & (77 - 21 \times 3) \times 1\\ & = & - 77 \times 1 &+& 21 \times 4\\ & = & - 77 \times 1 &+ & (1638 - 77 \times 21) \times 4 \\ &= &1638 \times 4 &-& 77 \times 85\\ & = & 1638 \times 4 &- & (16457 - 1638 \times 10) \times 85 \\ & = &16457 \times (-85) &+& 1638 \times 854\\ \end{array}$

## Worked Examples

### 1. Given integers $$x, y$$, describe the set of all integers $$N$$ that can be expressed in the form $$N=ax+by$$, where $$a, b$$ are integers.

Solution: Let $$k = \gcd(x,y)$$. Then any integer of the form $$kn$$, where $$n$$ is an integer, can be expressed as $$ax+by$$. We already know that this condition is a necessary condition, so to show that it is sufficient, Bezout's Lemma tells us that there exists integers $$a', b'$$ such that $$k = a' x + b'y$$. Therefore,

$kn = (a'n) x + (b'n) y.$

### 2. [Modulo Arithmetic Property I - Multiplicative inverses] Show that if $$a, b$$ are integers such that $$\gcd(a,n)=1$$, then there exists an integer $$x$$ such that $$ax \equiv 1 \pmod{n}$$.

Solution: Since $$\gcd(a,n)=1$$, Bezout's Lemma implies there exists integers $$x, y$$ such that $$ax + n y = \gcd (a,n) = 1$$. Then

$1 \equiv ax+ny \equiv ax \pmod{n} .$

Note by Calvin Lin
3 years, 4 months ago

Sort by:

I did not understand what the 1st worked example mean. Any number of form kn can be represented in the form ax+by but that does not mean that all nos of form ax+by will be of form kn. Actually just explain what the question demands? · 2 years, 11 months ago

The question asks you to classify all numbers that can be written in the form $$ax + by$$ for given integers $$x$$ and $$y$$. The claim is that these numbers are exactly those of the form $$k n$$, where$$k = \gcd (x,y)$$ and $$n$$ is any integer.

As you realized, there are 2 parts to this.
First, we have to show that any number of the form $$ax + by$$ can be written as $$kn$$ for some $$n$$. This is obvious because we can let $$x = k x^*, y = ky^*$$ then $$ax + by = a k x^* + bky^* = k ( ax^* + by^* )$$.
Second, we have to show that any number of the form $$kn$$ can be written as $$ax + by$$ for some $$a$$ and $$b$$. This follows by applying Bezout's lemma, which tells us that there exists integers which satisfy $$k = a' x + b' y$$, and hence $$kn = ( a'n) x + (b'n) y$$. Staff · 2 years, 11 months ago

I learned a lot! Thanks :D · 3 years ago