Given integers and , a linear combination of and has the form . Bezout's Lemma relates the question of finding the greatest common divisor of and to the question of finding linear combinations of and .
Bezout's Lemma: Given integers and , there exists integers and such that .
Applying the Euclidean Algorithm backwards gives an algorithm to obtain the integer values of and . We show how to obtain integers and such that . These numbers are calculated in Euclidean Algorithm.
1. Given integers , describe the set of all integers that can be expressed in the form , where are integers.
Solution: Let . Then any integer of the form , where is an integer, can be expressed as . 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 such that . Therefore,
2. [Modulo Arithmetic Property I - Multiplicative inverses] Show that if are integers such that , then there exists an integer such that .
Solution: Since , Bezout's Lemma implies there exists integers such that . Then