# Linear Diophantine Equations

• Aug 23rd 2009, 08:59 PM
dlbsd
Linear Diophantine Equations
Q: Show that if $a, b, c \in Z^+$ and (a, b) = 1, then the number of n nonnegative solutions of $ax + by = c$ satisfies the inequality: $\frac{c}{ab} - 1 < n \leq \frac{c}{ab} + 1$

Some Useful facts:
Intercepts @ (c/a, 0) and (o, c/b)

Distance between intercepts is: $\frac{c}{ab}*\sqrt{a^2 + b^2}$

Distance between successive points: $\frac{1}{d}*\sqrt{a^2 + b^2}$

There is an integral point x,y on the line and in the first quadrant if:
$\frac{c}{ab}*\sqrt{a^2 + b^2}$ $> \frac{1}{d}*\sqrt{a^2 + b^2}
$