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

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
• Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

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 learned a lot! Thanks :D

- 7 years ago

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?

- 6 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 - 6 years, 11 months ago

thanks....

- 7 years ago