# Euclidean Algorithm - GCD Word Problem

An Oil company has a contract to deliver 100000 litres of gasoline. Their tankers can carry 2400 litres and they can attach on trailer carrying 2200 litres to each tanker. All the tankers and trailers must be completely full on this contract, otherwise the gas would slosh around too much when going over some rough roads. Find the least number of tankers required to fulfill the contract [ each trailer, if used, must be pulled by a full tanker.]

Alright, so i know i can solve this by the Euclidean Algorithm. Where 100000 = 2200x + 4600y But, how do i solve with the variables there.

-
Find by trial and error? – MatthewL Mar 15 '13 at 6:33

Hint $\$ Cancelling $\,500\,$ yields $\rm\:11x+23y = 500,\:$ so $\rm\:mod\ 11\!:\ y \,\equiv\, 500\equiv 5,\:$ thus $\rm\: y = 5 + 11n\:$ hence$\rm\: x = (500-23y)/11 = (500 - 23(5+11n))/11 =\: \ldots$

-

Step 1. Divide everything through by $\gcd(2200,4600)$. (If that greatest common divisor doesn't divide 100000, then there's no solution - do you see why?) In this case, we get $500 = 11x + 23y$.

Step 2. With the remaining coefficients, use the extended Euclidean algorithm to find integers $m$ and $n$ such that $11m + 23n = 1$. Then $11(500m) + 23(500n) = 500$.

Step 3. One of the integers $500m$ and $500n$ is negative. However, you can add/subtract $23$ to/from $500m$ while subtracting/adding $11$ from/to $500n$ - it will remain a solution to $500 = 11x + 23y$. Keep doing that until both variables are positive. In this way you can even find all solutions (I find 21 solutions).

PS: To me it seems that the problem leads to the equation $100000 = 2400x+4600y$, rather than $2200x$.

-
Dividing by the GCD gives you $500=11x+23y$. – Fixed Point Mar 15 '13 at 7:49
um, yeah, that's what I meant.... – Greg Martin Mar 15 '13 at 18:18
And it also changes the number of solutions from twenty to two. – Fixed Point Mar 15 '13 at 19:09
nope, I did that part of the computation in a way that the previor error didn't affect. (although I miscounted them ... should be 21) – Greg Martin Mar 15 '13 at 22:13

Find the GCD of the three numbers and divide your equation by it. Then using the euclidean algorithm, you will find all of the integer solutions of which there are infinitely many. Then from all of those solutions there are only two where $x$ and $y$ are both positive so from those two pick the one with the smaller number of tankers.

-

You can construct an optimization problem by integer domain such as $$min_{x,y}x+y\quad s.t. 2400x+4600y=100000\quad x,y\in I$$ which can be solved as $$x=11\quad y=16$$

-