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.

  • 1
    $\begingroup$ See Pick's Theorem. $\endgroup$ – 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}.} $$


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.