"Given a linear diophantine equation $ax+by=c$ with a particular solution $(x_0,y_0)$ the general solution is given by $$\biggl(x_0-\frac{b}{gcd(a,b)}t,y_0+\frac{a}{gcd(a,b)}t\biggr)$$ for all $t\in \mathbb{Z}$"

I understand the proof of this theorem pretty well but would appreciate an intuitive explanation of why this general solution gives all the solutions to the equation...


Let's take, as an example, the case of money. We have banknotes whose values are $a$ and $b$. We want to exchange an amount of $c$.

Finding a solution $x_0, y_0$ then corresponds to finding some number of banknotes such that we exchange exactly $c$.

But, sort of as a dufus, I could insist on exchanging more bills.

So if I give you $x_0 + \frac{b}{gdc(a,b)}t$ number of bills, valued $a$, and you give me $y_0 - \frac{a}{gdc(a,b)}t$ number of bills valued $b$ back, we have exchanged exactly an additional $$\frac{ab}{gcd(a,b)}t - \frac{ba}{gcd(a,b)} t = 0$$

So we would still exchange exactly $c$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.