Problem: An \emph{irreducible lattice point} is an ordered pair
of integers $(x,y)$ satisfying $\gcd(x,y) = 1$.
Prove that if $S$ is a finite set of irreducible lattice points
then there exists a nonconstant
\emph{homogeneous} polynomial $f(x,y)$ with integer coefficients
such that $f(x,y)=1$ for each $(x,y) \in S$.

\end{enumerate}

Solution: We present two solutions.

\paragraph{First solution (Dan Carmon, Israel).}
We prove the result by induction on $|S|$,
with the base case being Bezout's Lemma ($n=1$).
For the inductive step, suppose we want to add a given pair
$(a_{m+1},b_{m+1})$ to $\left\{ (a_1, \dots, a_m), (b_1, \dots, b_m) \right\}$.
\begin{claim*}
  [Standard]
  By a suitable linear transformation we may assume
  \[ (a_{m+1},b_{m+1}) = (1,0). \]
\end{claim*}
\begin{proof}
  [Outline of proof]
  It would be sufficient to show there exists a $2 \times 2$ matrix
  $T = \left[ \begin{smallmatrix} u & v \\ s & t \end{smallmatrix} \right]$
  with integer entries such that $\det T = 1$ and
  $T \cdot \left[ \begin{smallmatrix} a_{m+1} \\ b_{m+1} \end{smallmatrix} \right]
  = \left[ \begin{smallmatrix} 1 \\ 0 \end{smallmatrix} \right]$.
  Then we could apply $T$ to all the ordered pairs in $S$ (viewed as column vectors);
  if $f$ was a polynomial that works on the transformed ordered pairs,
  then $f(ux+vy, sx+ty)$ works for the original ordered pairs.
  (Here, the condition that $\det T = 1$ ensures that $T\inv$ has integer entries,
  and hence that $T$ maps irreducible lattice points to irreducible lattice points.)

  To generate such a matrix $T$, choose
  $T = \left[ \begin{smallmatrix} u & v  \\ -b_{m+1} & a_{m+1} \end{smallmatrix} \right]$
  where $u$ and $v$ are chosen via B\'{e}zout lemma so that $ua_{m+1} + vb_{m+1} = 1$.
  This matrix $T$ is rigged so that $\det T = 1$ and the leftmost column of $T\inv$ is
  $\left[ \begin{smallmatrix} a_{m+1} \\ b_{m+1} \end{smallmatrix} \right]$.
\end{proof}
\begin{remark*}
  This transformation claim is not necessary to proceed;
  the solution below can be rewritten to avoid it with only cosmetic edits.
  However, it makes things a bit easier to read.
\end{remark*}

Let $g(x,y)$ be a polynomial which works on the latter set.
We claim we can choose the new polynomial $f$ of the form
\[ f(x,y) = g(x,y)^{M} - C x^{\deg g \cdot M-m} \prod_{i=1}^m (b_i x - a_i y). \]
where $C$ and $M$ are integer parameters we may adjust.

Since $f(a_i, b_i) = 1$ by construction we just need
\[ 1 = f(1,0) = g(1,0)^M - C \prod b_i. \]
If $\prod b_i = 0$ we are done,
since $b_i = 0 \implies a_i = \pm 1$ in that case
and so $g(1, 0) = \pm 1$, thus take $M = 2$.
So it suffices to prove:
\begin{claim*}
  We have $\gcd\left( g(1,0), b_i \right) = 1$ when $b_i \neq 0$.
\end{claim*}
\begin{proof}
  Fix $i$. If $b_i = 0$ then $a_i = \pm 1$ and $g(\pm 1,0) = \pm 1$.
  Otherwise know
  \[ 1 = g(a_i, b_i) \equiv g(a_i, 0) \pmod{b_i} \]
  and since the polynomial is homogeneous with $\gcd(a_i, b_i) = 1$
  it follows $g(1,0) \not\equiv 0 \pmod{b_i}$ as well.
\end{proof}
Then take $M$ a large multiple of $\varphi(\prod |b_i|)$ and we're done.

\paragraph{Second solution (Lagrange).}
The main claim is that:
\begin{claim*}
  For every positive integer $N$,
  there is a homogeneous polynomial $P(x,y)$ such that
  $P(x,y) \equiv 1 \pmod N$ whenever $\gcd(x,y) = 1$.
\end{claim*}
(This claim is actually implied by the problem.)
\begin{proof}
  For $N = p^e$ a prime take $(x^{p-1} + y^{p-1})^{\varphi(N)}$
  when $p$ is odd, and $(x^2+xy+y^2)^{\varphi(N)}$ for $p=2$.

  Now, if $N$ is a product of primes,
  we can collate coefficient by coefficient using the
  Chinese remainder theorem.
%  Now suppose $N = q_1 q_2 \dots q_k$ where $q_i$ are prime powers.
%  Look at the polynomial $Q_i$ described above for $i=1, \dots, k$.
%  Now \[ \frac{N}{q_i} Q_i(x,y) \equiv \frac{N}{q_i} \pmod{N} \]
%  for all $x$ and $y$;
%  so we can put together the polynomials $\frac{N}{q_i} Q_i$ by B\'{e}zout lemma.
\end{proof}

Let $S = \left\{ (a_i, b_i) \mid i=1, \dots, m \right\}$.
We have the natural homogeneous ``Lagrange polynomials''
\[ L_k(x,y) \coloneq \prod_{i \neq k} (b_i x - a_i y) \]
Now let
\[ N \coloneq \prod_k L_k(x_k, y_k) \]
and take $P$ as in the claim.
Then we can take a large power of $P$,
and for each $i$ subtract an appropriate multiple of $L_i(x,y)$; that is, choose
\[
  f(x,y)
  = P(x,y)^{C} - \sum_i L_i(x,y) \cdot Q_i(x,y)
\]
where $C$ is large enough that $C \deg P > \max_i \deg L_i$,
and $Q_i(x,y)$ is any homogeneous polynomial of degree $C \deg P - \deg L_i$
such that $L_k(x_k, y_k) Q_k(x_k, y_k) = \frac{P(x_k, y_k)^C - 1}{N} \cdot L_k(x_k, y_k)$
(which is an integer).