Math Is Fun Forum

mikau

Member

Registered: 2005-08-22

Posts: 1,504

Diaphantine equations

The following is a homework assignment i need to turn in. I am allowed to seek help.

The prices of two articles, tax included are (a)$ and (b)$ respectively. Find the least and the largest number of units of each that can be bought with (c)$.

So in effect we must solve:
ax + by = c

in the actual problem the values are given but i'd rather solve it myself, moreover, I'd prefer hints, to a direct solution.

My biggest problem is I don't understand what is meant by the 'least' and 'largest' number of units of each.

I think i can solve it by considering that both x and y must be positive, and divisibility, but I believe we are supposed to use the Euclidean algorithm to solve this. But I thought that only finds one particular solution, with no special properties.

---

A logarithm is just a misspelled algorithm.

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Diaphantine equations

You're spending $c on x items costing $a and y items costing $b.
Therefore, in total you are buying x+y items. It is this value that the question wants the boundaries for.

Or maybe it wants you to find the lowest and highest possible values for x and y individually.
If you can do x+y then x and y follow simply though (and vice versa).

Euclid's algorithm would be a good place to start.
It would give you x and y such that ax+by = hcf(a,b).
Then either you can multiply the whole thing by an integer so that the RHS is c, or no solutions exist.
(You're not necessarily finished though, because it's likely to give a negative value for x or y.)

After you've used that to find a particular solution to ax+by=c, you should then try generally solving ap+bq=0. (This is easy in comparison)

Then you can combine the two equations like so: [ax+by] + [ap+bq] = c+0 = c, and there is your general solution.

Now you can play around with k and see what gets you maximums, minimums, etc.

I think I might have helped more than you wanted, so I've hidden everything I've typed.
Highlight it line by line until you've read as much as you need/want.
(If you're not using the default forum skin then sorry! )

---

Why did the vector cross the road?
It wanted to be normal.