Linear diophantine equations
In this chapter we present a striking application of the Euclidean algorithm. The following very ancient problem will be solved.
Problem 18.0.1 Given integers a, b and c, find all integers m and n such that
Notice that Proposition 4.1.1 shows that for certain choices of a, b and c there are no solutions at all since it was proved there that there are no solutions for a = 14, b = 20, c = 101. The first part of the solution to the problem is to give a necessary and sufficient condition for a solution to exist. It turns out that the idea used in proving Proposition 4.1.1 gives such a condition although the proof ...