It is known that $2$ is a quartic residue mod a prime $p\equiv_{8}1$ if and only if $p$ can be represented as $x^2+64y^2$. Is it known whether there are infinitely many such primes?
See [Cox, Primes of the form $x^2 + ny^2$], p. 110, Theorem 5.26. There are infinitely many such primes since infinitely many primes split completely in the Hilbert class field, which follows from Chebotarev's density theorem, but there is also a completely elementary argument (analogous to Euclid's proof that there are infinitely many primes). 


You want an elementary argument for the existence of an infinite set of primes $p$ which at once divide a number of the form $x^42$ and a number of the form $y^4+1$, where $x,y \in \mathbb{Z}$. Here is a recipe which expands on Timo Keller's hint. I claim that there are rational polynomials $U,V \in \mathbb{Q}[X]$ such that $U^42$ and $V^4+1$ share a common nonconstant factor $P \in \mathbb{Q}[X]$. To see the claim, just consider an $\alpha \in \mathbb{Q}(\sqrt[4]{2},e^{\pi i/4})$ such that $\mathbb{Q}(\sqrt[4]{2},e^{\pi i/4}) = \mathbb{Q}(\alpha)$; for example, $\alpha := \sqrt[4]{2}+e^{\pi i/4}$ will do. Then you can express $\sqrt[4]{2} = U(\alpha)$ and $e^{\pi i/4} = V(\alpha)$ with $U,V \in \mathbb{Q}[X]$. Now both polynomials $U^42$ and $V^4+1$ are divisible in $\mathbb{Q}[X]$ by the minimum polynomial $P(X) \in \mathbb{Q}[X]$ of $\alpha$. It is thus sufficient to consider (large enough) primes which divide some value $P(n)$, $n \in \mathbb{Z}$. You know how to conclude a la Euclid: if $p_1,\ldots,p_k$ were all such primes, the consideration of $P\big(Np_1\cdots p_k\big)$ would lead you to contradiction for $N \gg 0$. 


There are two parts here. One is the fact that any primitive binary quadratic form (unless it is indefinite and factors, such as $x^2  y^2$) represents infinitely many primes. The original articles are shown here: primes represented by an indefinite binary quadratic form while there is an "elementary" proof much later (1954), by W.E. Briggs, a student of Burton Wadsworth Jones at U. Colorado, Boulder. Next, when do we get such a clear bijection, primes represented by a (principal) form being precisely those for which a monic quartic factors nicely? That answer is in LiuWilliams 1994, which I put at INHOMOGENEOUS. There is also a very nice table by Henri Cohen there, some of the same information. Similar for monic cubics in HudsonWilliams 1991. For instance, a prime other then 2,3,23, is represented by $x^2 + xy + 6 y^2$ if and only if $(p23)=1$ and $z^3  z + 1 $ factors nicely $\pmod p.$ This led to my first MO question, what integers are integrally represented by $$ 2 x^2 + x y + 3 y^2 + z^3  z, $$ one direction proved by Kevin Buzzard and the other direction unsure. Very similar, what integers are integrally represented by $$ 4 x^2 + 2 x y + 7 y^2 + z^3 , $$ one direction quite easy (I sent it as a problem in the MAA Monthly), one direction open. Let's see, problem 11539, December 2010, (page 929), single answer by Robin Chapman, December 2012, pages 884885; Robin's one reference was the Cox book. Finally, i can tell you that the complex multiplication method of finding these polynomials tends to produce huge coefficients, and these few articles give quite rare instances where small coefficients of everything are known. Finally, there is a very nice article by Stevenhagen and Lenstra, 1996 in the Mathematical Intelligencer, Chebotarev and his Density Theorem in which the earlier result of Frobenius (1880) is discussed; the set of primes $p$ for which a monic, irreducible polynomial $ f \in \mathbb Z[x],$ of degree $n,$ factors into $n$ linear factors is infinite and has a (predictable) natural density. The same can be said about other factoring patterns; infinitely many primes for which $f$ is irreducible, infinitely many primes where the factorization is a linear times an irreducible of degree $(n1)$ and so on. Evidently the only standard book to include this Frobenius result is Janusz... Frobenius density theorem 

