15
$\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$
1
  • 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$ Commented Jan 5, 2014 at 16:35

1 Answer 1

26
$\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.

$\endgroup$
2
  • $\begingroup$ Thanks for the formula...But can you please explain it?? $\endgroup$ Commented Jan 5, 2014 at 16:36
  • 14
    $\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
    Commented Jan 5, 2014 at 16:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .