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 \neq 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 \neq i$. Define $a_{i}=g_{i}(x_{i}, y_{i})$, and note that $a_{i} \neq 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 \neq i$.
2. $g_{i}(x_{i}, y_{i})=a_{i}$.

For any $N \geqslant 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\pmod{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 \leqslant i \leqslant 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})^{\phi(a)}$ if $p$ is odd;
- $f_{a}(x, y)=(x^{2}+x y+y^{2})^{\phi(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}}\pmod{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 \pmod{a}$ for any relatively prime $(x, y)$; and this polynomial is homogenous because all the $F_{q_{i}}$ have the same degree.

As in the previous solution, label the irreducible lattice points $(x_{1}, y_{1}), \ldots,(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 \leqslant i \leqslant 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)=c x+d y$ is suitable.

If $n \geqslant 2$ : By the induction hypothesis we already have a homogeneous polynomial $g(x, y)$ with $g(x_{1}, y_{1})=\ldots=g(x_{n-1}, y_{n-1})=1$. Let $j=\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} \neq 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(c x+d y)^{L}$$
where $K$ and $L$ are some positive integers and $C$ is some integer. We assume that $L=K j-n+1$ so that $f$ is homogenous.

Due to $g(x_{1}, y_{1})=\ldots=g(x_{n-1}, y_{n-1})=1$ and $g_{n}(x_{1}, y_{1})=\ldots=g_{n}(x_{n-1}, y_{n-1})=0$, the property $f(x_{1}, y_{1})=\ldots=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\pmod{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 \leqslant k<n$ such that $x_{k} y_{n} \equiv x_{n} y_{k}\pmod{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\pmod{p}$. In the other case, we have $x_{k} y_{n} \equiv x_{n} y_{k} \equiv 0\pmod{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}\pmod{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} \pmod{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 \pmod{p}$$
If $p^{\alpha} \mid m$, then we have
$$g(x_{n}, y_{n})^{p^{\alpha-1}(p-1)} \equiv 1 \pmod{p^{\alpha}}$$
which implies that the exponent $K=n \cdot \varphi(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 \geqslant n$ and so $L>0$.)