MATH135 Lecture 2: Example on LDE
SchoolUniversity of Waterloo
ProfessorRoxane Itier Itier
This preview shows half of the first page. to view the full 2 pages of the document.
MATH 135 Winter 2015
Example: Linear Diophantine Equations
Here is a brainteaser from the Waterloo County Almanac, circa 1930:
Farmer Joe owes Farmer Jane $10. Neither of them has cash, but Joe has 14 cows which
he values at $185 each. He would like to pay his debt in cows, with Jane making change
by giving Joe some of her pigs valued at $110 each. Is the deal possible, and in how
(The example is taken from Elementary Number Theory by Charles Vanden Eynden.)
xthe number of cows Joe pays,
ythe number of pigs Jane returns as change.
Then 0 ¤x¤14 and y¥0, and, to keep our discussion family-friendly, we shall restrict xand y
to be integers. The equation relating xand yis
This is a linear Diophantine equation (with a185, b 110 and c10). Let’s begin by solving
() for its general solution.
Step 1: Checking existence of solutions.
We apply the Extended Euclidean Algorithm to ﬁnd dgcdpa, bq gcdp185,110q gcdp185,110q.
We also obtain integers sand tfor which d185s110t.
s t r q
1 0 185
0 1 110
11 75 1
1 2 35 1
35 5 2
22 37 0 7
It follows that d5, which divides c10. By LDET 1, () has a solution. The above also yields
You're Reading a Preview
Unlock to view full version