Closest point to line in lattice Given an $n$ x $n$ integer grid, I look at all possible lines through two grid points and I am interested in the minimum distance from any grid point (not on the line) to any line.
I my guess is that the line which minimizes this distance is the one through $(0,0)$ and $(n-1,n)$ or maybe trough $(0,0)$ and $(1,n)$
My approach of computing the distances from the grid points to the ($(0,0)$ and $(n-1,n)$ ) line is not very elegant and I was wondering if someone knows a nicer approach. 
(And I would still have to show that this is actually the line which minimizes the distance)
Thank you
 A: In order to get to the minimum distance problem quickly, we quote a formula for the distance from the point $(x_0,y_0)$ to the line with equation $px+qy+r=0$. This distance is 
$$\frac{|px_0+qy_0+r|}{\sqrt{p^2+q^2}}.$$
The site linked to gives a proof, as does Wikipedia.  The distance from a point to a line has also been discussed more than once on StackExchange.
For our minimization problem, we can assume that one of the points is $(0,0)$, and the other is, say, $(a,b)$. So the line has equation $bx-ay=0$.  We can assume that $a$ and $b$ are relatively prime, for if $d$ is their greatest common divisor, the same line is determined by $(0,0)$ and $(a/d,b/d)$.
Then by Bezout's Theorem, we can find integers $x_0$, $y_0$ between $0$ and $\max(a,b)$ such that $|bx_0-ay_0|=1$. Thus the smallest non-zero value of $|bx-ay|$ as $(x,y)$ ranges over our grid is $1$.
So the minimum possible non-zero distance from a gridpoint to our line is $\dfrac{1}{\sqrt{a^2+b^2}}$. 
Now we want to maximize $a^2+b^2$, as $(a,b)$ ranges over relatively prime pairs on our grid.  Then for fixed $a+b$, this maximum occurs when $a$ and $b$ differ by as little as possible. If $n=1$, the maximum value of $\sqrt{a^2+b^2}$ is achieved when $a=b=1$.   
Suppose now that $n>1$. Then 
the maximum value of $a^2+b^2$, given that $\gcd(a,b)=1$ and $(a,b)$ is on our grid is attained at $a=n-1$, $b=n$, and at $a=n$, $b=n-1$.  The minimum non-zero distance is therefore 
$$\frac{1}{\sqrt{2n^2-2n+1}}.$$ 
Comment: For our particular problem, we do not need Bezout's Theorem, since if $n>1$ then the distance from $(1,1)$ to the line through $(0,0)$ and $(n-1,n)$ is $1/(2n^2-2n+1)$. It is clear that we can't do better, since $|bx_0-ay_0|$ is at least $1$.  However, if the $n\times n$ grid is replaced by an $m\times n$ grid, the natural analysis uses Bezout's Theorem.
