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.
Thanks in advance!
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 \cdot x$ an integer. Now let $d = gcd(x_0, y_0)$. We get $y_0 / x_0 \cdot x = (d \cdot \hat{y_0})/(d \cdot \hat{x_0}) \cdot x = \hat{y_0}/\hat{x_0} \cdot 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} \cdot 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 \cdot \hat{x_0}$. Hope this helps.