Prove that there exist infinitely many primes $p$ such that $13 \mid p^3+1$ $\textbf{Question:}$Prove that  there exist infinitely many  primes $p$ such that $13 \mid p^3+1$
I could easily see that the given is equivalent to showing that there are infinitely many primes $p$ such that, $p \equiv \{4,10,12\} \pmod{13}$
To prove this,I wanted to somehow generalize the idea used to show the infinitude of primes of the form $4k+1$.
And yes,this whole thing follows easily from drichlet theorem.But I was looking for a somewhat elementary proof.
 A: Yes, there is an elementary proof which requires nothing more than quadratic reciprocity.
Thanks to @lhf for the pointer to Murty’s classical paper on this.  I had heard about it but never seen the proof before, and the result of Schur cited in the paper was enlightening.  Murty’s paper is already sufficient to answer the OP because it implies we can pick out primes that are $12 \pmod{13}$, but it’s a bit unsatisfying not to include the other two residues by a simpler construction.  This is indeed possible!
Note that the set of residues $\{4,10,12\}$ is equal to the set difference of the subgroups $\langle 4 \rangle$ (of order 6) and $\langle 3\rangle = \{1,3,9\}$ in $(\mathbb Z/13\mathbb Z)^\times$.  This affords us the following strategy:

*

*Choose a polynomial $f$ such that the primes dividing $f(n)$ always lie in the subgroup $\langle 4 \rangle$.

*Further select $f$ so that $f(n)$ does not belong to $\{1,3,9\} \pmod{13}$, so that at least one prime factor belongs to the coset $\{4,10,12\}$.

The theorem of Schur cited by Murty assures us that 1 is possible, but in this case it’s a familiar object: since $(\mathbb Z/13\mathbb Z)^\times$ is cyclic, the unique subgroup of order 6 is just the set of quadratic residues, so reciprocity gives us this easily by choosing $f$ so that $13$ is a quadratic residue mod $f(n)$, such as $f(n) = 4n^2 - 13$.  To satisfy 2, we just need to tweak it very slightly: $f(n) := 52n^2-1$ will do.
We now proceed with the Euclidean argument.  Let $p_1, \ldots, p_k$ be any finite (possibly empty) list of primes congruent to $\{4,10,12\}$, and take $P = 52(p_1 \cdots p_k)^2 - 1 > 1$.  Let $q$ be a prime divisor of $P$.  Clearly $q$ is odd, and has $52$ (hence $13$) as a quadratic residue, so by reciprocity $q$ belongs to one of the residue classes $\{1,3,4,9,10,12\}$ mod 13.  And $q$ cannot be equal to any of the $p_i$ since $P$ is coprime to all of them.
So $P$ is composed entirely of primes in those 6 classes, but since $P\equiv 12 \pmod{13}$ (and $P$ is positive), at least one prime divisor of $P$ does not belong to any of the 3 residue classes $\{1,3,9\}$ mod 13.  This divisor is thus a prime congruent to $\{4, 10, 12\}$ mod 13 which does not appear in the original list of $k$ primes, which completes our argument.
