# 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
4 years, 1 month ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

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?

- 3 years, 8 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 - 3 years, 8 months ago

I learned a lot! Thanks :D

- 3 years, 9 months ago

thanks....

- 3 years, 9 months ago