efoski1687 wrote: Let m be a positive integer. Prove that there exist infinitely many prime numbers p such that m+p^3 is composite. Do you know the answer?

Easy. Let $q$ be any prime such $(m,q)=1$. Let $t=m+q^3$. There are infinitely many primes in form $tk+q$ . If $p$ is such prime then obviously $p^{3} \equiv q^{3} \equiv -m (mod t)$.

RaleD wrote: Easy. Let $q$ be any prime such $(m,q)=1$. Let $t=m+q^3$. There are infinitely many primes in form $tk+q$ . If $p$ is such prime then obviously $p^{3} \equiv q^{3} \equiv -m (mod t)$. But I am not sure about this proof.Firstly it used Dirichlet's theorem,secondly this includes the term $tk+q=(m+q^3)k+q$ which involves a cubic term.But it is not defined that $n^2+1$ contains infinitely many primes.And as far I know this theorem works only for linear combinations.

1. The use of Dirichlet's theorem should be allowed - why not? 2. Who cares some expression is cubic? 3. Where is the assumption infinitely many primes are of the form $n^2+1$ being used? The proof is absolutely correct. Since $\gcd(m,q) = 1$, it follows $\gcd(m+q^3,q)=1$. Thus we can apply Dirichlet's to the arithmetic progression $q + kt$, where the ratio $t = m+q^3 > 1$. Take one of those infinitely many primes $p$. Then $m+p^3 = m + (q+kt)^3 \equiv m + q^3 = t \equiv 0 \pmod{t}$, so $t \mid m+p^3$. Since clearly $p>t$, whence $m+p^3 >t$, it means $m+p^3$ is composite.

A propos, there exists the solution which used Dirichlet's theorem only for progression $6k-1$. This is original solution from St-Petersbourg 2000.

Actually I don't know the solution and I tried to solve that without Drichlet's theorem. So I'm looking for a solution which is more elementary . nnosipov, if you know the solution, could you write it?

Fix a large prime $q\equiv 2\pmod{3}$ with $(q,m)=1$. Note that, $m^3\equiv n^3\pmod{q}\iff m\equiv n\pmod{q}$ (this follows from the fact that $-3$ is not a quadratic residue modulo $q$, or alternatively, from Fermat's theorem, letting $q=6k-1$, we have $m^3\equiv n^3\pmod{q}\implies m^{6k-3}\equiv n^{6k-3}\pmod{q}$, which, together with $m^{6k-2}\equiv n^{6k-2}\pmod{q}$ following from Fermat's theorem yields the claim). Thus, any integer, in particular, $-m$ is a cubic residue modulo $q$. Let $k^3\equiv -m\pmod{q}$. It then suffices to show that there exists infinitely many primes $p$ of form $p=qn+k$ where $n\in\mathbb{Z}^+$, which follows from Dirichlet's theorem on arithmetic progressions.

Let $m$ be a positive integer. Prove that there exist infinitely many prime numbers $p$ such that $m+p^3$ is composite.