For a prime number $p$. Can the number of n positive integers that make the expression \[\dfrac{n^3+np+1}{n+p+1}\]an integerĀ beĀ $777$?
Problem
Source: Turkey JBMO TST 2023 Day 2 P4
Tags: number theory, Divisibility
30.04.2023 19:11
The answer is no! Assume the contrary, and observe that $p>2$. We first notice $n\equiv -p-1\pmod{n+p+1}$. So, \[ 0\equiv n^3+np+1\equiv -(p+1)^3 - p(p+1)+1\pmod{n+p+1}, \]which implies \[ n+p+1\mid n^3+np+1\Leftrightarrow n+p+1\mid p(p+2)^2. \]As $n\ge 1$, the number of all such $n$ is clearly the number of all divisors of $p(p+2)^2$ that is at least $p+2$. Let $S=\{d:d\mid p(p+2)^2 , d\ge p+2\}$. We show $|S|=777$ is impossible. To that end, let $N$ be the number of divisors of $(p+2)^2$. Note that there exists exactly $N-1$ elements $d\in S$ for which $p\mid d$ (indeed, any $d$ of form $p\cdot i$, where $i\mid (p+2)^2$ and $i>1$ satisfies the condition). We now count the number of such $d\in S$ for which $p\nmid d$. Consider the pairs $(x,(p+2)^2/x)$, where $x\mid (p+2)^2$ and $x\ne p+2$. Note that there are $(N-1)/2$ such pairs. Moreover, for each such pair, exactly one of $x$, $(p+2)^2/x$ is at least $p+2$. So, the number of $d\mid S$ with $p\mid d$ is $(N-1)/2 +1$ (the extra is from $p+2$). Hence, \[ |S| = N-1 + \frac{N-1}{2}+1 = \frac{3N-1}{2} = 777\Leftrightarrow 3N-1 = 2\cdot 777, \]which is impossible via modulo 3.