1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ There's mathjax for all your mathematical writing needs. Please use it in the future $\endgroup$ – Jakobian Oct 15 '18 at 18:29
  • 1
    $\begingroup$ 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$) $\endgroup$ – Jakobian Oct 15 '18 at 18:35
0
$\begingroup$

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.

$\endgroup$

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.