Chinese Remainder Theorem : Size of loop We say that two integer points $(a,b)$ and $(c,d)$ in the plane can see each other if the line segment joining them passes through no other integer points. A loop is a non-empty set of integer points such that each element can see precisely two other elements of the set. Does there exist a loop of size 100 ?
My attempt :
Equation of the lines pass through the points $(a,b)$ and $(c,d)$, 
$pa=qb+r$
$pc=qd+r$ , $p, q, r \in \mathbb{N}$
so $p(2c-a)=q(2d-b)+r$
and the points $(2c-a,2d-b)$ and $(\frac{c+a}{2},\frac{d+b}{2})$ are not on the loop.
By induction, $\forall k \in \mathbb{Z}$, $t+k=1$
we have $(tc+ka,td+kb)$ are not on the loop.
so the size of loop depends on the value of $a,b,c,d$.
 A: Say we have two points $P_1 = (x_1, y_1)$ and $P_2 = (x_2, y_2)$, then the condition of one point seeing the other is equivalent to the condition that
$$\gcd (x_2-x_1, y_2-y_1) = \pm 1$$
(The $\pm$ comes from the fact that one of the differences might be negative, but this is not essential)
Lets call this the "distance" between points $P_1$ and $P_2$ and write it down as $|P_2 - P_1| = \gcd (x_2-x_1, y_2-y_1)$
Let us show a construction that produces a loop of size $n+2$ (for arbitrary $n$, for example, $n=98$).
First let us create $n+1$ points:
$$A_0 = (0, 0); A_1 = (a, b); A_2 = (2a, 2b) \dots A_n = (na, nb)$$
Where $a$ and $b$ are arbitrary numbers on which we impose simply that $\gcd (a, b) = \pm 1$. Notice that the points all lie on one straight line.
This implies that each of the points $A_1, A_2 \dots A_{n-1}$ sees exactly two others, while $A_0$ and $A_n$ see exactly one other point.
(The gcd condition makes it so that there are no points between $A_i$ and $A_{i+1}$, since then 
$$|P_{i+1} - P_i|= \gcd (a\cdot(i+1)-a \cdot i, b \cdot (i+1)-b \cdot i) = \gcd (a, b) = \pm 1$$
And it is clear that two points that have a point in between them cannot see each other from definition, thus any single point on this line can see no more than two others.)
Now all that is left is to find the coordinates of a point $B = (c, d)$ such that $B$ sees $A_0$ and $A_n$ and does not see any other point. So in essence this boils down to the following system:
$$|B-A_0| = \gcd(c-0, d-0) = \gcd(c, d) = \pm 1$$
$$|B-A_i| = \gcd(c-ia, d-ib) \neq \pm 1 $$
$$|B-A_n| = \gcd(c-na, d-nb) = \pm 1$$
where the middle equation has to be satisfied for all $0<i<n$. Now since we have freedom over what exactly is the $|B-A_i|$ for these $i$ then we will require that 
$$\gcd(c-ia, d-ib) = d-ib \neq \pm 1$$
This in essence means simply that 
$$c-ia \equiv 0 \mod d-ib$$
$$c \equiv ia \mod d-ib$$
This is starting to look like the chinese remainder theorem now, isnt it?
For $|B-A_0|$ we will simply ask that 
$$ c \equiv 1 \mod d$$
(it is not hard to verify that this means that $\gcd(c, d) = 1$)
And for $|B-A_n|$ let us require that
$$ c \equiv na+1 \mod d - nb$$
So we have translated our $\gcd$ requirements into a system of congruences:
$$ c \equiv 1 \mod d$$
$$ c \equiv ia \mod d - ib$$
$$ c \equiv na+1 \mod d - nb$$
The chinese remainder theorem guarantees the existence of such a $c$. However, we must first establish that all of the modulus are pairwise coprime.
Notice that $d, d-b, d-2b \dots d-nb$ form an arithmetic progression. Now by the well known Green-Tao theorem there exists an arithmetic progression of $k$ terms consisting only of primes for any $k$. So we choose $k=n+1$ and take the corresponding $d$ and $-b$ to be the first member of the sequence and difference respectively. Thus all of $d, d-b, d-2b \dots d-nb$ are now primes and are obviously coprime to one another.
Obviously it is possible to choose $a$ such that $\gcd(a,b) = 1$. And the existence of $c$ is guaranteed by the chinese remainder theorem.
This completes the proof.
