1

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.

G Tony Jacobs
  • 31,218
Boby
  • 5,985

1 Answers1

1

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.

G Tony Jacobs
  • 31,218
  • 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 01:14
  • 1
    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
  • I often think of a quotation attributed to Sophie Germain: "L'algèbre n'est qu'une géométrie écrite; la géométrie n'est qu'une algèbre figurée," which translates as, "algebra is nothing but written geometry; geometry is nothing but pictured algebra." I very often find it useful to turn algebra problems into geometry problems. That's all I did here; I looked at the picture, and there was the solution. – G Tony Jacobs Aug 29 '14 at 14:00
  • So, what was the picture you thought about? – Boby Aug 29 '14 at 16:37
  • First, I rearranged the equation as $a/b=z_y/z_x$. This made me think of slopes, so I imagined a line through the origin passing through the point $(b,a)$. The problem then became that of identifying other lattice points on that line, subject to the constraint that we're looking for points in the region given by certain inequalities. If a line through the origin has rational slope $p/q$, with that fraction in lowest terms, then it passes through precisely the lattice points $(kq,kp)$ for $k\in\mathbb{Z}$. Does that make sense? – G Tony Jacobs Aug 30 '14 at 13:27
  • yes. Thank you. Tony I posted a some what similar question could you please take a look at it: http://math.stackexchange.com/questions/915168/minimum-of-az-x-bz-y. Thank you – Boby Aug 31 '14 at 18:54