Class Notes (1,100,000)

CA (620,000)

UW (20,000)

MATH (2,000)

MATH135 (300)

Roxane Itier Itier (10)

Lecture 2

School

University of WaterlooDepartment

MathematicsCourse Code

MATH135Professor

Roxane Itier ItierLecture

2This

**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

###### You're Reading a Preview

Unlock to view full version