This was proposed by John Berman. Solution by 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\}$. By a suitable linear transformation assume $(a_{m+1},b_{m+1}) = (1,0)$. (The transformation is not necessary to proceed but cleans up the presentation that follows.) 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: Claim: $\gcd\left( g(1,0), b_i \right) = 1$ when $b_i \neq 0$. 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. $\blacksquare$ Then take $M$ a large even multiple of $\varphi(\prod b_i)$ and we're done.

Come on don't post solutions so quickly you're killing the hype

The proof goes by induction in the number $n=|S|$ of points of the set. The base case is trivial by Bézout's Theorem. Write $S =\{(a_1,b_1)., \ldots, (a_n,b_n), (a_{n_1},b_{n+1})\}$ and let $g(x,y)$ be a homogeneous polynomial of degree $\ell$ such that $g(a_i,b_i)=1$ for $1 \leq i \leq n$ (by the induction hypothesis). We will construct a homogeneous polynomial $f(x,y)$ of the form $$ f(x,y)=g(x,y)^k + \prod_{i=1}^n (b_ix - a_iy) \cdot h(x,y),$$where $k$ and $h(x,y)$ will be chosen so that the conditions are fulfilled. Note that $f(a_i,b_i) = 1$ for $1 \leq i \leq n$, so we need to ensure that $f$ is a homogeneous polynomial and that $f(a_{n+1},b_{n+1}) = 1$. We need that $$ 1 = f(a_{n+1},b_{n+1}) = g(a_{n+1},b_{n+1})^k + \prod_{i=1}^n (b_ia_{n+1} - a_ib_{n+1})\cdot h(a_{n+1},b_{n+1}). $$If $\gcd\left(\prod_{i=1}^n (b_ia_{n+1} - a_ib_{n+1}),g(a_{n+1},b_{n+1})\right) = 1$, we can use Euler-Fermat's Theorem to guarantee that $h(a_{n+1},b_{n+1})$ is an integer. If not, there would be a prime $p$ such that $p$ divides $g(a_{n+1},b_{n+1})$ and wlog $b_1a_{n+1}-a_1b_{n+1}$. Working modulo $p$, we have that $$ 0 \equiv b_1^{\ell}g(a_{n+1},b_{n+1}) \equiv g(b_1a_{n+1},b_1b_{n+1})\equiv g(a_1b_{n+1},b_1b_{n+1}) \equiv b_{n+1}^{\ell}g(a_1,b_1) \equiv b_{n+1}^{\ell}\mod p.$$Analogously, we have that $a_{n+1}^{\ell} \equiv 0$, which is a contradiction, because $(a_{n+1},b_{n+1})$ is a primitive point. In order to finish, it's enough to prove that for any integer $d\ge 0$ and any integer $M$, there is a homogeneous polynomial $T(x,y)$ of degree $d$ such that $T(a_{n+1},b_{n+1}) = M$. For this, just take $T(x,y) = M(\alpha x + \beta y)^d$, where $\alpha$ and $\beta$ are integers such that $\alpha a_{n+1} + \beta b_{n+1} = 1$.

WLOG all coordinates in $S$ are nonnegative: replace all $(x,y)$ by $(x^2,y^2)$ and replace $x,y$ by $x^2,y^2$ in the polynomial. Then $x_iy_j-x_jy_i\neq 0$ for all $(x_i,y_i),(x_j,y_j)\in S$. Let $S_i$ be the set $S$ with its $i$-th element removed. Consider the polynomial $P_i(x,y)=\prod_{(u,v)\in S_i}(vx-uy)$ which is zero on $S_i$ but some nonzero value $M_i$ at the $i$-th element of $S$. By adding integer multiples of all the $P_i$ to the resulting polynomial, it suffices to show that we can choose a polynomial which is $1\mod \prod M_i$ at every point in $S$. Let $q$ be a prime power in $\prod M_i$. Let $q=p^k$ and consider $f_q(x,y)=x^{2k\varphi(q)}-x^{k\varphi(q)}y^{k\varphi(q)}+y^{2k\varphi(q)}$. By Euler-Fermat's theorem, $f_q(x,y)\equiv 1\pmod{q}$ for any $(x,y)\in S$. Take $f_q(x,y)$ for each $q$. With CRT, we can generate an $f(x,y)$ all of whose coefficients are congruent to the corresponding coefficient of $f_q$ modulo $q$ for each $q$. Then for all $(x,y)\in S$, $f(x,y)\equiv 1\pmod q$ for each $q$, so $f(x,y)\equiv 1$ mod $\prod M_i$. This is what we needed, so we're done. Edit. It is instructive to find and fix the hole in this proof.

msecco wrote: The proof goes by induction in the number $n=|S|$ of points of the set. The base case is trivial by Bézout's Theorem. Write $S =\{(a_1,b_1)., \ldots, (a_n,b_n), (a_{n_1},b_{n+1})\}$ and let $g(x,y)$ be a homogeneous polynomial of degree $\ell$ such that $g(a_i,b_i)=1$ for $1 \leq i \leq n$ (by the induction hypothesis). We will construct a homogeneous polynomial $f(x,y)$ of the form $$ f(x,y)=g(x,y)^k + \prod_{i=1}^n (b_ix - a_iy) \cdot h(x,y),$$where $k$ and $h(x,y)$ will be chosen so that the conditions are fulfilled. Note that $f(a_i,b_i) = 1$ for $1 \leq i \leq n$, so we need to ensure that $f$ is a homogeneous polynomial and that $f(a_{n+1},b_{n+1}) = 1$. We need that $$ 1 = f(a_{n+1},b_{n+1}) = g(a_{n+1},b_{n+1})^k + \prod_{i=1}^n (b_ia_{n+1} - a_ib_{n+1})\cdot h(a_{n+1},b_{n+1}). $$If $\gcd\left(\prod_{i=1}^n (b_ia_{n+1} - a_ib_{n+1}),g(a_{n+1},b_{n+1})\right) = 1$, we can use Euler-Fermat's Theorem to guarantee that $h(a_{n+1},b_{n+1})$ is an integer. If not, there would be a prime $p$ such that $p$ divides $g(a_{n+1},b_{n+1})$ and wlog $b_1a_{n+1}-a_1b_{n+1}$. Working modulo $p$, we have that $$ 0 \equiv b_1^{\ell}g(a_{n+1},b_{n+1}) \equiv g(b_1a_{n+1},b_1b_{n+1})\equiv g(a_1b_{n+1},b_1b_{n+1}) \equiv b_{n+1}^{\ell}g(a_1,b_1) \equiv b_{n+1}^{\ell}\mod p.$$Analogously, we have that $a_{n+1}^{\ell} \equiv 0$, which is a contradiction, because $(a_{n+1},b_{n+1})$ is a primitive point. In order to finish, it's enough to prove that for any integer $d\ge 0$ and any integer $M$, there is a homogeneous polynomial $T(x,y)$ of degree $d$ such that $T(a_{n+1},b_{n+1}) = M$. For this, just take $T(x,y) = M(\alpha x + \beta y)^d$, where $\alpha$ and $\beta$ are integers such that $\alpha a_{n+1} + \beta b_{n+1} = 1$. We have same solution!

My solution is slightly different from the official one but I think mine is easier to figure out. We use induction on $\ell=|S|$. The case $\ell=1$ is given by Bézout's Theorem. For $\ell=2$, say $$ S=\{(x_1,y_1),(x_2,y_2)\}. $$Euclidean's algorithm gives us a linear isomorphism $$ \begin{pmatrix} U\\ V \end{pmatrix} = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} X\\ Y \end{pmatrix} $$satisfying that $(u_1,v_1)=(1,0)$ and $(u_2,v_2)=1$. It suffices for every $(s,t)=1$ to find a homogeneous polynomial with integral coefficients, $P(U,V)$, such that $deg(P)>0$ and $P(1,0)=P(s,t)=1$. If $s=0$ or $t=0$, it's trivial. Otherwise, we let $n=\varphi(t)$ and solve $$ 1=s^{n}+\sum_{i=1}^{n}a_is^{n-i}t^{i}. $$By Euler's theorem, $s^n\equiv 1\pmod t$. Also, $\{s^{n-i}\}$ are invertible when mod t. So we can inductively solve integral $a_1,a_2,\cdot,a_{n-1}$, and finally solve $a_n$. So we can choose $$ P=U^n+\sum_{i=1}^{n}a_iU^{n-i}V^{i}. $$For $\ell\geq 3$, we similarly assert a linear isomorphism. $S=\{(1,0),(u_2,v_2),\cdots,(u_{\ell},v_{\ell})\}$. By induction hypothesis, there is a homogeneous polynomial $F(U,V)$ of degree $\alpha>0$ with integral coefficients satisfying that $F(u_j,v_j)=1$ for $j=2,3\cdots,\ell$. Define another homogeneous polynomial $G(U,V)$ with integral coefficients: $$ G(U,V)=\prod_{j=2}^{\ell}(v_jU-u_jV). $$Then $G(u_j,v_j)=0$ for $j=2,3\cdots,\ell$. $G(1,0)=\prod_{j=2}^{\ell}v_j$. On the other hand, $F(1,0)$ is the coefficient of the $X^{\alpha}$ term of $F$. Since $F(u_j,v_j)=1$ for $j=2,3\cdots,\ell$, $F(1,0)$ is coprime to $v_j$ for $j=2,3\cdots,\ell$. Let $F'=F^{\ell-1}$ and $G'=G^{\alpha}$. Then $F',G'$ are homogeneous polynomials of the same degree with integral coefficients. Let $s=F'(1,0)$, $t=G'(1,0)$. We have $(s,t)=1$ and thus a polynomial $P$ given by the case $\ell=2$, $S=\{(1,0),(s,t)\}$. Now $P(F',G')$ is what we want.

