Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
 Already signed up? New to KöMaL?

# Problem A. 703. (September 2017)

A. 703. Let $\displaystyle n\ge 2$ be an integer. We call an ordered $\displaystyle n$-tuple of integers primitive if the greatest common divisor of its components is $\displaystyle 1$. Prove that for every finite set $\displaystyle H$ of primitive $\displaystyle n$-tuples, there exists a non-constant homogenous polynomial $\displaystyle f(x_1,x_2,\dots,x_n)$ with integer coefficients whose value is $\displaystyle 1$ at every $\displaystyle n$-tuple in $\displaystyle H$.

(Based on the sixth problem of the 58th IMO, Brazil)

(5 pont)

Deadline expired on October 10, 2017.

Solution. Fix a large degree $\displaystyle d$. Let $\displaystyle f$ be some homogenous polynomial with integer coefficients with degree $\displaystyle d$. To each such $\displaystyle f$, we can assign an $\displaystyle |H|$-tuple containing the values of $\displaystyle f$ at the elements of $\displaystyle H$. We wish to construct an $\displaystyle f$ where this $\displaystyle |H|$-tuple is precisely $\displaystyle (1,1,\dots,1)$. To this end, we will create two auxiliary polynomials (of degree $\displaystyle d$). First, for each $\displaystyle v\in H$, we build $\displaystyle Q_v(x_1,\dots,x_n)$, which attains some integer $\displaystyle M_v>0$ at $\displaystyle v$, but vanishes over $\displaystyle H\setminus\{v\}$. Second, we create $\displaystyle T(x_1,\dots,x_n)$ with value $\displaystyle 1$ modulo each $\displaystyle M_v$ at each element of $\displaystyle H$. Then an integer combination of $\displaystyle T$ and the $\displaystyle Q_v$ will create a polynomial which attains exactly $\displaystyle 1$ over all elements of $\displaystyle H$.

Construction of $\displaystyle Q_v$.

Let $\displaystyle v\in H$ be arbitrary. First consider

$\displaystyle P_v(x_1,\dots,x_n):=\prod_{(a_1,a_2,\dots,a_n)\in H\setminus \{v\}} \left( \sum_{i=1}^n (x_i-a_i)^2 \right).$

Since $\displaystyle \sum_{i=1}^n (x_i-a_i)^2=0$ iff $\displaystyle (x_1,\dots,x_n)=(a_1,\dots,a_n)$, we have $\displaystyle P_v(v)=M_v>0$, but that $\displaystyle P_v$ vanishes over $\displaystyle H\setminus\{v\}$.

Moreover, since the coordinates of $\displaystyle v=(v_1,v_2,\dots,v_n)$ have greatest common divisor $\displaystyle 1$, Bézout's identity implies that $\displaystyle \alpha_1v_1+\dots+\alpha_nx_n=1$ for some $\displaystyle \alpha_i\in\mathbb{Z}$. Now let

$\displaystyle L_v(x_1,\dots,x_n)=\alpha_1x_1+\dots+\alpha_n x_n.$

Then for any degree $\displaystyle d$ larger than $\displaystyle \deg P_v$, we can take

$\displaystyle Q_v=P_v\cdot L_v^{d-\deg P_v}$

to be homogenous, have integer coefficients, and take on value $\displaystyle M_v$ at $\displaystyle v$ and $\displaystyle 0$ over $\displaystyle H\setminus\{v\}$.

Construction of $\displaystyle T(x_1,\dots,x_n)$.

Set $\displaystyle M=2\prod_{v\in H}M_v$. Let the prime factorization of $\displaystyle M$ be $\displaystyle M=p_1^{k_1}p_2^{k_2}\dots p_s^{k_s}$. Suppose further that $\displaystyle d$ is a multiple of $\displaystyle d_0=n!\cdot \prod_{i=1}^s k_i\varphi\left(p_i^{k_i}\right)$ (we will soon understand the use of this).

