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$ .

Bezout's Lemma: Given integers $x$ and $y$ , there exists integers $a$ and $b$ such that $ax+by = \gcd(x,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} .$

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Bezout's Lemma

Bezout's Lemma: Given integers $x$ and $y$ , there exists integers $a$ and $b$ such that $ax+by = \gcd(x,y)$ .

Technique

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.

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}$ .

Comments

Bezout's Lemma

Bezout's Lemma: Given integers x xx and y yy, there exists integers a aa and b bb such that ax+by=gcd⁡(x,y) ax+by = \gcd(x,y) ax+by=gcd(x,y).

Technique

Worked Examples

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

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

Comments

Bezout's Lemma: Given integers $x$ and $y$ , there exists integers $a$ and $b$ such that $ax+by = \gcd(x,y)$ .

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.

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}$ .