Basic ideas. Let $S = \{(x_1, y_1), (x_2, y_2), \dots, (x_m, y_m)\}$ and let $P(x, y) = a_0 x^n + a_1 x^{n-1} + \dots + a_n y^n$. Also, assume $(x, y)$ and $(-x, -y)$ are not both in $S$, since for even $n$ they evaluate to the same thing, and we claim existence for some even $n$. 1. Prove the result $\pmod N$ for any positive integer $N$. For this, it suffices to prove $\pmod {p^k}$, then we can splice using Chinese Remainder Theorem. However, notice that if $n$ is a multiple of $2k \phi(p^k)$, then $P(x, y) = x^n - x^{n/2} y^{n/2} + y^n$ is either $0 - 0 + 1 = 1$, or $1 - 1 + 1 = 1$, or $1 - 0 + 0 = 1 \pmod {p^k}$, using Euler's theorem and casework on whether $x, y$ is divisible by $p$ (both cannot be, due to relatively prime condition). Thus, the choice $a_n = 1, a_0 = 1, a_{n/2} = -1$ and other $a_i = 0$ in $\pmod {p^k}$ is valid. All we then need is to choose $n$ to be the lcm of the $2k \phi(p^k)$. 2. Prove the existence of $N = N(x_1, y_1) > 0$ such that $P(x_1, y_1) = N$ and $P(x_i, y_i) = 0$ for $2 \le i \le m$. Assume $n > m + 1$. First if $x_1 = 0$ then $y_1 = \pm 1$ to ensure $(x_1, y_1)$ is primitive. The rest is easy: choose $a_0 = x_1$ and $a_i = 0$ for $1 \le i \le n$. Similarly for $y_1 = 0$. Thus, assume $x_1, y_1 \neq 0$. By Bezout's lemma, we can assume there exist integers $a, b$ such that $a x_1 - b y_1 = 1$. The crucial idea is to look at the polynomial $$f(t) = t \cdot (at - b)^{n-m-2} \prod_{i=2}^m (y_i t - x_i).$$Let $a_i$ be the coefficient of $t^{n-i}$ in $f$. Then $a_0 = a_n = 0$ because $f$ is degree $n-1$ (or less) and divisible by $t$. (It is nonzero since $(x_i, y_i) \neq (0, 0)$ as it is primitive.) Then for $2 \le i \le m$, we have for $y_i \neq 0$ that $$P(x_i, y_i) = y_i^n f(\frac{x_i}{y_i}) = 0,$$and for $y_i = 0$, we have $P(x_i, y_i) = a_0 x_i^n = 0$. On the other hand, we have $P(x_1, y_1) \neq 0$ because $\frac{x_1}{y_1} \neq 0$ and is not the value of $\frac{x_i}{y_i}$ for some $i$ (as both are primitive, this will imply $x_1 = -x_i$ and $y_1 = -y_i$, contradiction to our beginning assumption). Thus since negating the $a_i$ negates $P(x_1, y_1)$, we can choose $N = |P(x_1, y_1)|$. (It is independent of $n$ because $(ax_1 - by_1)^{n-m-2} = 1$.) Now the result clearly follows by a simple linear algebra linear combination argument. (The $a_i$'s form a linear system of equations, and therefore if we express the RHS as an $m$-dimensional vector, then the solution space is closed under addition and scalar multiplication. Therefore, we can take Claim 1 and Claim 2 vectors (in Claim 1, take $N$ to be the lcm of $N(x_1, y_1), N(x_2, y_2), \dots, N(x_m, y_m)$ in Claim 2) and form $(1, 1, 1, \dots, 1)^T$, which must be in the space, completing the proof.)

msecco wrote: If $\gcd\left(\prod_{i=1}^n (b_ia_{n+1} - a_ib_{n+1}),g(a_{n+1},b_{n+1})\right) = 1$, we can use Euler-Fermat's Theorem to guarantee that $h(a_{n+1},b_{n+1})$ is an integer. I'm sorry to bother you, since your solution seems very nice, I had the same begining but then I got stuck on what I hilighted in your solution : it is ok that $\gcd\left(\prod_{i=1}^n (b_ia_{n+1} - a_ib_{n+1}),g(a_{n+1},b_{n+1})^k\right) = 1$ but the thing is that we want to find $k$ and $C$ such that $1=g(a_{n+1},b_{n+1})^k + C\prod_{1 \leqslant i \leqslant n} (b_i a_{n+1}-a_ib_{n+1})=1$, but the fact that $\gcd\left(\prod_{i=1}^n (b_ia_{n+1} - a_ib_{n+1}),g(a_{n+1},b_{n+1})^k\right) = 1$ only proves that there exist $A,C$ such that $1=Ag(a_{n+1},b_{n+1})^k + C\prod_{1 \leqslant i \leqslant n} (b_i a_{n+1}-a_ib_{n+1})=1$. Can you explain me why $A=1$ without loss of generality? Thank you a lot,

@above: You also have the freedom to choose $k$, so just choose $k$ such that $g(a_{n+1},b_{n+1})^k \equiv 1 \pmod {(\prod_{1 \leq i \leq n} (b_ia_{n+1} - a_ib_{n+1})}$

@fattypiggy123: thank you, I totally forgot this! I am a mess!

We induct, $n=1$ is Bezout's. We will find $f$ homogeneous that works for $(a_i,b_i)\forall i\le n$. By bezout we can take $ma_n-\ell b_n=1$ and $(m,n)=1$. Notice $\forall i\le n-1$ we have $(ma_i-\ell b_i, b_na_i - a_nb_i)=1$ since if $p$ divides them both, then WLOG $p|m,p|b_i,p|b_n$ but then $p|ma_n-\ell b_n=1$. Thus we can use the induction hypothesis and get $g$ is a homogeneous polynomial of degree $d$ that works for $(ma_i-\ell b_i, b_na_i - a_nb_i)\forall i\le n-1$. Notice $(g(ma_n-\ell b_n, b_na_n - a_nb_n),b_na_i-a_nb_i)=1$. Indeed, the first number is just $X(ma_n-\ell b_n)^d=X$ where $X$ is the $x^d$ coefficient of $g(x,y)$. But $(X,b_na_i-a_nb_i)=1$ since $X(ma_i-\ell b_i)^d \equiv g(ma_i-\ell b_i,b_na_i-a_nb_i)=1 (\text{mod }b_na_i-a_nb_i)$. So $$(g(ma_n-\ell b_n, b_na_n - a_nb_n),(b_na_1-a_nb_1)\cdots (b_na_{n-1}-a_nb_{n-1}))=1$$ and take by Euler's Theorem $E$ and $M$ with $$g(ma_n-\ell b_n, b_na_n - a_nb_n)^E = 1 + M(b_na_1-a_nb_1)\cdots (b_na_{n-1}-a_nb_{n-1})$$. WLOG we assume $E>n$. Then $$f(x,y)=g(mx-\ell y, b_nx-a_ny)^E - (mx-\ell y)^{Ed-n+1}M\left( \prod_{i=1}^{n-1} (b_na_i-a_nb_i)(mx-\ell y)-(ma_i-\ell b_i)(b_nx-a_ny) \right)$$ works. $\square$

Interestingly this problem is a special case of Lemma 7.3 of this paper: https://arxiv.org/pdf/1604.01704.pdf. (Someone pointed out to me that this paper was potentially related.) The lemma is the following: Let $X$ be a finite scheme over $\operatorname{Spec}\mathbb{Z}.$ Then $\operatorname{Pic}(X)$ is finite. The proof of this lemma should translate in elementary terms into the proof already posted. The advantage of this formulation is that from an algebraic geometer's point of view, such statements are easy applications of the technique of devissage - which makes it clear what the right direction to proceed in is.

Induct on $\left | S \right |$. If $\left | S \right | = 1$ the problem is obvious. Now suppose problem is true when $\left | S \right | = m$ and we aim to prove it when $\left | S \right | = m+1$. Let $S = \left \{ (p_1, q_1), (p_2, q_2), ..., (p_{m+1}, q_{m+1}) \right \}$. Use inductive hypothesis and take a homogeneous polynomial with integer coefficients $P(x, y)$ such that $P(p_i, q_i) = 1$ for every $i = 1, 2, ..., m$. Let $d$ the degree of polynomial $P$. Now, for every positive integer $t$ such that $dt > m$ and a homogeneous polynomial with integer coefficients $Q(x, y)$ that has degree of $dt-m$, $T(x, y) = \left ( P(x, y) \right )^t - \prod_{i=1}^{m}\left ( q_ix-p_iy \right ) \cdot Q(x, y)$ is a homogeneous polynomial with integer coefficients such that $T(p_i, q_i) = 1$ for every $i = 1, 2, ..., m$. Since $(p_{m+1}, q_{m+1})$ is primitive, there exists integers $a, b$ such that $ap_{m+1} + bq_{m+1} = 1$. Take $Q(x, y) = c(ax+by)^{dt-m}$ and we will define $t$ and $c$ shortly after. Let $U = P(p_{m+1}, q_{m+1})$ and $V = \prod_{i=1}^{m}\left ( q_ip_{m+1}-p_iq_{m+1} \right )$. If $gcd \left ( U, V \right ) \neq 1$, there exists a prime $p$ and index $i$ between $1$ and $m$ such that $p$ divides both $P(p_{m+1}, q_{m+1})$ and $q_ip_{m+1}-p_iq_{m+1}$. Both $p_i$ and $q_i$ can't be divisible by $p$, so WLOG $q_i$ is not divisible by $p$. Then $q_{m+1}^d = q_{m+1}^d P(p_i, q_i) = P(p_iq_{m+1}, q_iq_{m+1}) \equiv P(q_ip_{m+1}, q_iq_{m+1}) = q_i^d P(p_{m+1}, q_{m+1}) \equiv 0 (mod p)$, so $q_{m+1}$ is divisible by $p$. Since $q_ip_{m+1}-p_iq_{m+1}$ is divisible by $p$, this implies that $p_{m+1}$ is also divisible by $p$, a contradiction. Hence $gcd \left ( U, V \right ) = 1$. Finally, we can take sufficiently large $t$ and integer $c$ such that $U^t - cV = 1$ by Euler's theorem, which finishes the construction of our desired polynomial $T(x, y)$.

It is interesting that none of the above solutions refers to Lagrange Interpolation.

silouan, Lagrange interpolation based solution looks possible, but containing many annoying technical details.

Maybe, I didn't write down the details, but for me it was the first (and I think straightforward) idea that I had. Take the Lagrange Interpolation polynomial, then try to make the coefficients integers by subtracting a polynomial which is zero on the points of the set.

silouan wrote: Maybe, I didn't write down the details, but for me it was the first (and I think straightforward) idea that I had. Take the Lagrange Interpolation polynomial, then try to make the coefficients integers by subtracting a polynomial which is zero on the points of the set. I tried that and couldn't make it work, but I think it probably is possible. If so, it's going to be disgusting, though.

1. For each prime $p$, there exists a nonconstant homogeneous polynomial $f_p(x, y)$ with the following property: if $\gcd(x, y) = 1$, then $\gcd(f_p(x, y), p) = 1$. Proof. If $p = 2$, take $x^2 + xy + y^2$; if $p \ge 3$, take $x^{p - 1} + y^{p - 1}$. 2. For each positive integer $m$, there exists a nonconstant homogeneous polynomial $f_m(x, y)$ with the following property: if $\gcd(x, y) = 1$, then $\gcd(f_m(x, y), m) = 1$. Proof. Let $p_1 < \dots < p_k$ be the primes dividing $m$. Raise each of $f_{p_1}, \dots, f_{p_k}$ to a power so that all of them have degree $\text{lcm}(\deg f_{p_1}, \dots, \deg f_{p_k})$, and combine them using CRT. (Here $f_m$ refer to the polynomiaIs in step 1. If $m = 1$, then anything works.) 3. For each positive integer $m$, there exists a nonconstant homogeneous polynomial $f_m(x, y)$ with the following property: if $\gcd(x, y) = 1$, then $f_m(x, y) \equiv 1 \pmod{m}$. Proof. $f_m(x, y)^{\phi(m)}$ works. (Here $f_m$ refers to the polynomial from step 2.) At this stage, WLOG add points to $S$ to make $S = -S$. Let $S^{+} = S \cap \left(\{(x, y) \mid y > 0\} \cup (1, 0)\right)$ and $S^{-} = -S^{+}$. Now, $S = S^{+} \sqcup S^{-}$ and $S^{-} = -S^{+}$, so if we find a polynomial which works for $S^{+}$, we may square it to make its degree even, and then it will work for $S^{-}$ as well. The upshot of this is that now we may suppose $S$ is a subset of $\{(x, y) \mid y > 0\} \cup (1, 0)$. Let $S = \{(x_1, y_1), \dots, (x_k, y_k)\}$, and define $M = \prod_{i < j} (x_iy_j - x_jy_i)$. Note $M \neq 0$. 4. For any integer $d \ge k - 1$, there exist homogenous integer-coefficient polynomials $P_1(x, y), \dots, P_k(x, y)$ of degree $d$ such that $P_i(x, y) = M$ at $(x_i, y_i)$ and $P_i(x, y) = 0$ at the other points of $S$. Proof. Consider the degree $k - 1$ polynomial $\prod_{i \neq r} (xy_i - yx_i)$. It is zero at the points $(x_i, y_i)$ with $i \neq r$, and is a factor of $M$ at $(x_r, y_r)$. Now, multiply it by a constant to make its value equal to $M$ at $(x_r, y_r)$. Finally, multiply this by a degree $d - (k - 1)$ polynomial which is one at $(x_r, y_r)$ (which exists by Bezout). 5. The problem itself. Proof. Consider $f_M(x, y)$; it is $1 \pmod{M}$ at each point $(x_k, y_k)$. Suppose that $f_M(x_i, y_i) = a_i M + 1$ for all $i$; by raising $f_M$ to a large power, we may ensure its degree is $\ge k - 1$. Finally, the polynomial \[f_M(x, y) - a_1 P_1(x, y) - \dots - a_k P_k(x, y)\]works. (Here, each $P_i$ is selected to be the same degree as $f_M$.)

Here is a solution slightly different than the official solution, but I believe much more motivated. We induct on $k=\left | S \right |;$ for $k=1$ the problem follows directly from Bezout's lemma. Key Fact: Consider a pair of homogenous polynomials $P,Q \in \mathbb{Z}[x,y]$ of the same degree with the following property: For all $a,b \in \mathbb{Z},$ $\text{gcd}(a,b)=1$, then $\text{gcd}(P(a,b),Q(a,b))=1.$ Then, it suffices to solve the problem for the set $$S'=\{(P(x,y),Q(x,y)) \mid (x,y) \in S\}.$$ This fact is pretty easy to prove; by assumption, every point in $S'$ is still primitive, and if we can find a polynomial that works for $S',$ we can substitute $x \to P(x,y), y \to Q(x,y),$ and get a homogenous polynomial that works for $S,$ since the composition of homogenous polynomials is a homogenous polynomial. Now, our strategy will be to find polynomials that satisfy these conditions and send the first two points in $S$ to the same point; then, we only have $k-1$ distinct points, and induction will finish. In particular, we can take $P(x,y)=x,Q(x,y)=x-y,$ we get a reduction where we take $(x,y) \to (x,x-y).$ By iterating this using the Euclidean algorithm, we can reduce one element of $S$ to $(1,0).$ Suppose some other element of $S$ is $(z,w),$ then we will construct polynomials that map the first two points to the same point. Let $n>1$ be such that $w \mid z^n-1.$ Then by Bezout's lemma, there exist integers $a,b$ such that $$a \cdot z^{n-1}+b \cdot w^{n-1}=\frac{1-z^n}w$$$$\implies z^n+a\cdot wz^{n-1}+b \cdot w^n=1$$Then in the key fact, we take $(P(x,y),Q(x,y))=(x^n+a\cdot xy^{n-1}+b \cdot y^n,y^n).$ It's clear that $P,Q$ are homogenous of degree $n,$ and if $p \mid P(x,y),Q(x,y)$ is prime, then $$p \mid y^n \implies p \mid y \implies p \mid x,$$so $x,y$ are not coprime. Conversely, if $x,y$ are coprime, so are $P(x,y),Q(x,y).$ Now, note that $$(P(1,0),Q(1,0))=(1,0)$$and $$(P(z,w),Q(z,w))=(1,w^n).$$Now, we take two more polynomials $R(x,y),S(x,y)$ to finish. There are many options, but $$R(x,y)=x^2,S(x,y)=w^n xy-y^2$$works fine. Applying these to every point in $S',$ we reduce both of the first two points to $(1,0),$ and the induction hypothesis finishes.

We proceed by induction on $|S|$. When $|S|=1$, Bezout suffices. For our inductive step, suppose $|S|<k$ works. Then, if $S$ is composed of $\{(x_i,y_i)\}_{i\le k}$, we have a homogenous polynomial $Q(x,y)$ of degree $n$ such that $Q(x_i,y_i)=1$ for all $i<k$. Note that the coefficient of $x^n$ is coprime to all $y_i$ for $i<k$, or else $Q(x_i,y_i)$ would have a factor greater than $1$ for that particular $i$. So, if we consider $R(x,y)=\prod_{i=1}^{k-1}(y_ix-x_iy)$, the coefficients of $x^n$ are coprime, so we can choose a suitable factor $r$ such that $rR(x,y)+Q(x,y)$ has coefficient of $x^n$ that is coprime to $y_k$, which in turn implies that if we consider mapping all our pairs $(x_i,y_i)\to (rR(x_i,y_i)+Q(x_i,y_i),y_i^n)$, all pairs remain relatively prime, as the first $k-1$ pairs have first element $1$, and for the last one we have $$\text{rad}(\gcd(rR(x_k,y_k)+Q(x_k,y_k),y_k^n))=\text{rad}(\gcd(rR(x,y)+Q(x,y),y_k))=\text{rad}(\gcd(rR(1,0)+Q(1,0),y_k))=1$$by construction. Also, note that all pairs have been mapped by the same homogenous polynomials, so it suffices to find a polynomial for the new pairs, as reverse substitution will recover a polynomial for the initial pairs. Now, we can do the exact same thing to the new $y_i$s to transform them all to $1$s, so we get a new set of $k$ pairs such that $k-1$ of them are $(1,1)$s and the last one is still relatively prime. Finally, perform $(x,y)\to (x,y-x)$ to transform the first $k-1$ to $(1,0)$. So, we only need to solve the case when $|S|=2$ and one of our pairs is $(1,0)$. Now, if our other pair is $(a,b)$, we can explicitly construct a polynomial $P(x,y)$ such that the coefficient of $x^n$ is $1$ and $P(a,b)=1$. To do this, choose $\deg P=n$ such that $a^n\equiv 1\pmod b$. Then, $b|a^n-1$. Now, choose the coefficient of $xy^{n-1}$ such that $b^2|a^n+c_1ba^{n-1}-1$. Then, choose the coefficient of $x^2y^{n-2}$ such that $b^3|a^n+c_1ba^{n-1}+c_2b^2a^{n-2}-1$. Continue inducting upwards until we get that $b^n|P(a,b)-c_nb^n-1$. Now, as $P(a,b)-c_nb^n\equiv 1\pmod{b^n}$, we can choose a suitable $c_n$ such that $P(a,b)=1$, as desired. So, as we can find a suitable polynomial for our particular $2$ variable case, we can back substitute 3 times to transform $P$ into a valid homogenous polynomial for our initial coprime pairs.

Induct on $|S|$. The result is immediate for $|S|=1$ by Bézout's Theorem. Let $|S'|=k-1$ and $(x^*,y^*)\not\in S'$ be a primitive point. Let $S=S'\cup\{(x^*,y^*)\}$. The induction hypothesis guarantees a polynomial $p$ such that $p(x',y')=1$ for all $(x',y')\in S$ and Bézout's Theorem guarantees a choice of $a,b$ for which $ax^*-by^*=1$. We claim that $\gcd(p(x^*,y^*),x^*y'-y^*x')=1$ for all $(x',y')\in S'$. Note that since $\gcd(x^*,y^*)=1$, there exists a linear transformation taking $x^*\to 1,y^*\to 0$ and keeping integers as integers and it suffices to compute the gcd in that case. Then the expression is \[\gcd(a_0,y')\]where $p(x,y)=a_0x^n+a_1x^{n-1}y+\cdots+a_ny^n$. But then this is immediately $1$ because otherwise $1<\gcd(a_0,y')\mid 1$, absurd. Now, note that there must exist some $M>|S|$ for which \[p(x,y)^M \equiv 1\pmod{\displaystyle\prod_{(x',y')\in S'} (x^*y'-y^*x')}\]by the previous observation. Let $c=\frac{p(x,y)^M-1}{\displaystyle\prod_{(x',y')\in S'} (x^*y'-y^*x')}$ and $d=M-|S'|$. Then the polynomial \[p(x,y)^M - c\cdot (ax-by)^d\prod_{(x',y')\in S'}(xy'-yx')\]works because it works for $(x',y')\in S'$ and we engineered it to work for $(x^*,y^*)$.

This was very cool! Say the elements of $S$ are $(x_0, y_0), (x_1,y_1), \cdots, (x_k,y_k)$. Induct on $k$, the base case being bezout's theorem. WLOG by changing $(x,y) \rightarrow (x-y,y)$ and other things, assume $x_0 = 0, y_0 = 1$. By the inductive hypothesis, let $P$ be the homogenous polynomial of degree $n$ such that $P(x_i, y_i) = 1$ for all $1 \le i \le k$. Let $Q(x,y) = \prod_{i=1}^k (x_iy - y_ix)$. It satisfies $Q(x_i, y_i) = 0$ for all $1 \le i \le k$. Let $M = Q(0,1) = \prod_{i=1}^k x_i$. Let the coefficient of $y^n$ in $P$ be $z$. I claim $M$ and $z$ are coprime. Suppose not, and say $p | z$ and $p | M$, then there is a $j$ such that $p | x_j$. But now $1 = P(x_j, y_j) \equiv 0 \pmod p$, a contradiction, so they're coprime. Now we're just done, consider a number $c$ such that $z^c \equiv 1 \pmod M$, which exists since they were coprime. Now consider the polynomial $R(x,y) = P(x,y)^c - lQ(x,y)$. This is still $1$ for all $(x_i, y_i)$ with $1 \le i \le k$, but also since $P(0,1)^c = z^c \equiv 1 \pmod M$, we can choose $l$ such that $R(0,1) = 1$ as well, which completes the induction. $\blacksquare$

I think the following solution hasn't been posted yet. It is pretty straightforward. We induct on $n=|S|$. The base case $n=1$ is done by Bezout. For a positive integer $d$, let $H_d$ be the set of homogeneous polynomials in $\mathbb{Z}[x,y]$ of degree $d$, together with the zero polynomial. Let $S=\{(x_i,y_i)\}_{i=1}^n$. From now on we assume $S$ is ordered. By Bezout, for each $i=1,\dots,n$ we can choose a linear polynomial $l_i\in H_1$ with $l_i(x_i,y_i)=1$. For a polynomial $P(x,y)$ we define $P(S)$ as the tuple $\left(P(x_i,y_i)\right)_{i=1}^n$. Note that if some element of $P(S)$ is nonzero, then $P\not\equiv 0$ so $\deg(P)$ is well-defined. Our goal is to prove that there exist a positive integer $d$ and a polynomial $P\in H_d$ with $P(S)=(1,\ldots,1)$. Now we prove the case $n=2$. Define $a,b\in\mathbb Z$ as the unique integers satisfying $l_1(S)=(1,a)$ and $l_2(S)=(b,1)$. Hence $Q=al_2-l_1$ satisfies $Q(S)=(ab-1,0)$. Since $\gcd(ab-1,b)=1$ and by Euler's theorem, there exist $m\in\mathbb N$ and $t\in\mathbb Z$ with $b^m-(ab-1)t=1$. Now $R=l_2^m-tQ\cdot l_1^{m-1}$ satisfies $R\in H_m$ and $R(S)=(1,1)$. To finish the induction, assume $n\ge 3$ and the problem is true for $n-1$. For a positive integer $m$ and an integer $x$, let $(x)_m=(\overbrace{x,\ldots,x}^{m\text{ times}})$. By induction hypothesis, there exist $a,b,c\in\mathbb Z$ and homogeneous polynomials $P_1,P_2,P_3\in\mathbb Z[x,y]$ with $$\begin{cases} P_1(S)&=(a,1,1,(1)_{n-3})\\ P_2(S)&=(1,b,1,(1)_{n-3})\\ P_3(S)&=(1,1,c,(1)_{n-3}) \end{cases}$$We can assume WLOG that $P_1,P_2,P_3$ are of the same degree $d$. Hence $Q=(P_1-P_2)(P_1-P_3)$ satisfies $Q\in H_{2d}$ and $Q(S)=((a-1)^2,(0)_{n-1})$. Since $\gcd((a-1)^2,a)=1$ and by Euler's theorem, there exist $m\in\mathbb{N}_{\ge 2}$ and $t\in\mathbb Z$ with $a^m-(a-1)^2t=1$. Now $R=P_1^m-tQ\cdot l_1^{d(m-2)}$ satisfies $R\in H_{md}$ and $R(S)=(1)_n$.

Amir Hossein wrote: An ordered pair $(x, y)$ of integers is a primitive point if the greatest common divisor of $x$ and $y$ is $1$. Given a finite set $S$ of primitive points, prove that there exist a positive integer $n$ and integers $a_0, a_1, \ldots , a_n$ such that, for each $(x, y)$ in $S$, we have: $$a_0x^n + a_1x^{n-1} y + a_2x^{n-2}y^2 + \cdots + a_{n-1}xy^{n-1} + a_ny^n = 1.$$ Proposed by John Berman, United States Awesome problem! We will induct on \(\lvert S\rvert\), with the base case being Bezout's. Let \(S=\{(x_1,y_1),\hdots,(x_m,y_m)\}\). Let\(g(x,y)=\sum_{i=0}^na_ix^{n-i}y^i\) is a working polynomial for \(S\), then note that \[f(x,y)=g(x,y)^{A}+Bq(x,y)\prod_{i=1}^m(x_iy-y_ix)\]is also a working polynomial, where \(q\) is a homogeneous polynomial of degree \(\deg g^{A}-m\). Now, let \((a,b)\) be a primitive point which is added as an extra element to \(S\). Then u need \(f(a,b)=1\). We prove a claim. Claim 1. \(g(a,b)\) is coprime to \(\prod_{i=1}^m(x_ib-y_ia)\) Proof. We prove that \(g(a,b)=\sum_{i=1}^na_ix^{n-i}y^i \) is coprime to each of \(x_ib-y_ia\). Assume that there exists a prime \(p\) that divides both \(x_ib-y_ia\) and \(g(a,b)\). If \(p\) divides \(a\), then \(p\) must divide \(b\), a contradiction (note \(p\mid g(a,b)\)). Similarly if \(p\mid x_i\) then \(p\mid y_i\), a contradiction yet again. Therefore \(p\nmid a,b,x_i,y_i\). Now, note that \(\frac{a}{b}\equiv\frac{x_i}{y_i}\pmod{p}\). Then, since \(p\mid g(a,b)\) and \(\gcd(p,b)=1\), it forces \(p\mid g\left(\frac{a}{b},1\right)\) and so \(p\mid g\left(\frac{x_i}{y_i},1\right)\) too. Since \(p\nmid y_i\) too, it forces \(g(x_i,y_i)=1\) to be divisible by \(p\), a plain contradiction, therefore our claim is true. $\blacksquare$ Back to the problem, since \(g(a,b)\) is coprime to \(N=\prod_{i=1}^m(x_ib-y_ia)\), choose \(q(a,b)\) such that it is coprime to \(g(a,b)\), you can choose \(q(x,y)=x^{\deg g^A-m}\) for example. Then, there exists \(A\) so that\(g(a,b)^A=1\pmod{Nq(a,b)}\). Choosing \(B=\frac{1-g(a,b)^A}{Nq(a,b)}\) does our job, completing the inductive step and hence solves the problem. $\blacksquare$

Definition 1: We say a homogeneous polynomial with integer coefficients $P$ over $a, b$ is pure with respect to a positive integer $s$ if for every $\gcd(x, s) = 1$, we have $\gcd(P(x, s), s) = 1$. Notice this is equivalent to saying the coefficient of $x^{\text{Deg }P}$ is coprime to $s$ by taking mod $s$ for arbitrarily large $n$. Definition 2: We say a homogeneous polynomial with integer coefficients $P$ over $a, b$ is perfect over a set of primitive points $S$ if for every $(x, y) \in S$ we have $P(x, y) = 1$. Lemma 1: For positive integers $a, b, c$ such that $\gcd(a, c) = 1$ and $\gcd(b, c) = 1$, there exists a positive integer $n \geq 2$ such that $v_p(c(a^{n-1}-b^{n-1})) \leq v_p(a^n-b^n)$ for each $p \mid c$.

Lemma 2: If $v_p(a) \leq v_p(b)$ for every $p \in S$ for a finite set of primes $S$, then there exists $c$ such that $v_p(ca+b)$ is arbitrarily large for all $p \in S$.

Theorem 1: For positive integers $a, b, c$ such that $\gcd(a, c) = 1, \gcd(b, c) = 1$, there exists a positive integer $n$ and a monic integer polynomial of degree $n$, $P(x) = x^n+a_1x^{n-1}+\cdots+a_n$, such that $a_i$ is a multiple of $c^i$ for $1 \leq i \leq n-1$, and such that $P(a) = P(b)$.

Corollary 1: There exists a homogeneous integer polynomial $P(x, y)$ such that $P(a, c) = P(b, c) = 1$ and $P$ is pure with respect to $c$.

Theorem 2: For a finite set of primitive points $S$ such that all points in $S$ have $y$-value $s$, there exists a homogeneous integer polynomial $P(x, y)$ that is pure with respect to $s$ and perfect over $S$.

Theorem 3: For any finite set of primitive points $S$, there exists a homogeneous integer polynomial $P(x, y)$ such that $P$ is constant over $S$.

Theorem 4: For any finite set of primitive points $S$ and positive integer $s$, there exists a homogeneous integer polynomial $P(x, y)$ that is pure with respect to $s$.

Theorem 5: For any finite set of primitive points $S$, there exists a homogeneous integer polynomial $P(x, y)$ such that $P$ is perfect over $S$.

Q.E.D.

For a polynomial $P(x, y)$, let $[x^ay^b]P(x, y)$ denote the coefficient of $x^ay^b$ in $P(x, y)$. For a given positive integer $m$, let it decompose into prime powers $P = \{p_1^{a_1}, p_2^{a_2}, ...\}$. Choose $N = N(m) \in \mathbb{N}$ such that $\varphi(p_i^{a_i}) \mid N$ and $N > \max(\{a_i\})$. Furthermore, force the condition that if $a \mid b$ then $N(a) \mid N(b)$ (this just involves adding more factors to $N(b)$). Then for all integers $x$, $x^N \equiv$ 0 or 1 $\pmod{p_i^{a_i}}$. Call a homogeneous polynomial $P(x, y) = a_0x^n + a_1x^{n-1}y + ... + a_ny^n$ $m$-good if $n \equiv 0 \pmod{N}$, all terms are of the form $Cx^{kN}y^{n-kN}$ and $a_0 \equiv a_n \equiv a_0 + a_1 + ... + a_n \equiv 1 \pmod{m}$. By our forced condition, if $a \mid b$, then $P(x, y)$ is $b$-good $\Rightarrow$ it is $a$-good. Claim 1: An $m$-good polynomial $P$ satisfies $P(x_z, y_z) \equiv 1 \pmod{m}$ for all primitive pairs $(x_z, y_z)$. Proof: For all $p_i^{a_i}$: i) If $(x_z^N, y_z^N) \equiv (1, 1) \pmod{p_i^{a_i}}$, we have $P(x_z, y_z) \equiv a_0 + a_1 + ... + a_n \equiv 1 \pmod{m}$. ii) If $(x_z^N, y_z^N) \equiv (0, 1) \pmod{p_i^{a_i}}$ we have $P(x_z, y_z) \equiv a_0 \equiv 1 \pmod{m}$. iii) If $(x_z^N, y_z^N) \equiv (1, 0) \pmod{p_i^{a_i}}$ we have $P(x_z, y_z) \equiv a_n \equiv 1 \pmod{m}$. Since $x_z, y_z$ cannot share a factor of $p_i$, this means that for any primitive $(x_z, y_z)$, $P(x_z, y_z) \equiv 1 \pmod{m}$. $\square$ As a generalisation, call a homogeneous polynomial $P(x, y) = a_0x^n + ... + a_ny^n$ $(S, m)$-good if it is $m$-good, $a_0 = 1$, and for every $(x_i, y_i) \in S$, $P(x_i, y_i) = 1$. Similar to above, if $P(x, y)$ is $(S, b)$-good and $a \mid b$, then it is also $(S, a)$-good. The existence of an $(S, m)$-good polynomial proves the problem statement. Note also that $P(1, 0) = 1$. Claim 2: Consider any $(S, m)$-good polynomial $P(x, y)$ of degree $n$. Then $P(x, y)^d$ is also an $(S, m)$-good polynomial. Proof: It is clear that the resultant polynomial is still homogeneous with degree $nd$. $nd \equiv 0 \pmod{n} \Rightarrow nd \equiv 0 \pmod{N}$, and since all powers in $P(x, y)$ are multiples of $N$, since the powers in $P(x, y)^d$ are sums of powers in $P(x, y)$ they are also multiples of $N$. $[x^{nd}]P(x, y) = 1^d = 1$. $[y^{nd}]P(x, y) \equiv 1^d \equiv 1 \pmod{m}$. The sum of the coefficients of a polynomial is the value at $(1, 1)$, and $P(1, 1)^d \equiv 1^d \equiv 1 \pmod{m}$. Furthermore, $P(x_i, y_i)^d = 1^d = 1$ for all $(x_i, y_i) \in S$. $\square$ Claim 3: Given a primitive $(x_z, y_z)$ and a positive integer $m$, there exists $(\{(x_z, y_z)\}, m)$-good polynomials with arbitrarily large coefficients. Proof: $(x_z, y_z)$ primitive $\Rightarrow (x_z^{pN}, y_z^{pN})$ primitive for any $p$, so choose $pN = k\varphi(y_z^{M+N})N$ where $M$ is to be chosen later. We choose $k$ such that $pN > M + N$ and $p > 4$ if necessary. By Bezout's Lemma, there exists $a_0, a_4$ such that $a_0x_z^{pN} + a_4y_z^{pN} = 1$. We claim that we can find a new pair $(a_0', a_4')$ such that $a_0' \equiv 1 \pmod{my_z^N}$. Suppose for all $p \mid \gcd(m, y_z)$, $v_p(m) < v_p(y_z^M) < v_p(y_z^{M+N})$ (i.e. pick a sufficiently large $M$). We have $x_z^{pN} \equiv 1 \pmod{y_z^{M+N}}$, and since $y_z^{M+N} \mid y_z^{pN}$, $1 \equiv a_0x_z^{pN} + a_4y_z^{pN} \equiv a_0 \pmod{y_z^{M+N}}$. Now let $\lambda$ be the part of $m$ coprime to $y_z$. We have $(a_0 + j \cdot y_z^{pN}) x_z^{pN} + (a_4 - j \cdot x_z^{pN}) y_z^{pN} = 1$. $a_0 + j \cdot y_z^{pN}$ forms a complete reduced residue class mod $\lambda$, and so there exists $a_0 + j \cdot y_z^{pN} \equiv 1 \pmod{\lambda}$. But we also have $a_0 + j \cdot y_z^{pN} \equiv a_0 \equiv 1 \pmod{y_z^{M+N}}$. Thus, by CRT $a_0' \equiv 1 \pmod{\lambda y_z^M \cdot y_z^N}$. $m \mid \lambda y_z^M$, so $a_0' \equiv 1 \pmod{my_z^{N}}$. Now we consider \begin{align*} T(x, y) = a_0x^{pN} + a_1x^{pN-N}y^{N} + a_2x^{pN-2N}y^{2N} + a_3x^{pN-3N}y^{3N} + a_4y^{pN}. \end{align*}If we set $a_0, a_4$ as discovered above, as well as $a_1 = a_2 = a_3 = 0$, we find that $T(x_z, y_z) = 1$. We construct $(\{(x_z, y_z)\}, m)$-good polynomials $T'(x, y) = a_0'x^{pN} + a_1'x^{pN-N}y^{N} + a_2'x^{pN-2N}y^{2N} + a_3'x^{pN-3N}y^{3N} + a_4'y^{pN}$ from $T(x, y)$. Indeed, if we consider: \begin{align*} a_0' &= a_0 + Ay_z^{N} \\ a_1' &= a_1 - Ax_z^{N} + By_z^{N} \\ a_2' &= a_2 - Bx_z^{N} \\ a_3' &= a_3 + Cy_z^{(p-3)N} \\ a_4' &= a_4 - Cx_z^{(p-3)N}. \end{align*}We find that $T'(x_z, y_z) = 1$ still. Let $a_0 = 1 + umy_z^N$, $A = -um$. We find that $a_0' = 1 + umy_z^N - umy_z^N = 1$. It suffices to find $B, C$ such that $T'(x, y)$ is $m$-good. Consider $p_i^{a_i} \in P$. Case 1: $(x_z^N, y_z^N) \equiv (1, 1) \pmod{p_i^{a_i}}$. Choose $C \equiv a_4 - 1 \pmod{p_i^{a_i}}$. Then $a_4' \equiv a_4 - C \equiv 1 \pmod{p_i^{a_i}}$, and $a_0' + ... + a_4' \equiv a_0 + ... + a_4 \equiv T(x_z, y_z) \equiv 1 \pmod{p_i^{a_i}}$. Case 2: $(x_z^N, y_z^N) \equiv (1, 0) \pmod{p_i^{a_i}}$. Choose $B \equiv 1 \pmod{p_i^{a_i}}, C \equiv a_4 - 1 \pmod{p_i^{a_i}}$. Then $a_4' \equiv a_4 - C \equiv 1 \pmod{p_i^{a_i}}$, and $a_0' + ... + a_4' \equiv a_0 + ... + a_4 - (A + B + C) \equiv a_0 + a_1 + a_2 + a_3 + a_4 - B - C \equiv 1 + 0 + 0 + 0 + a_4 - B - C \equiv 2 - B \equiv 1 \pmod{p_i^{a_i}}$. Case 3: $(x_z^N, y_z^N) \equiv (0, 1) \pmod{p_i^{a_i}}$. Choose $B \equiv 0 \pmod{p_i^{a_i}}, C \equiv -a_4 \pmod{p_i^{a_i}}$. Then $a_4' \equiv a_4 \equiv T(x_z, y_z) \equiv 1 \pmod{p_i^{a_i}}$, and $a_0' + ... + a_4' \equiv a_0 + ... + a_4 + (A + B + C) \equiv 1 + a_4 + B + C \equiv 1 \pmod{p_i^{a_i}}$. Now we've proven that $a_4' \equiv a_0' + ... + a_4' \equiv 1 \pmod{m}$ by CRT. $a_0' = 1$ so indeed $T'(x, y)$ is $m$-good and hence $(\{(x_z, y_z)\}, m)$-good. Furthermore, the only restriction on $B, C$ are modular, which means the coefficients can get arbitrarily large. $\square$ We induct on $V = |S|$ to prove that for any set $S$ of $V$ primitive pairs, and a fixed positive integer $m$, there exists $(S, m)$-good polynomials with arbitrarily large coefficients. Base case: See Claim 3. Inductive step: Assume this holds for $V-1$. Let $S' = S \setminus \{(x_V, y_N)\}$. Pick a $(S', mx_Vy_V)$-good polynomial $P_1(x, y)$. Note that $P_1(x_V, y_V) \neq 0$ since the leading coefficients are $1 \pmod{x_Vy_V}$. Pick a $(S', m \cdot P_1(x_V, y_V))$-good polynomial $P_2(x, y)$. WLOG they are of equal degree, otherwise apply Claim 2 to each with the degree of the other. Let $Q(x, y) = m(P_1(x, y) - P_2(x, y))$ with degree $k$. It's clear that this polynomial is still homogeneous, and all coefficients are $0 \pmod{m}$. Furthermore, $[x^k]P_1(x, y) = [x^k]P_2(x, y) = 1$, so actually $[x^k]Q(x, y) = 0$. For all $(x_i, y_i) \in S'$, $Q(x_i, y_i) = m(1 - 1) = 0$, and since $P_2(x_V, y_V)$ is coprime to $P_1(x_V, y_V)$ by Claim 1, $Q(x_V, y_V) = c \neq 0$. Finally, pick a $(S', cm)$-good polynomial $P_3(x, y)$, and WLOG it shares the same degree as $Q(x, y)$. Then for all $(x_i, y_i) \in S'$, $P_3(x_i, y_i) = 1$, and $P_3(x_V, y_V)$ is coprime to $Q(x_V, y_V)$. Now consider $(P_3(x, y), Q(x, y))$. For our pairs in $S$, this yields in order: $(0, 1)$ for $i = 1, 2, ..., V-1$ and $(P_3(x_V, y_V), c) = (X, Y)$ for $i = V$. These are all primitive pairs, although only 2 distinct ones. Finally, take any $(\{(X, Y)\}, m)$-good polynomial $R(x, y)$. We claim that $R(P_3(x, y), Q(x, y))$ suffices. Indeed it is still homogeneous, and all powers are multiples of $N$ since $P_1, P_2, P_3$ are all $(S', m)$-good. Furthermore, the coefficients of $R(P_3(x, y), Q(x, y))$ are bounded as a function of the coefficients of $P_3$ and $Q$; since we can choose arbitrarily large coefficients for these, we get arbitrarily large coefficients for our new polynomial. Let $\deg(R) = f$ and $\deg(P_3) = \deg(Q) = gN$. Then $[x^{fgN}]R(x, y) = ([x^{gN}]P_3(x, y))^f + ([x^{gN}]Q(x, y))^f = 1^f + 0^f = 1$. $[y^{fgN}]R(x, y) = ([y^{gN}]P_3(x, y))^f + ([y^{gN}Q(x, y))^f \equiv 1^f + 0^f \equiv 1 \pmod{m}$. The sum of the coefficients of $R(P_3, Q)$ is equal to $R(P_3(1, 1), Q(1, 1)) \equiv R(1, 0) \equiv 1 \pmod{m}$ by Claim 1. For $i = 1, 2, .., V-1$, $R(P_3(x_i, y_i), Q(x_i, y_i)) = R(1, 0) = 1$, and $R(P_3(x_V, y_V), Q(x_V, y_V)) = R(X, Y) = 1$. Hence, $R(P_3(x, y), Q(x, y))$ satisfies all the criteria for $(S, m)$-goodness.

We prove a generalization: Komal A703 wrote: Let $n\ge2$ be an integer. We call an ordered n-tuple of integers primitive if the greatest common divisor of its components is $1$. Prove that for every finite set $H$ of primitive $n$-tuples, there exists a non-constant homogenous polynomial $f(x_1,x_2,\cdots,x_n)$ with integer coefficients whose value is $1$ at every $n$-tuple in $H$. We induct on $|H|$. The base case, $|H|=1$, is a consequence of Bezout's theorem. Inductive Step: Suppose I have $f(x_1,\cdots,x_n)=1$ for all $(x_1,\cdots,x_n) \in H$, and I want to create a new polynomial $g$ such that $g$ is homogenous, $g(y_1,\cdots,y_n) = 1$ for a fixed $n$-tuple $(y_1,\cdots,y_n)$, and $g(x_1,\cdots,x_n)=1$ for all $(x_1,\cdots,x_n) \in H$. The key idea is to construct $h$ with linear factors such that $h(x_1,\cdots,x_n)=0$ for all $(x_1,\cdots,x_n)\in H$ and $\gcd(h(y_1,\cdots,y_n), f(y_1,\cdots,y_n))=1$. If we have this, there exists constants $A,B$ such that$$f(y_1,\cdots,y_n)^A = Bh(y_1,\cdots,y_n) + 1$$Thus, the polynomial $g = f^A - Bh$ is equal to 1 at all $(x_1,\cdots,x_n)\in H$, as well as $(y_1,\cdots,y_n)$. The only issue is that it is not homogenous. To fix this, by Bezout, there exists $q_1,q_2,\cdots,q_n$ such that $q_1y_1 + \cdots +q_ny_n=1$, so$$g(z_1,\cdots,z_n)=f(z_1,\cdots,z_n)^A - B(\sum_{j=1}^n q_jz_j)^{A \deg f - \deg h} h(z_1,\cdots,z_n)$$Works. Now, the goal is to for every $(x_1,\cdots,x_n)\in H$, I want to construct an $n$-tuple, $(a_1,\cdots,a_n)$ such that$$ \sum_{j=1}^n a_jx_j = 0$$and$$\gcd( \sum_{j=1}^n a_jy_j, P(y_1,\cdots,y_n))=1 $$For now, work in the vector space of $(\mathbb{F}_p)^n$, where $p\mid P(y_1,\cdots,y_n)$. If the two vectors $(x_1,\cdots,x_n)$ and $(y_1,\cdots,y_n)$ are linearly dependent, then there exists a constant $c$ such that $cy_j \equiv x_j (\bmod\; p)$ for all $j$, and $p\nmid c$. This implies that $$P(x_1,\cdots,x_n) \equiv P(cy_1,\cdots,cy_n) = c^{\deg P} P(y_1,\cdots,y_n) \equiv 0 (\bmod\; p)$$Which contradicts our inductive hypothesis that $P(x_1,\cdots,x_n)=1$. Thus, the two vectors are linearly independent, and such $(a_j)_{j=1}^n$ always exist in $\mathbb{F}_p$. Now call them $(a_{p,j})_{j=1}^n$ Let $p_1,\cdots,p_m$ be the divisors of $P(y_1,\cdots,y_n)$. Observe any $(a_1,\cdots,a_n)$ satisfying $a_j \equiv a_{p_k,j} (\bmod\; p_k)$ for all $k\in \{1,\cdots,m\}, j\in \{1,\cdots,n\}$ satisfies $$\prod\limits_{j=1}^m p_j \mid \sum_{w=1}^n a_wx_w$$$$\gcd\left(\prod\limits_{j=1}^m p_j, \sum_{w=1}^n a_wy_w\right) = 1$$Let $\sum_{w=1}^n a_wx_w = \prod\limits_{j=1}^m p_j \cdot N$. Let $b_1,\cdots,b_n$ such that $\sum b_wx_w=1$. Then note $$\sum_{w=1}^n \left(a_w - \left(\prod\limits_{j=1}^m p_j\right) \cdot N b_wx_w\right) = 0$$And the second condition is still satisfied. Now, for each $(x_1,\cdots,x_n)\in H$, we have successfully constructed $c_1,\cdots,c_n$ such that $\sum c_jx_j = 0$ and $\gcd\left( \sum c_jy_j, P(y_1,\cdots,y_n)\right)=1$. For convenience, let $c_x=(c_{x,j})$ satisfy these conditions for $x=(x_1,\cdots,x_n)$. This implies that constructing $h(z_1,\cdots,z_n) = \prod\limits_{x=(x_1,\cdots,x_n)\in H} \left( \sum c_jx_j \right)$ gives our desired $h$.

Excellent problem. We first prove the following claim. Claim: Let $P$ be a homogeneous degree-$n$ $2$-variable polynomial and let $(a,b)$ be a primitive point such that $P(a,b)=1$. Then for any primitive point $(c,d)$, we have $\gcd(P(c,d),bc-ad)=1$. Proof: Fix a primitive point $(c,d)$ and suppose some prime $p$ divides both $bc-ad$ and $P(c,d)$. If $p \mid a \implies p \nmid b$, then we need $p \mid c \implies p \nmid d$. Since $p \mid P(c,d)$, it clearly follows that the $y^n$ coefficient must be divisible by $p$. But then $p \mid P(a,b)$: absurd. The case where $p \mid b$ is similar. Hence suppose $p \nmid ab$, which implies $p \nmid cd$. Thus we may write $d \equiv bc/a \pmod{p}$, so then $P(c,d) \equiv P(c,bc/a) \pmod{p}$. But since everything is coprime to $p$ and $P$ is homogeneous, $p \mid P(c,bc/a) \implies p \mid P(ac,bc) \implies p \mid P(a,b)$: contradiction. $\blacksquare$ We are now ready to solve the main problem by induction on $|S|$, with the base case of $|S|=1$ being Bezout's lemma. For the inductive step, suppose $P_0$ is a homogeneous polynomial which is $1$ over the set $S':=\{(a_1,b_1),\ldots,(a_k,b_k)\}$, and we wish to add some primitive point $(a,b)$ to $S'$ to form $S$. Let $$C=\prod_{i=1}^k (b_ia-a_ib).$$By the claim, we have $\gcd(P_0(a,b),C)=1$, hence there exists some positive integer $N$ such that $P_0(a,b)^N \equiv 1 \pmod{C}$. Let $\deg (P_0(a,b)^N)=d+k$ (clearly $d \geq 0$) for convenience. By Bezout's lemma again, as $i$ and $j$ span $\mathbb{Z}$, the expression $iCx^d+jCy^d$ spans all multiples of $C$, hence there exists some choice of $(i,j)$ that makes it equal to $P_0(c,d)^N-1$. Then we may take $$P(x,y)=P_0(x,y)^N-\left(ix^d+jy^d\right)\prod_{i=1}^m (b_ix-a_iy)$$This works, since $P$ is homogeneous (of degree $d+k$), $P(a_i,b_i)=1^N-0=1$ for all $i$, $P(a,b)=(P_0(a,b)^N)-(P_0(a,b)^N-1)=1$. Hence our induction is complete, so we are done. $\blacksquare$ Remarks: It seems rather difficult to get a grip on this problem. Although you can chip away and explore a few possible techniques, constructing a polynomial for $S=\{(3,2),(4,1)\}$ is already a headache ($n=2$ doesn't work). However, when trying $|S|=2$ there is the fairly intuitive idea that we can apply Bezout to the coefficients, which works if (in the language of the above proof) we have $P_0(a,b) \equiv 1 \pmod{b_1a-a_1b}$ by default. However this is not always true (i.e. when $S=\{(3,2),(4,1)\}$), and in fact this can clearly generalize if we could guarantee $P_0(a,b) \equiv 1 \pmod{C}$. At this point I am thoroughly stuck, but at some point the key idea that $1^N=1$ for any positive integer $N$ enters my head, which is the main "leap" of the problem. It is then clear that we just have to prove $\gcd(P_0(a,b),C)=1$. This turns out to not be too difficult, and we're done! I still haven't found the polynomial for $\{(3,2),(4,1)\}$ btw

We'll proceed induction on $|S|$. Base case $|S| = 1$ is Bezout lemma. Now assume it's true on $|S| = n-1$ and we'll prove that $|S| = n$. Let the $n$ points be $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$. Let $f(x,y) \in \mathbb{Z}[x, y]$ such that $f(x_i, y_i) = 1$ for all $1 \le i \le n-1$. Now consider the following claim: Claim: $\gcd(f(x_n, y_n), x_ny_i - y_nx_i) = 1$ for all $1 \le i \le n-1$. Proof. Fix $i$. Assume the contrary, there exists prime $p$ such that $p \mid \gcd(f(x_n, y_n), x_ny_i - y_nx_i)$. If $p \mid x_n$, then since $\gcd(x_n, y_n) = 1$, so $p \mid x_i$. Note that $p \mid f(x_n, y_n)$ and $p \mid x_n$, thus $p \mid f(0, y_n)$ and $p \nmid y_n$, therefore $p \mid f(x_i, y_i)$, a contradiction. Now assume $\gcd(p, x_ny_nx_iy_i) = 1$. Then $\frac{x_n}{y_n} \equiv \frac{x_i}{y_i} (p)$, so $0 \equiv f(x_n, y_n) = y_n^{\deg(f)} \cdot f(\frac{x_n}{y_n}, 1) \equiv y_n^{\deg(f)} f(\frac{x_i}{y_i}, 1) (p)$. Hence $p \mid f(x_i, y_i)$, a contradiction. $\blacksquare$ Let $a, b$ be integers such that $ax_n + by_n = 1$ .We'll choose suitable $k, M$ such that the polynomial $g(x, y) = f(x, y)^k - M \cdot(ax + by)^{\deg(f) \cdot k - (n-1)} \cdot \prod_{i=1}^{n-1} (xy_i - yx_i)$ satisfies the problem condition. Note that $g(x_i, y_i) = 1$ for all $1 \le i \le n-1$, so we only need to choose $k, M$ such that $g(x_n, y_n) = 1$. By claim, we have $\gcd(f(x_n, y_n), \prod_{i=1}^{n-1} (x_ny_i - y_nx_i)) = 1$, so letting $k = \varphi(\prod_{i=1}^{n-1} (x_ny_i - y_nx_i))$ and $M = \frac{f(x_n, y_n)^k - 1}{\prod_{i=1}^{n-1} (x_ny_i - y_nx_i)}$ would work. This completes proof. $\blacksquare$

Solved with megarnie, OronSH, and pi271828 Assume $n$ is even, so if $(a,b)$ works so does $(-a,-b)$. In each negative pair remove one of them, so assume there are no negative pairs. Now, the idea is that due to the primitive condition, each point has a different ratio of $x$ to $y$ coordinates, so each point has a unique irreducible homogenous linear polynomial that kills it. Label the points $(x_1,y_1)\dots (x_k,y_k)$. Define $$P_i(x,y)=\prod_{j\neq i}(y_jx-x_jy),$$which zeroes all points except for $(x_i,y_i)$. Define the modular bottleneck $M_i$ of a point $(x_i,y_i)$ as $$P_i(x_i,y_i).$$In particular, by adding $P_i(x,y)Q(x,y)$ where $Q(x_i,y_i)=1$, we can adjust the value of the function at point $i$ by multiples of $M_i$ without affecting any other points. In particular, we only need to get to a point where each point $i$ is $1\pmod{M_i}$ hence the name. Define the universal modular bottleneck $u$ as $\prod_{i} M_i$. Now, we try to show the existence of a universal polynomial $U(x,y)$, such that $U(x,y)\equiv 1\pmod{u}$ for all $(x,y)\in S$ and $U$ is homogenous. Consider mod each prime power separately. For mod $p^n$, consider $$(x^{p^{n-1}(p-1)}+y^{p^{n-1}(p-1)})^{p^{n-1}(p-1)}.$$At most one of $x$ and $y$ are divisible by $p$. If one of them is, then this is $1^{p^{n-1}(p-1)}\equiv 1$, if neither are, this is $2^{p^{n-1}(p-1)}\equiv 1$ as well. This works for $p>2$. For mod $2^n$, consider $(x^2+xy+y^2)^{2^{n-1}}.$ Since $x$ and $y$ are not both even, the inside is odd, so this becomes $1\pmod{2^n}$. Now, construct a separate polynomial mod each prime power, raise each one to a suitable power to make all of them the same degree, and use CRT to collapse the results into a single universal polynomial $U$. Now, any power of $U$ also works, so assume $U$ has sufficiently large and even degree. Now, start by adding $U$. Then, each point is now correct mod its modular bottleneck. Then, for each point $(x_i,y_i)$, choose $Q$ suitably such that $Q(x_i,y_i)=1$ and $P_i(x,y)Q(x,y)$ has the same degree as $U$ (possible since $x_i^k$ and $y_i^k$ are relatively prime) and add a constant multiple of $P_i(x,y)Q(x,y)$ to the mix to fix the value at point $i$ to $1$. Doing this for each $i$, we are done. The degree is the same as $U$, which is also even, done.

Think my solution, if correct, is new. Let me know if I am mistaken. Call a polynomial with required property a good polynomial for $S$. Proposition. Let $k\geq 2, S=\{(1, a_1), \ldots, (1, a_{k-1}), (b, 1)\}$, where $a_1, \ldots, a_{k-1}$, and $b$ are integers. Then good polynomial exists for $S$.

Induct on $|S|=k$ with $k=1$ being trivial. Assume $S=\{(x_1, y_1), \ldots, (x_k, y_k)\}, k\geq 2$. By induction hypothesis there exists good polynomial $Q$ for $\{(x_1, y_1), \ldots, (x_{k-1}, y_{k-1})\}$. Let $R$ be an integral homogeneous polynomial of same degree as $Q$ such that $R(x_k, y_k)=1$ (existence of $R$ follows from Bezout). Let $S'=\{(Q(x_1, y_1), R(x_1, y_1)), \ldots, (Q(x_k, y_k), R(x_k, y_k))\}$. Then $S'$ is a set of the form in the Proposition; let $T$ be a good polynomial for $S'$, and finally let $P(x, y)=T(Q(x,y), R(x,y))$. Since $Q, R, T$ are homogenous of integer coefficients with $\deg Q=\deg R$, so is $P$. For any $(x, y)\in S$ we have \begin{align*} P(x, y) &= T(Q(x, y), R(x, y))\\ &=1 && ((Q(x,y), R(x,y))\in S'). \end{align*}To show that $P$ is the desired good polynomial, it remains to show that it has positive degree. Suppose not, then the constant polynomial $P$ must be identically $1$. But $P(0, 0) = T(Q(0,0), R(0,0)) = T(0,0)=0$, a contradiction.

We will show that, if $S$ has size $n,$ then there is such a polynomial. We will show this via induction. The base case, $n = 1,$ is just Bezout's Theorem. \newline \newline For the inductive step, assume that, any set $S$ of primitive points such that $|S| = n$ has such a polynomial. We will show this for $n+1.$ Let $$S = \{(b_{i},c_{i}) \colon 1 \le i \le n+1\}.$$Now, let $$S^{\prime} = \{(b_{i},c_{i}) \colon 1 \le i \le n\} \subset S,$$and let $f(b_{i}, c_{i}) = 1$ for $1 \le i \le n.$ We will show that we can find a polynomial $f^{\prime}$ that has $f^{\prime}(b_{i}, c_{i}) = 1$ for $1 \le i \le n+1.$ Claim: There exists a polynomial $h$ such that $$g(x,y) = f(x,y)^{k}+h(x,y) \cdot \prod_{j=1}^{n}(c_{j}x-b_{j}y),$$so that $g(b_{i}, c_{i}) = 1$ for $1 \le i \le n+1.$

Since we can find a possibility for $h,$ we can also find a possibility for $g.$ So, we have completed the induction.

headsolved over the course of a few hours Claim: For any nonzero integer $k$, the homogeneous polynomial \[ f(x, y) \coloneq x^{2k\varphi(n)} - x^{k\varphi(n)}y^{k\varphi(n)} + y^{2k\varphi(n)} \]is divisible by $n$ if and only if both $x, y$ are divisible by $n$, else it is $1 \pmod{n}$. Proof. Note that by FLT, $x^{\varphi(n)}$ and $y^{\varphi(n)}$ are in $\{0, 1\}$, then this is a routine check. $\blacksquare$ Let $p_i = (x_i, y_i)$ be the points in $S$, and suppose $|S| = k$. If we define the degree $k-1$ polynomial \[ f_i \coloneq \prod_{j \ne i} (x_j \cdot y - y_j \cdot x) \]then this polynomial is equal to some integer $n_j$ at $p_j$ and is zero at every other point. We can thus define $N = \varphi(n_1)\varphi(n_2) \cdots \varphi(n_k)$ such that \[ f \coloneq x^{2kN} - x^{kN}y^{kN} + y^{2kN} \]is $1 \pmod{n_i}$ for each $i$. We now define $a_i$ as a degree $1$ homogenous polynomial which is $1$ at $p_i$. Then it thus follows that we can choose $\ell_1, \ell_2, \dots, \ell_n$ such that \[ f - \ell_1 a_1^{2kN-(k-1)} f_1 - \ell_2 a_2^{2kN-(k-1)} f_2 \dots - \ell_n a_n^{2kN-(k-1)} f_n \]is $1$ at each point, and this polynomial is homogeneous and has integer coefficients as desired.