Fix some $\displaystyle i\in\{1,2,\dots,s\}$, and let $\displaystyle q=p_i^{k_i}=p^k$. We first construct a polynomial which has value $\displaystyle 1$ mod $\displaystyle q$ whenever $\displaystyle x_1,x_2,\dots,x_n$ are integers, not all of them divisible by $\displaystyle p$. Doing this is essentially an application of PIE. In particular, for each $\displaystyle j=1,2,\dots,n$, define

$\displaystyle T_j(x_1,\dots,x_n)=\sum_{1\le i_1< i_2< \dots< i_j\le n} x_{i_1}^{d/j}x_{i_2}^{d/j}\dots x_{i_j}^{d/j}.$

Then if $\displaystyle d$ is a multiple of $\displaystyle n!\cdot k\varphi(q)$, Euler-Fermat implies

$\displaystyle x^{d/j}\equiv \begin{cases} 1\pmod{q}\quad\text{ha }p\not|x \\ 0\pmod{q}\quad \text{ha }p|x \end{cases},$

so if exactly $\displaystyle \nu$ of $\displaystyle x_1,x_2,\dots,x_n$ are not divisible by $\displaystyle p$, then

$\displaystyle T_j(x_1,x_2,\dots,x_n)\equiv \binom{\nu}{j}\pmod{q}.$

(Here we denote $\displaystyle \binom\nu j=0$ if $\displaystyle j>\nu$.) For $\displaystyle \nu=1,2,\dots,n$, the Binomial Theorem implies

$\displaystyle (1-1)^\nu=1-\binom \nu1+\binom \nu2\mp\dots\pm \binom \nu n,$

so all this proves that polynomial

$\displaystyle T[q]=T_1-T_2\pm\dots\pm T_n$

has value $\displaystyle 1$ mod $\displaystyle q$, whenever at least one of $\displaystyle x_1,x_2,\dots,x_n$ is not divisible by $\displaystyle p$.

Having constructed polynomial $\displaystyle T[q]$ (with degree $\displaystyle d$) for each prime power $\displaystyle q$ in $\displaystyle M$, we simply choose polynomial $\displaystyle T$ by making each of its coefficients in its expanded form congruent to the corresponding coefficient of $\displaystyle T[p_i^{k_i}]$ modulo $\displaystyle p_i^{k_i}$ for each $\displaystyle i=1,2,\dots,s$; this amounts to applying the Chinese Remainder Theorem (CRT) $\displaystyle \binom{d+n-1}{n-1}$ times.

Then another application of CRT shows that $\displaystyle T(x_1,x_2,\dots,x_n)\equiv 1\pmod{M}$ if $\displaystyle (x_1,\dots,x_n)\in H$. Indeed, $\displaystyle T\equiv 1\pmod{p_i^{k_i}}$ for each $\displaystyle i$, because $\displaystyle p_i$ cannot divide all of $\displaystyle x_1,\dots,x_n$.

Finishing up.

Choose $\displaystyle d$ to be a multiple of $\displaystyle d_0$ larger than the degree of all the $\displaystyle P_v$'s. With this $\displaystyle d$, we'll have $\displaystyle T(v)=1+M_v\ell_v$ with some $\displaystyle \ell_v\in\mathbb{Z}$ for all $\displaystyle v\in H$. In this case,

$\displaystyle f(x_1,\dots,x_n)=T(x_1,\dots,x_n)-\sum_{v\in H}\ell_v Q_v(x_1,\dots,x_n)$

satisfies the required conditions.

### Statistics:

 9 students sent a solution. 5 points: Beke Csongor, Bukva Balázs, Gáspár Attila, Imolay András, Janzer Orsolya Lili, Matolcsi Dávid, Schrettner Jakab, Simon Dániel Gábor, Szabó Kristóf.

Problems in Mathematics of KöMaL, September 2017