9
$\begingroup$

How can we count the number of lattice point on a line, given that the endpoints of the lines are themselves lattice points? I really can't think of how counting lattice points would work, so please provide me some intuition on how lattice points can be counted. Also, what is the relation of the x-distance and y-distance being coprime to existence of lattice points?

$\endgroup$
  • 2
    $\begingroup$ Start by moving everything so that one lattice point is at the origin. The other is at $(a, b)$. You're hoping to find $n$ and $k$ such that $(n, k)$ is on the line from $(0,0)$ to $(a, b)$ and $0 \le n \le a$. Being on the line means that $bn = ak$. Write both $k$ and $n$ as multiples of $d = gcd(k, n)$ and you should be on your way... $\endgroup$ – John Hughes Jan 5 '14 at 16:35
18
$\begingroup$

For the line from $(a,b)$ to $(c,d)$ the number of such points is $${\gcd(c-a,d-b)}+1.$$ Especially, if the $x$ and $y$ distances are coprime, only the endpoints are lattice points.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the formula...But can you please explain it?? $\endgroup$ – Shaurya Gupta Jan 5 '14 at 16:36
  • 10
    $\begingroup$ The equation of the line is $$y=\frac{d-b}{c-a}(x-a)+b$$ Now define $c-a=\alpha\cdot k$ and $d-b=\beta\cdot k$ where $k$ is the greatest common divisor (gcd) of $c-a$ and $d-b$. Then $$y=\frac{\beta}{\alpha}(x-a)+b$$ holds for integers $x$ and $y$ if and only if $(x-a)$ is a multiple of $\alpha$. Since $a\leq x\leq c$ we must have $0\leq (x-a)\leq c-a=\alpha\cdot k$ so there are $k+1$ multiples of $\alpha$ in this interval. Thus there will be $k+1$ lattice points. $\endgroup$ – String Jan 5 '14 at 16:52

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.