Given is a positive integer $n$ divisible by $3$ and such that $2n-1$ is a prime. Does there exist a positive integer $x>n$ such that $$nx^{n+1}+(2n+1)x^n-3(n-1)x^{n-1}-x-3$$is a product of the first few odd primes?
Problem
Source: Serbia TST 2022 P5
Tags: number theory
20.04.2023 19:02
General idea: For size reasons 2n-1 must divide the polynomial. By multiplying by 2, simplifying and using the fact that x^(n-1) is 1 or -1 module 2n-1, we get that x must be either 1 or -3 modulo 2n-1. By plugging in the polynomial x=(2n-1)a + 1 or x = (2n-1)a + 3 we get that P(x) is divisible by (2n-1)^2. The end.
01.05.2023 23:00
The answer is no. Let me write out the details of the above sketch. Let $A$ denote the given expression. We firstly present the following initial Claim, which will be used later on. Claim 1: Let $n\#$ denote the primorial of $n$, i.e. the product of all primes $\leq n$. Then, $n\#<4^n$ for all positive integers $n$. Proof: The proof idea is due to Paul Erdős. Firstly, consider $k=\binom{2m-1}{m}=\dfrac{(2m-1)!}{m!(m-1)!}$. Note that all primes $m+1 \leq p \leq 2m-1$ appear on its numerator but not on its denominator. Thus, $\dfrac{(2m-1) \#}{m \#} \leq k=\dfrac{1}{2}(\binom{2m-1}{m}+\binom{2m-1}{m-1})<\dfrac{1}{2}(1+1)^{2m-1}=2^{2m-2}$. Now, we may easily dispose of the small cases. We proceed by strong induction on $n$. Assume that $n \geq 3$. If $n$ is even, then $n$ is not a prime and so $n\#=(n-1)\# <4^{n-1}<4^n$, as desired. On the other hand, if $n$ is odd, we may write $n=2m-1$ with $m \geq 2$, and so by the above estimate we obtain that $(2m-1)\# <2^{2m-2} \cdot m \# <2^{2m-2} \cdot 4^m=2^{4m-2}=4^{2m-1},$ as desired $\blacksquare$ And now, the rest of the proof is structured in some Claims. Claim 2: $2n-1$ divides $A$. Proof: Suppose not. Let $p_k=2n-1$, i.e. $2n-1$ is the $k-$th prime. Then, from the given condition we infer that $A<p_1 \ldots p_{k-1} \leq (2n-3)\#,$ Note that from our initial Claim $m\# < 4^m$ for all positive integers $m$, and so $A<(2n-3)\# <4^{2n-3}$. However, $A=nx^{n+1}+(2n+1)x^n-3(n-1)x^{n-1}-x-3>n^{n+2}+2n^{n+1}+3n^{n-1}-2n^n-n-3>n^{n+2},$ and so we obtain that $4^{2n-3}>n^{n+2}$, which is an immediate contradition since $n \geq 3$ $\blacksquare$ Claim 3: $x \equiv 1 \pmod {2n-1}$ or $x \equiv -3 \pmod {2n-1}$. Proof: Note that by Fermat's Little Theorem $x^{2n-2} \equiv 1 \pmod {2n-1}$, and so $x^{n-1} \equiv \pm 1 \pmod {2n-1}$. We consider two cases: Case 1: $x^{n-1} \equiv 1 \pmod {2n-1}$. Then, $0 \equiv A \equiv nx^2+(2n+1)x-3(n-1)-x-3=nx^2+2nx-3n=n(x-1)(x+3) \pmod {2n+1},$ and so $x \equiv 1 \equiv \pmod {2n+1}$ or $x \equiv -3 \pmod {2n+1}$. Case 2: $x^{n-1} \equiv -1 \pmod {2n-1}$. Then, $0 \equiv -nx^2-(2n+1)x+3(n-1)-x-3 \equiv -nx^2-(2n+2)x+3n-6 \equiv -(x+3)(nx-(3n-3)),$ and so $x \equiv -3 \pmod {2n-1}$ or $nx \equiv 3n-3 \equiv n-2 \pmod {2n-1},$ i.e. $x \equiv 2nx \equiv 2n-4 \equiv -3 \pmod {2n-1}$. All in all, we must always have that $x \equiv 1 \pmod {2n-1}$ or $x \equiv -3 \pmod {2n-1}$ $\blacksquare$ Claim 4: If $x \equiv 1 \pmod {2n-1}$ or $x \equiv -3 \pmod {2n-1}$, then we must have $(2n-1)^2 \mid A$. Proof: Let me present only the proof for the first case, as the proof for the second one is analogous. Assume that $x \equiv 1 \pmod {2n-1}$. Let $x=(2n-1)k+1$ for some positive integer $k$. Then, $x^i \equiv ((2n-1)k+1)^i \equiv 1+(2n-1)ki \pmod {(2n-1)^2},$ for all $i$, due to the Binomial Theorem. Thus, $A \equiv n(1+(2n-1)(n+1)k)+(2n+1)(1+(2n-1)nk)-(3n-3)(1+(2n-1)(n-1)k)-(1+(2n-1)k)-3 \equiv $ $\equiv 4k(2n-1)^2 \equiv 0 \pmod {(2n-1)^2},$ as desired $\blacksquare$ Returning to the problem, the result of the last Claim gives us the desired contradiction, since $A=p_2 \cdot p_3 \cdots p_\ell$ is supposed to be squarefree.