Suppose and are nonzero polynomials in with greatest common divisor .
- Given , show that there exist such that if and only if is divisible by .
- Given , if and are a particular solution to the equation , prove that every solution is of the form and for some .
We will approach this problem from a more abstract point of view.
Lemma: Let be a Bezout domain and let be nonzero. Suppose and . If , then . Proof: Write . Since , we have for some . Since , we have for some . Now , so that , and thus . Then . Now , so that , and we have .
This lemma generalizes part (a) of this previous exercise.
Lemma: Let be a Bezout domain and let with . There exist such that if and only if . Proof: If , then , so that and exist with . Conversely, if and exist with , then , so that .
Part (a) of this problem follows because is a Euclidean domain, hence a principal ideal domain, and thus a Bezout domain.
Lemma: Let be a Bezout domain and let such that , , , and . If such that , then and for some . Proof: Note that . Then , and thus . Now is in , so that by the first lemma, . Say ; then . Plugging this back into and solving for (using the fact that divides ), we see that .
Again, this solves the stated problem because is a Bezout domain. But more generally, this lemma allows us to solve linear Diophantine equations in two variables over any Bezout domain.