points with integer coordinates inside triangles in $\Bbb{R}^3$ I'm taking off from Number of lattice points inside a triangle and its area
Consider a triangle in $\Bbb{R}^3$ whose vertices have integer coordinates. What's the fastest way of counting how many points with integer coordinates are in the interior of the given triangle? 
The reason I have the adjective "fastest" is because I hope to write a program to do this. What I have done is translate the triangle to have one vertex at the origin to obtain two vectors that define the triangle. I can try `reduce' both vectors to the shortest vector with integer coordinates in the same direction as the original vectors then count how many non-negative integer combinations of these reduced vectors are inside the original triangle. The problem with these approach is that there are points with integer coordinates on the plane spanned by the two vectors that are not non-negative integer combinations (it can be the case that a rational combination of the two vectors becomes a point with integer coordinates.). I've seen Pick's theorem but it only counts how many points are non-negative integer combinations of the reduced vectors.
 A: Here is how you can compute the number of points with integral coordinates in the parallelogram spanned by two integer vectors $\def\Z{\Bbb Z}v,w\in\Z^3$, counting points on the border with weight $\frac12$ and corners with weight $\frac14$ (thinking of what happens with the plane spanned by$~v,w$ when tiling it with translates of the parallelogram, these weights are quite natural). From this you can get the number for the triangle by dividing by$~2$, and then the number of points in the interior by subtracting off the contributions on the border, which is fairly easy.
Write down the $3\times 2$ matrix formed by the coordinates of $v,w$, and compute its Smith normal form (applying row and column operations consisting of adding an integer multiple of one row or column to another, leaving only nonzero entries on the main "diagonal". Then the absolute values of the product of the two entries on that diagonal (the invariant factors) is the desired number of weighted points for the parallelogram.
This method in fact computes the order of the finite Abelian group $(\Z^3\cap\langle v,w\rangle_\Bbb R)/\langle v,w\rangle_\Z$, the quotient of the group formed by all vectors in the plane considered by the subgroup spanned by $v,w$. One can interpret this order geometrically as the area of the parallelogram spanned by$~v,w$ divided by the area of a "fundamental parallelegram" for the plane, one with its corners in $\Z^3$ but containing no other points of $\Z^3$. In order to find this order one does a sequence of coordinate changes (row operations, corresponding to choosing a different integral basis for $\Bbb R^3$ than the standard one) and changes of the generating set of $\langle v,w\rangle_\Z$ (column operations, corresponding to modifying $v,w$ individually in such a way that the sub-lattice they span remain the same). One can arrange that in the end the generating vectors each have only one nonzero coordinate, and now the the answer is easy to find since one is essentially dealing with a rectangle in the $x,y$ plane whose sides are parallel to the coordinate axes.
Here is a concrete computational example. Suppose $v=[12,-3,15]$ and $w=[2,22,-35]$. Now form our matrix and successively add the middle row $4$ times to the first row and $5$ times to the second row; then subtract the third row from the first, and subtract the result from the second row and $5$ times (back) from the third row (making it zero). These row operations give
$$
  \begin{pmatrix}12&2\\ -3&22\\ 15&35\end{pmatrix}
\sim
  \begin{pmatrix}0&90\\ -3&22\\ 0&75\end{pmatrix}
\sim
  \begin{pmatrix}0&15\\ -3&7\\ 0&0\end{pmatrix}.
$$
Now one needs a column operation: add the first column $2$ times to the second and then swap the columns. Now continue with row operations
$$
  \begin{pmatrix}15&0\\ 1&-3\\ 0&0\end{pmatrix}
\sim
  \begin{pmatrix}0&45\\ 1&-3\\ 0&0\end{pmatrix}
\sim
  \begin{pmatrix} 1&-3\\0&45\\ 0&0\end{pmatrix}
$$
and finally add the first column $3$ times to the second to clear out the entry $-3$. The invariant factors are $1$ and $45$, and the number associated to the parallelogram spanned by $v,w$ is$~45$. (In fact we could see it coming that the absolute value would be$~45$, by computing a determinant as soon as a row of zeros was produced.)
Finally for the triangle one gets the weighted sum $\frac{45}2$, where the corners get weight $\frac16$ since in a tiling by triangles corners are shared by $6$ of them. From $\frac{45}2$ we must subtract $\frac36$ for the corners and also the contributions for the integral points on the interior of the sides. On the side $[0,v]$ there are $2$ interior points since $\gcd(12,-3,15)=3$, on the side $[0,w]$ there are none because $\gcd(2,22,-35)=1$, and on the side $[v,w]$ there are $4$ interior points since $\gcd(-10,25,50)=5$. For the number of interior points of the triangle one finds $\frac{45}2-\frac36-\frac22-\frac42=19$. (Fortunately this turns out to be a natural number.)
A: You may assume that the triangle has vertices $0$, $a$, $b\in{\mathbb Z}^3$, whereby the two vectors $a$ and $b$ are linearly independent. We need an explicit description of the set $\Lambda:=\langle a,b\rangle\cap{\mathbb Z}^3$ of lattice points in the plane spanned by $a$ and $b$. To this end consider the normal vector $n:=a\times b\in{\mathbb Z}^3$ and replace $n$ by a scalar multiple $n'=(n_1,n_2,n_3)$ such that ${\rm gcd}(n_1,n_2,n_3)=1$. The planar lattice $\Lambda$ then consists of  the integer solutions to the homogeneous linear diophantine equation
$$n_1x_1+n_2x_2+n_3 x_3=0$$
and can be written in the form
$$\Lambda=\bigl\{k_1 e_1+k_2 e_2\>\bigm|\>k_1,\> k_2\in{\mathbb Z}\bigr\}\ .$$
The basis vectors $e_1$, $e_2\in{\mathbb Z}^3$ (which are not uniquely determined) can be found by means of a reduction process (a repeated euclidean algorithm). 
After such $e_1$, $e_2$ have been determined we can proceed as follows: Express $a$ and $b$ in terms of $e_1$ and $e_2$. Since $a$, $b\in\Lambda$ the appearing coefficients will be integers:
$$a=\alpha_1 e_1+\alpha_2 e_2,\quad b=\beta_1e_1+\beta_2 e_2\ .$$
We are now looking at the triangle$T'$  with vertices $0':=(0,0)$, $a':=(\alpha_1,\alpha_2)$, $b':=(\beta_1,\beta_2)\in{\mathbb Z}^2$ and have to count its interior lattice points. This can be done using Pick's area theorem.
Here is an example: Let $a=(437,95,-1)$, $\>b=(173,37,3)$.
One obtains $n=(322,-1484,-266)$, which leads to $n'=(23,-106,-19)$. Therefore we have to finbd a basis ($e_1, e_2)$ of the integer solutions of
$$23x_1-106 x_2-19 x_3=0\ .$$
We can immediately choose $e_1:=(106,23,0)$. Since ${\rm gcd}(106,23)=1$ the equation $23x_1-106 x_2-19\cdot 1=0$ has  solutions, which implies that there are vectors $q=(q_1,q_2,1)\in\Lambda$. One such vector is $e_2:=(-13,-3,1)$. We now know that $\Lambda={\mathbb Z}e_1+{\mathbb Z}e_2$.
One now finds that
$$a=4e_1-e_2,\qquad b=2e_1+3e_2\ ,$$
i.e., $a'=(4,-1)$, $\>b'=(2,3)$. Neither the segment $[0',a']$ nor the segment $[0',b']$ contain lattice points in their interior, but the third side $[a',b']$ of the triangle $T'$ contains the lattice point $(3,1)$ in its interior. It follows that $T'$ possesses $r=4$ boundary lattice points. Therefore by Pick's theorem the number of interior lattice points of $T'$ is given by
$$i(T')={\rm area}(T')-{r\over2}+1={1\over2}(4,-1)\wedge(2,3)-2+1=6\ .$$
