number of points with integer coordinates of a line segment in $\mathbb{R}^3$ through the origin Take the line segment between $(a,b,c)$ and $(d,e,f)$ where $a,b,c,d,e,f \in \mathbb{Z}$. What's the shortest way to count the number of points in this line segment that have integer coordinates? 
I was wondering how to do this as I was solving a problem that hinged on showing no such points are in some line segment in three dimensions.

This problem is invariant under translations and reflections, so without loss of generality you can assume $a=b=c=0$ and $d,e,f \ge 0$. If such an $\alpha \in \mathbb R$ satisfies $\alpha d, \alpha e, \alpha f \in \mathbb Q$, then of course $\alpha$ is rational, so write $\alpha = p/q$. Then $pd/q, pe/q,pf/q \in \mathbb Z$, hence assuming $(p,q) = 1$, this means $q | (d,e,f)$. Since the smallest positive (i.e. $> 0$) $\alpha$ for which this works is clearly $\alpha = \frac 1{(d,e,f)}$ and that solutions are all equidistant, you see that there are precisely $(d,e,f) + 1$ solutions. 
Now it suffices to see how this solution behaves under translation. $d$, $e$ and $f$ are the distances between the coordinates of our two points, and these distances are invariant under translations and reflections, so given $a,b,c,d,e,f \in \mathbb Z$, the number of solutions is $(|a-d|,|b-e|,|c-f|) + 1$. The "fastest algorithm" is therefore a greatest-common-divisor algorithm.
Hope that helps,
