MATH135 Lecture 2: Example on LDE

• School: University of Waterloo
• Department: Mathematics
• Course: MATH135
• Professor: Roxane Itier Itier

Document Summary

Here is a brainteaser from the waterloo county almanac, circa 1930: Neither of them has cash, but joe has 14 cows which he values at each. He would like to pay his debt in cows, with jane making change by giving joe some of her pigs valued at each. Is the deal possible, and in how many ways? (the example is taken from elementary number theory by charles vanden eynden. ) Let x the number of cows joe pays, y the number of pigs jane returns as change. Then 0 x 14 and y 0, and, to keep our discussion family-friendly, we shall restrict x and y to be integers. This is a linear diophantine equation (with a 185, b 110 and c 10). Let"s begin by solving ( ) for its general solution. We apply the extended euclidean algorithm to nd d gcd a, bq gcd 185, 110q gcd 185, 110q.