Let $n$ be a natural number and $P_1, P_2, ... , P_n$ are polynomials with integer coefficients, each of degree at least $2$. Let $S$ be the set of all natural numbers $N$ for which there exists a natural number $a$ and an index $1 \le i \le n$ such that $P_i(a) = N$. Prove, that there are infinitely many primes that do not belong to $S$.
Problem
Source: IFYM - XI International Festival of Young Mathematicians Sozopol 2022, Theme for 11-12 grade,finals p6
Tags: polynomial, algebra
23.12.2022 07:38
The formulation should say "infinitely many", not "uncountably many".
23.01.2023 00:03
Suppose otherwise. Since the polynomials are finitely many and of degree at least 2, there are constants $c$ and $C$, such that $|P_i(x)|\geq cx^2$ for all $i=1,\ldots,n$ and $x \geq C$. Hence \[\sum_{i=1}^n\sum_{k=\lceil C \rceil}^{\infty} \frac{1}{|P_i(k)|}\leq \sum_{i=1}^n\sum_{k=c}^{\infty} \frac{1}{ck^2}\leq \frac{4n}{c}\](we used $\displaystyle \sum_{k=1}^{\infty} \frac{1}{k^2} \leq 1 + \sum_{k=2}^{\infty} \frac{1}{k(k-1)} = 1 + \sum_{k=2}^{\infty} \left(\frac{1}{k-1} - \frac{1}{k}\right) = 2$). This contradicts the well known fact that $\displaystyle \sum_{j=1}^{\infty} \frac{1}{p_j}$ (where $p_j$ is the $j$-th prime) is infinite, contradiction.
01.05.2023 02:43
p.lazarov06 wrote: Suppose otherwise. Since the polynomials are finitely many and of degree at least 2, there are constants $c$ and $C$, such that $|P_i(x)|\geq cx^2$ for all $i=1,\ldots,n$ and $x \geq C$. Hence \[\sum_{i=1}^n\sum_{k=\lceil C \rceil}^{\infty} \frac{1}{|P_i(k)|}\leq \sum_{i=1}^n\sum_{k=c}^{\infty} \frac{1}{ck^2}\leq \frac{4n}{c}\](we used $\displaystyle \sum_{k=1}^{\infty} \frac{1}{k^2} \leq 1 + \sum_{k=2}^{\infty} \frac{1}{k(k-1)} = 1 + \sum_{k=2}^{\infty} \left(\frac{1}{k-1} - \frac{1}{k}\right) = 2$). This contradicts the well known fact that $\displaystyle \sum_{j=1}^{\infty} \frac{1}{p_j}$ (where $p_j$ is the $j$-th prime) is infinite, contradiction. Interesting solution
09.09.2023 20:20
Let $P\in\mathbb{Z}[x]$ be a polynomial having $\deg P\geq 2$. We will prove that there are infinitely many pairs $(p,r_p)$ where $p$ is a prime not dividing $r_p$ such that $P(x)\equiv r_p\pmod{p}$ does not have a solution. Let's look at $Q(x)=P(x+1)-P(x)$. We know that $\deg Q=\deg P-1\geq 1$, hence by Schur's theorem we get infinitely many primes $q$, dividing $Q(x_q)$ for some $x_q\in\mathbb{Z}$. Let's take $q>1+\deg P=d+1$. Then assume $q$ does not require the desired condition. It means that for each $c\not\equiv 0 \pmod{q}$ $P(x)\equiv c\pmod{p}$ has a solution. But we know that there is a residue which appears at least twice in $P(0), P(1),\dots, P(q-1)$. So we get that in the set $\{P(k)\vert k=0,1,\dots,q-1\}$ there are all nonzero residues modulo $q$ and one of them occurs twice - denote it with $r$. Also, let's write $P(x)=a_dx^d+\dots+a_0$. Then \[r\equiv r+1+2+\dots+q-1\equiv\sum_{k=0}^{q-1}P(k)=\sum_{i=0}^d\left(a_i\sum_{k=0}^{q-1}k^i\right)\]To finish off the solution we'll prove that $\sum_{k=0}^{q-1}k^i=\sum_{k=1}^{q-1}k^i\equiv0\pmod{q}$ for all $i\leq d$. Let $\varphi$ be a primitive root modulo $q$. Then \[\sum_{k=1}^{q-1}k^i\equiv\sum_{k=0}^{q-2}(\varphi^{i})^{k}\equiv \frac{(\varphi^i)^{q-1}-1}{\varphi^i-1}\equiv 0\pmod{q} \text{, because we have $q-1\nmid i$}.\]The last one gives us $r\equiv 0\pmod{q}$, which is a contradiction. Now, we've proved that there are different $p_1,p_2,\dots,p_n$ and $c_1,c_2,\dots,c_n$ such that $p_i\nmid c_i$ and $P_i(x)\equiv c_i\pmod{p_i}$ has no solutions for every $i\leq n$. The Chinese Remainder Theorem provides us $T\equiv c_i\pmod{p_i}$ for some $T$, so the Dirichlet's theorem gives us infinitely many primes of the form $lp_1p_2\dots p_n+T$, each of which is not achievable.