International Mathematical Olympiad

First of all, we note that finding a homogenous polynomial $f(x,y)$ such that $f(x,y)=\pm 1$ is enough, because we then have $f^2(x,y)=1$. Label the irreducible lattice points $(x_1,y_1)$ through $(x_n,y_n)$. If any two of these lattice points $(x_i,y_i)$ and $(x_j,y_j)$ lie on the same line through the origin, then $(x_j,y_j)=(-x_i,-y_i)$ because both of the points are irreducible. We then have $f(x_j,y_j)=\pm f(x_i,y_i)$ whenever $f$ is homogenous, so we can assume that no two of the lattice points are collinear with the origin by ignoring the extra lattice points.

Consider the homogenous polynomials ${\ell }_i(x,y)=y_{i}x-x_{i}y$ and define $$g_i(x,y)=\prod _{j\ne i}{\ell }_j(x,y).$$ Then ${\ell }_i(x_j,y_j)=0$ if and only if $j=i$, because there is only one lattice point on each line through the origin. Thus, $g_i(x_j,y_j)=0$ for all $j\ne i$. Define $a_i=g_i(x_i,y_i)$, and note that $a_i\ne 0$.

Note that $g_i(x,y)$ is a degree $n-1$ polynomial with the following two properties: 1. $g_i(x_j,y_j)=0$ if $j\ne i$. 2. $g_i(x_i,y_i)=a_i$.

For any $N⩾n-1$, there also exists a polynomial of degree $N$ with the same two properties. Specifically, let $I_i(x,y)$ be a degree 1 homogenous polynomial such that $I_i(x_i,y_i)=1$, which exists since $(x_i,y_i)$ is irreducible. Then $I_i(x,y{)}^{N-(n-1)}{g}_i(x,y)$ satisfies both of the above properties and has degree $N$.

We may now reduce the problem to the following claim: Claim: For each positive integer $a$, there is a homogenous polynomial $f_a(x,y)$, with integer coefficients, of degree at least 1, such that $f_a(x,y)\equiv 1(\mathrm{mod}a)$ for all relatively prime $(x,y)$.

To see that this claim solves the problem, take $a$ to be the least common multiple of the numbers $a_i$ ($1⩽i⩽n$). Take $f_a$ given by the claim, choose some power $f_a(x,y{)}^k$ that has degree at least $n-1$, and subtract appropriate multiples of the $g_i$ constructed above to obtain the desired polynomial.

We prove the claim by factoring $a$. First, if $a$ is a power of a prime ($a=p^k$), then we may choose either: - $f_a(x,y)=(x^{p-1}+y^{p-1}{)}^{\varphi (a)}$ if $p$ is odd; - $f_a(x,y)=(x^2+xy+y^2{)}^{\varphi (a)}$ if $p=2$.

Now suppose $a$ is any positive integer, and let $a=q_1{q}_2\cdots q_k$, where the $q_i$ are prime powers, pairwise relatively prime. Let $f_{q_i}$ be the polynomials just constructed, and let $F_{q_i}$ be powers of these that all have the same degree. Note that $$\frac{a}{q_i}{F}_{q_i}(x,y)\equiv \frac{a}{q_i}(\mathrm{mod}a)$$ for any relatively prime $x,y$. By Bézout's lemma, there is an integer linear combination of the $\frac{a}{q_i}$ that equals 1. Thus, there is a linear combination of the $F_{q_i}$ such that $F_{q_i}(x,y)\equiv 1(\mathrm{mod}a)$ for any relatively prime $(x,y)$; and this polynomial is homogenous because all the $F_{q_i}$ have the same degree.

---

Alternative solution.

As in the previous solution, label the irreducible lattice points $(x_1,y_1),\dots ,(x_n,y_n)$ and assume without loss of generality that no two of the points are collinear with the origin. We induct on $n$ to construct a homogenous polynomial $f(x,y)$ such that $f(x_i,y_i)=1$ for all $1⩽i⩽n$.

If $n=1$ : Since $x_1$ and $y_1$ are relatively prime, there exist some integers $c,d$ such that $c{x}_1+d{y}_1=1$. Then $f(x,y)=cx+dy$ is suitable.

