# Solution to Diophantine equation with constraint.

solve the following equation over $z_x,z_y$ \begin{align} &az_x=bz_y\\ &\text{s.t. } a,b,z_x,z_y \in \mathbb{Z} \text{ and } 1 \le z_x \le N \text{ and } 1 \le z_y \le N \end{align}

How many solutions are there? What are the solutions?

I can show that if $bN<a$ or $aN<b$ then there is no solutions. Is there any other conditions like this?

Thank you.

## 1 Answer

First of all, if $a=b=0$, then any pair $(z_x,z_y)$ is a solution. If, only one of $a$ or $b$ equals $0$, then you have no solutions. Now we'll assume that $ab\neq 0$

You can rewrite your equation as $\frac{a}{b}=\frac{z_y}{z_x}$. This gives us a geometric intuition: we want $(z_x,z_y)$ to be a lattice point, collinear with the origin and $(b,a)$, lying within the region $[1,N]\times[1,N]$. If $b$ and $a$ have different signs, there will be no solutions (since $N>1$).

Let $d=\gcd(a,b)$, and let $\overline{a}=\left|\frac{a}{d}\right|, \overline{b}=\left|\frac{b}{d}\right|$. Let $k=\min\left\{\left\lfloor\frac{N}{\overline{a}}\right\rfloor\,\left\lfloor\frac{N}{\overline{b}}\right\rfloor\right\}$. Then your complete set of solutions is $(z_x,z_y)=(m\overline{b},m\overline{a})$, where $m=1,\ldots,k$. In the case where $k=0$, there is no solution.

• Dear, Tony if I change the condition $1 \le z_x \le N$ and $1 \le z_y \le N$ to $1 \le z_x \le N_1$ and $1 \le z_y \le N_2$. Then value of $k$ will be $k=\min \left \{ \left\lfloor\frac{N_1}{\bar{a}} \right\rfloor, \left\lfloor\frac{N_2}{\bar{b}} \right\rfloor \right\}$. Is this correct? – Boby Aug 19 '14 at 1:14
• Those seem to be flipped around. You want $\left\lfloor\frac{N_1}{\bar{b}}\right\rfloor$ and $\left\lfloor\frac{N_2}{\bar{a}}\right\rfloor$ – G Tony Jacobs Aug 19 '14 at 13:03
• Dear, Tony. Could you recommend me any beginners literature on this subject? Thank you very much. – Boby Aug 28 '14 at 22:43
• There are lots of good books on elementary number theory. I particularly liked "Number Theory" by George E. Andrews and "Elementary Number Theory" by Gareth A. Jones and J. Mary Jones. That isn't to say I've seen a problem quite like this one in one of those books, but they both cover lots of ground, and look at Diophantine equations in various ways. If you take a book like that, and work all of the exercises in the first few chapters, you're sure to build some intuition about these things. – G Tony Jacobs Aug 29 '14 at 13:52
• Actually, there's a chapter at the end of the Andrews book about Geometric Number Theory and using lattice points as a subset of $\mathbb{R}^n$ as a way of thinking about the integers. Solutions to a Diophantine equation are lattice points that lie on some curve or surface. In the case of this problem, the curve is the straight line $z_y=\frac{a}{b}z_x$, and it's fairly straightforward, it turns out, to find lattice points on a line passing through the origin with rational slope. – G Tony Jacobs Aug 29 '14 at 13:55