Let $d(n)$ be the number of divisors of a nonnegative integer $n$ (we set $d(0)=0$). Find all positive integers $d$ such that there exists a two-variable polynomial $P(x,y)$ of degree $d$ with integer coefficients such that: for any positive integer $y$, there are infinitely many positive integers $x$ such that $\gcd(x,y)=1$ and $d(|P(x,y)|) \mid x$, and for any positive integer $x$, there are infinitely many positive integers $y$ such that $\gcd(x,y)=1$ and $d(|P(x,y)|) \mid y$. Allen Wang
Problem
Source: ELMO Shortlist 2024/N8
Tags: Elmo, number theory
22.06.2024 18:56
22.06.2024 19:02
Here's the author's (i.e. my) original solution, using a different polynomial. The fact that $x^ay^b$ works was first found by Advaith Avadhanam The answer is that all $d$ work. In fact, choosing $P(x,y)=(x+y)^d$ will do the job. By symmetry it suffices to show that for any positive integer $y$, there are infinitely many choices of $x \perp y$ such that $d(|P(x,y)|) \mid x$. We commit to choosing $x$ of the form $p^k-y$, so $d(|P(x,y)|)=kd+1$. Unless $p \mid y$, which happens finitely often, this guarantees that $x \perp y$. Suppose that we can find some prime $q$ dividing $y^d-1$ such that $q \equiv 1 \pmod{d}$, so we can write $q=kd+1$ for some positive integer $k$. Then $y$ is a $k$-th power modulo $q$ for order reasons, and since $q \nmid y$ there exists some nonzero residue $a$ such that $a^k \equiv y \pmod{q}$. By Dirichlet we can then find infinitely many primes $p \equiv a \pmod{q}$, whence $kd+1=q \mid p^k-y$ as desired. In most cases, such a prime $q$ is supplied by Zsigmondy's theorem: any primitive prime divisor $q$ of $y^d-1$ (i.e. prime dividing $y^d-1$ which doesn't divide $y^k-1$ for any $0<k<d$) must have $\mathrm{ord}_q(y)=d$ by definition, hence $d \mid p-1$. We now deal with the following edge cases: If $y=1$, then such a prime $q$ obviously exists by Dirichlet's theorem. If $d=1$ and $y=2$, then such a prime $q$ obviously exists. If $d=2$ and $y+1 \neq 2$ is a power of $2$, then $y-1$ is not a power of $2$ and hence has some odd prime divisor, which then divides $y^2-1=(y-1)(y+1)$. Letting $q$ be this odd prime divisor works. If $d=6$ and $y=2$, then $q=7$ works. This finishes the problem. $\blacksquare$