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