# How many number of integer coordinates exists between a line segment, including the end points?

There is a line segment say $$AB$$ with coordinates of end-points as $$A=(x_1, y_1)$$ and $$B=(x_2, y_2)$$. $$x_1, y_1, x_2, y_2$$ are integers. I need to find the number of integer coordinates which lie on the line segment including end-points.

I read somewhere that it is $$\gcd(|x_1 - x_2|, |y_1 - y_2|) + 1$$. But, I cannot understand why this works.

I do not get the intuition behind it. I searched for proof but did not find anything intuitive and straightforward.

Please help me understand this. I am stuck on it. I am expecting a nice proof with great explanation.

• Maybe this will make it easier for you. Without loss of generality, we can assume that $A=(0, 0)$, and $B=(x, y)$ with $x, y\geq 0$. ($B\neq A$) – Jakobian Oct 15 '18 at 18:35
Using Jakobian's simplification, the problem looks as follows: For any $$x_0, y_0 > 0$$, how many integer coordinates does the line from $$(0, 0)$$ to $$(x_0, y_0)$$ pass? We note first, that the slope of this line is $$y_0/x_0$$. So the problem is equivalent to asking: for how many integers $$x$$ with $$0 \leq x \leq x_0$$ is $$y_0 / x_0 * x$$ an integer. Now let $$d = gcd(x_0, y_0)$$. We get $$y_0 / x_0 * x = (d * \hat{y_0})/(d * \hat{x_0}) * x = \hat{y_0}/\hat{x_0} * x$$ for some $$\hat{y_0},\hat{x_0}$$ with $$gcd(\hat{y_0},\hat{x_0}) = 1$$. Now $$\hat{y_0}/\hat{x_0} * x$$ is an integer if and only if x is a multiple of $$\hat{x_0}$$. So how many multiples of $$\hat{x_0}$$ are there between $$0$$ and $$x_0$$. It is exactly $$d + 1$$, because $$x_0 = d * \hat{x_0}$$. Hope this helps.