If $n⩾2$ : By the induction hypothesis we already have a homogeneous polynomial $g(x,y)$ with $g(x_1,y_1)=\dots =g(x_{n-1},y_{n-1})=1$. Let $j=\mathrm{deg}g$, $$g_n(x,y)=\prod _{k=1}^{n-1}(y_{k}x-x_{k}y)$$ and $a_n=g_n(x_n,y_n)$. By assumption, $a_n\ne 0$. Take some integers $c,d$ such that $c{x}_n+d{y}_n=1$. We will construct $f(x,y)$ in the form $$f(x,y)=g(x,y{)}^K-C\cdot g_n(x,y)\cdot (cx+dy{)}^L$$ where $K$ and $L$ are some positive integers and $C$ is some integer. We assume that $L=Kj-n+1$ so that $f$ is homogenous.

Due to $g(x_1,y_1)=\dots =g(x_{n-1},y_{n-1})=1$ and $g_n(x_1,y_1)=\dots =g_n(x_{n-1},y_{n-1})=0$, the property $f(x_1,y_1)=\dots =f(x_{n-1},y_{n-1})=1$ is automatically satisfied with any choice of $K,L$, and $C$.

Furthermore, $$f(x_n,y_n)=g(x_n,y_n{)}^K-C\cdot g_n(x_n,y_n)\cdot (c{x}_n+d{y}_n{)}^L=g(x_n,y_n{)}^K-C{a}_n.$$ If we have an exponent $K$ such that $g(x_n,y_n{)}^K\equiv 1(\mathrm{mod}{a}_n)$, then we may choose $C$ such that $f(x_n,y_n)=1$. We now choose such a $K$.

Consider an arbitrary prime divisor $p$ of $a_n$. By $$p\mid a_n=g_n(x_n,y_n)=\prod _{k=1}^{n-1}(y_k{x}_n-x_k{y}_n)$$ there is some $1⩽k<n$ such that $x_k{y}_n\equiv x_n{y}_k(\mathrm{mod}p)$. We first show that $x_k{x}_n$ or $y_k{y}_n$ is relatively prime with $p$. This is trivial in the case $x_k{y}_n\equiv x_n{y}_k\not\equiv 0(\mathrm{mod}p)$. In the other case, we have $x_k{y}_n\equiv x_n{y}_k\equiv 0(\mathrm{mod}p)$. If, say $p\mid x_k$, then $p\nmid y_k$ because $(x_k,y_k)$ is irreducible, so $p\mid x_n$; then $p\nmid y_n$ because $(x_n,y_n)$ is irreducible. In summary, $p\mid x_k$ implies $p\nmid y_k{y}_n$. Similarly, $p\mid y_n$ implies $p\nmid x_k{x}_n$.

By the homogeneity of $g$ we have the congruences $$x_k^d\cdot g(x_n,y_n)=g(x_k{x}_n,x_k{y}_n)\equiv g(x_k{x}_n,y_k{x}_n)=x_n^d\cdot g(x_k,y_k)=x_n^d(\mathrm{mod}p)$$ and $$y_k^d\cdot g(x_n,y_n)=g(y_k{x}_n,y_k{y}_n)\equiv g(x_k{y}_n,y_k{y}_n)=y_n^d\cdot g(x_k,y_k)=y_n^d(\mathrm{mod}p).$$ If $p\nmid x_k{x}_n$, then take the $(p-1{)}^{st}$ power of the first congruence; otherwise take the $(p-1{)}^{st}$ power of the second; by Fermat's theorem, in both cases we get $$g(x_n,y_n{)}^{p-1}\equiv 1(\mathrm{mod}p)$$ If $p^{\alpha }\mid m$, then we have $$g(x_n,y_n{)}^{p^{\alpha -1}(p-1)}\equiv 1(\mathrm{mod}{p}^{\alpha })$$ which implies that the exponent $K=n\cdot \phi (a_n)$, which is a multiple of all $p^{\alpha -1}(p-1)$, is a suitable choice. (The factor $n$ is added only so that $K⩾n$ and so $L>0$.)