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.


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.

  • $\begingroup$ 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? $\endgroup$ – Boby Aug 19 '14 at 1:14
  • 1
    $\begingroup$ 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$ $\endgroup$ – G Tony Jacobs Aug 19 '14 at 13:03
  • $\begingroup$ Dear, Tony. Could you recommend me any beginners literature on this subject? Thank you very much. $\endgroup$ – Boby Aug 28 '14 at 22:43
  • $\begingroup$ 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. $\endgroup$ – G Tony Jacobs Aug 29 '14 at 13:52
  • $\begingroup$ 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. $\endgroup$ – G Tony Jacobs Aug 29 '14 at 13:55

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.