Diophantine Equations

A Diophantine equation is an equation in which only integer solutions are allowed. A linear Diophantine equation (in two variables) is an equation of the general form ax + by = c, where solutions are sought with a, b, and c being integers. Such equations can be solved completely, and the first known solution was constructed by Brahmagupta. Consider the equation ax + by = 1. This particular equation can be solved using the Euclidean Algorithm. In fact, this solution is equivalent to finding the continued fraction for a/b, where a and b are relatively prime.

Consider the general first-order equation of the form ax + by = c. The greatest common factor of a and b -- call it f -- can be divided through yielding:

ax/f + by/f = c/f

If f | c, then c/f is not an integer and the equation cannot have any integer solutions. A necessary and sufficient condition for the general first-order equation to have integer solutions is that f|c.

For example, consider 14x + 18y = 28. The GCF(14,18) = 2, and 28/2 is an integer. Therefore integer solutions exist, one of them is (2,0).

ACTIVITY: The CTM club sold t-shirts for a fundraiser this year. At the last meeting of the year, they recruited members ($5 dues) and collected payment for the shirts ($12). When the new treasurer got home, she realized that she did not keep track of how much of the money received was for dues and for shirts. Help her figure out how many shirts were paid for and how many dues were paid. The total received was $134 that night.

EXAMPLES