Waste less time on Facebook — follow Brilliant.
×

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} .\]

Note by Calvin Lin
3 years, 7 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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?

Chandrachur Banerjee - 3 years, 2 months ago

Log in to reply

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 \).

Calvin Lin Staff - 3 years, 2 months ago

Log in to reply

I learned a lot! Thanks :D

Astro Enthusiast - 3 years, 3 months ago

Log in to reply

thanks....

Shatrughna Kumar - 3 years, 2 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...