# Find the number of solutions $(x,y)$ in non-negative integers such that $ax+by\leq ab$, where $a$ and $b$ are positive integers.

Problem: Find the number of solutions $(x,y)$ in nonnegative integers such that $ax+by\leq ab$, where $a$ and $b$ are positive integers.

My Attempt: I observed that this is equivalent to counting the number of lattice points on and under the line $ax+by= ab.$ So I know that the number of solutions must be at least $$\frac{(a+1)(b+1)}{2}$$ since there are $(a+1)(b+1)$ points in the rectangle $[0,b]*[0,a].$ However, I am having trouble in counting the points on the line $ax+by=ab.$ Any ideas/hints will be much appreciated.

• See Pick's Theorem. – Gerry Myerson Nov 19 '16 at 22:26

So far, you should agree that the number of solutions $(x,y)$ is $$\frac{(a+1)(b+1) + B}{2}, \tag{1}$$ where $B$ is the number of points on the boundary $ax + by = ab$. So we need to count $B$.
Write $a = da'$, $b = db'$, where $d = \gcd(a,b)$, so that $\gcd(a',b') = 1$. Our equation becomes \begin{align*} (da') x + (db') y &= d^2 a' b'\\ \iff a' x + b' y &= d a' b' \tag{2} \end{align*}
Mod $a'$, $b'y \equiv 0$ so $a' \mid y$. Likewise mod $b'$, $a'x \equiv 0$ so $b' \mid x$. So if we write $x = b'x'$ and $y = a' y'$, the number of solutions to (2) is equal to the number solutions $(x',y')$ to $$a'b'x' + a'b'y' = da'b'$$ i.e. just $x' + y' = d$. There are $d+1$ solutions to this since $x'$ and $y'$ are nonnegative.
So $B = d + 1 = \gcd(a,b) + 1$ in (1), and the final answer is $$\boxed{\frac{(a+1)(b+1) + \gcd(a,b) + 1}{2}.}$$