Let $A,B,C$ be $3$ points on the plane with integral coordinates. Prove that there exists a point $P$ with integral coordinates distinct from $A,B$ and $C$ such that the interiors of the segments $PA,PB$ and $PC$ do not contain points with integral coordinates.
Problem
Source: Singapore IMO TST 2007, Problem 6
Tags: analytic geometry, number theory, greatest common divisor, modular arithmetic
t0rajir0u
08.09.2008 01:35
What is the interior of a segment? Do you just mean that on each of the lines $ PA, PB, PC$ there are no points with integral coordinates between $ P$ and $ A, B, C$ respectively?
mr.danh
08.09.2008 10:15
Yes, the interior of segment PA is the set of points between P,A (except P,A). I did use original words in Singapore TST 2007.
SUPERMAN2
19.05.2009 05:31
Can anyone post a solution please?
polya78
04.01.2012 20:18
Try this. It's not pretty, but I think it works. Let the points be $(a_i,b_i)$, for $i=1,2,3.$ The problem is equivalent to showing that there exists a lattice point $(r,s)$ such that gcd$(r-a_i,s-b_i) = 1$, for $i=1,2,3$. Consider the unit square with bottom left vertex the origin. Each of the four vertices represent a different combination modulo 2, so at least one of them must differ modulo 2 from each of the $(a_i,b_i)$. Call that point $(m,n)$. So $2 \nmid gcd(m-a_i,n-b_i)$, for $i=1,2,3$. Consider $(m+2k,n+2l)$, for $k,l \in \{0,1,2\}$. Those 9 points range over all combinations modulo 3, so at least one is different modulo 3 from the $(a_i,b_i)$. Call it $(m',n')$. So $2,3 \nmid gcd(m'-a_i,n'-b_i)$, for $i=1,2,3$. Now take all the points of the form $(m'+6k,n'+6k)$. Those points represent 5 different pairs modulo 5, so again we can find one $(m",n")$ such that $2,3,5 \nmid gcd(m"-a_i,n"-b_i)$, for $i=1,2,3$. Continuing on this way, for any T, we can find a point $(m'+A,n'+A)$ such that $p \nmid gcd(m'+A-a_i,n'+A-b_i)$, for $i=1,2,3$, where p is any prime less than T. No suppose q is a prime such that $q \mid (m'+A-a_i)$ and $q \mid (n'+A-b_i)$ for some i. Then $q \mid (m'-n'+b_i-a_i)$. But this is impossible if we choose T large enough, so we have a contradiction, and $(m'+A,n'+A)$ is the point we are looking for.
mavropnevma
04.01.2012 21:03
polya78 wrote: Now take all the points of the form $(m'+6k,n'+6k)$. Those points represent 5 different pairs modulo 5, so again we can find one $(m",n")$ such that $2,3,5 \nmid gcd(m"-a_i,n"-b_i)$, for $i=1,2,3$. Continuing on this way, for any T, we can find a point $(m'+A,n'+A)$ such that $p \nmid gcd(m'+A-a_i,n'+A-b_i)$, for $i=1,2,3$, where p is any prime less than T. No suppose q is a prime such that $q \mid (m'+A-a_i)$ and $q \mid (n'+A-b_i)$ for some i. Then $q \mid (m'-n'+b_i-a_i)$. But this is impossible if we choose T large enough, so we have a contradiction, and $(m'+A,n'+A)$ is the point we are looking for. That needs a little clarification. Once we got past the primes $2$ and $3$, assume we found $M,N$ such that $2,3,\ldots, p_{t-1} \nmid \gcd(M-a_i,N-b_i)$, for all $i=1,2,3$. We now build $M_k = M + (p_t-2)!k$, $N_k = N + (p_t-2)!k$, $k=0,1,2,3$, for the next prime $p_t$. By Wilson's theorem we have $(p_t - 2)! \equiv 1 \pmod{p_t}$, so $M_k \equiv M + k \pmod{p_t}$ and $N_k \equiv N + k \pmod{p_t}$, $k=0,1,2,3$. At least for one $k$ we will have the property that $2,3,\ldots, p_{t} \nmid \gcd(M_k-a_i,N_k-b_i)$, for all $i=1,2,3$. Now we can conclude, with having reached far enough, that no prime $q$ will divide the final $\gcd$'s.
polya78
09.01.2012 23:06
Fair point.
Pathological
13.04.2019 18:39
We will first show the following lemma:
$\mathbf{Lemma.}$ Let $x_0, y_0$ be positive integers satisfying $nx + my = c$, for some $c \neq 0$ and relatively prime $m, n \in \mathbb{Z}$, and let $(x_k, y_k) = (x_0 +mk, y_0 - nk)$ for $k \in \mathbb{N}.$ Then, there exists some $k \in \mathbb{N}$ with $\gcd(x_k, y_k) = 1.$
$\mathbf{Proof.}$ Notice that $nx_k + my_k = c$, for all $k \ge 0$. Therefore, if $p|x_k, y_k$, then we must have $p|c$. Let $p_1, p_2, \cdots, p_t$ be the distinct prime divisors of $c$. Then, for each $p_i$, there clearly exists some $a_i \in \mathbb{N}$ with $p_i \nmid \gcd(x_{a_i+p_ik}, y_{a_i+p_ik})$. Hence, it only suffices to solve the system of equations with CRT to produce some $k \in \mathbb{N}$ with $p_i \nmid \gcd(x_k, y_k)$ for all $p_i$'s.
$\blacksquare$
With this lemma, we may now return to the problem. Let the line through $A, B$ have slope $\frac{-m}{n},$ for some relatively prime positive integers $m, n$. (If the line is vertical, let $m = -1, n=0$ and vice versa if horizontal). Call that line $nx +my = c$. Now, consider the lines $nx+my = c \pm 1$. Clearly, one of them must not contain $C$, and neither of them can contain $A$ or $B$. Furthermore, for any lattice point on either of these lines, say $P$, neither $PA$ nor $PB$ contains another lattice point. Therefore, assume WLOG by symmetry that $nx+my = c+1$ doesn't contain $A, B, C.$ Letting $(x, y)$ be on this line and $(x_c, y_c)$ be the coordinates of $C$, it only suffices to apply the lemma for $(x_0, y_0) = (x - x_c, y - y_c)$, noting that $nx_0 + my_0 \neq 0$ because $C$ isn't on the line.
$\square$