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

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

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

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

## Comments

Sort by:

TopNewestI 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?

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

Log in to reply

I learned a lot! Thanks :D

Log in to reply

thanks....

Log in to reply