1. **State the problem:** We need to find the greatest common divisor (gcd) $d$ of $a=135$ and $b=59$, and express $d$ as a linear combination $d = sa + tb$ where $s > 0$ is as small as possible and $t$ is an integer (negative). 2. **Find $d = \gcd(135,59)$ using Euclid's algorithm:** $$135 = 59 \times 2 + 17$$ $$59 = 17 \times 3 + 8$$ $$17 = 8 \times 2 + 1$$ $$8 = 1 \times 8 + 0$$ So, $d = 1$. 3. **Use Extended Euclid's algorithm to express $1$ as $s \times 135 + t \times 59$:** Start from $1 = 17 - 8 \times 2$ From previous steps: $$8 = 59 - 17 \times 3$$ Substitute: $$1 = 17 - (59 - 17 \times 3) \times 2 = 17 \times 7 - 59 \times 2$$ Next, express $17$ in terms of $135$ and $59$: $$17 = 135 - 59 \times 2$$ Substitute: $$1 = (135 - 59 \times 2) \times 7 - 59 \times 2 = 135 \times 7 - 59 \times 14 - 59 \times 2 = 135 \times 7 - 59 \times 16$$ 4. **Check coefficients:** $s = 7 > 0$ and $t = -16$ (negative), which satisfies the problem's conditions. 5. **Interpretation:** Fill jug A ($135$ gallons) $7$ times and empty jug B ($59$ gallons) $16$ times to measure exactly $1$ gallon. **Final answer:** $$s = 7, \quad t = -16$$