In the grid constructed by grid points (M*x, M*y) and given the point A(x1,y1) and point B(x2,y2) where all the variables are integers. I need to check how many grid points lie on the line segment from point A to point B. I know that it can be done by using the extended euclidean algorithm somehow, but I have no clue on how to do it. I would appreciate your help.
Rephrased, you want to determine how many numbers t satisfy
(1) M divides (1-t) x1 + t x2
(2) M divides (1-t) y1 + t y2
(3) 0 <= t <= 1.
Let's focus on (1). We introduce an integer variable q to represent the divisibility constraint and solve for t:
exists integer q, M q = (1-t) x1 + t x2
exists integer q, M q - x1 = (x2 - x1) t.
If x1 is not equal to x2, then this gives a periodic set of possibilities of the form t in {a + b q | q integer}, where a and b are fractions. Otherwise, all t or no t are solutions.
The extended Euclidean algorithm is useful for intersecting the solution sets arising from (1) and (2). Suppose that we want to compute the intersection
{a + b q | q integer} intersect {c + d s | s integer}.
By expressing a generic common element in two different ways, we arrive at a linear Diophantine equation:
a + b q = c + d s,
where a, b, c, d are constant and q, s are integer. Let's clear denominators and gather terms into one equation
A q + B s = C,
where A, B, C are integers. This equation has solutions if and only if the greatest common divisor g of A and B also divides C. Use the extended Euclidean algorithm to compute integer coefficients u, v such that
A u + B v = g.
Then we have a solution
q = u (C/g) + k (B/g)
s = v (C/g) - k (A/g)
for each integer k.
Finally, we have to take constraint (3) into consideration. This should boil down to some arithmetic and one floor division, but I'd rather not work out the details (the special cases of what I've written so far already will take quite a lot of your time).