Class Notes (1,100,000)
CA (620,000)
UW (20,000)
MATH (2,000)
MATH135 (300)
Lecture 2

# MATH135 Lecture 2: Example on LDE

Department
Mathematics
Course Code
MATH135
Professor
Roxane Itier Itier
Lecture
2

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
many ways?
(The example is taken from Elementary Number Theory by Charles Vanden Eynden.)
Solution. Let
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
185x110y10.()
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
1