Primes mod 4 and integer polynomials I have asked these questions as comments here (these are related to the question there). The questions are: Let $S$ be one of the following sets of primes:


*

*All primes of the form $4k+1$ ;

*All primes of the form $4k+3$; 

*All primes of the form $4k+1$ except $5, 13$;


Is there a monic integer polynomial which is reducible mod prime $p$ iff $p\in S$.
 A: Here is a way to argue without showing directly that the polynomial must have degree $2$. It was explained to me by Borys Kadets (all further mistakes are, of course, my contribution).
Lemma. If a set of primes $S$ of density $\frac{1}{2}$ admits such polynomial then some subset $S'\subset S$ with $\#(S\setminus S')<\infty$ admits a monic quadratic polynomial that is reducible precisely at $S'$.
Proof. Suppose that $f$ is a polynomial of degree $n$ satisfying the condition for the set $S$. Let $G$ be the Galois group of its splitting field coming with an embedding $G\subset S_n$. By Chebotarev density, exactly $\frac{1}{2}\# G$ elements of this group must be cycles of length $n$. 
Since the centralizer of a length $n$ cycle $\sigma\in S_n$ is the subgroup generated by $\sigma$, the number of conjugacy classes of length $n$ cycles in $G$ is $\frac{n}{2}$. In particular, $n$ is even and $G\cap A_n$ has index $2$ in $G$ with cycles of length $n$ forming the non-trivial coset. 
The subgroup $G\cap A_n\subset G$ corresponds to a degree $2$ extension $K/\mathbb{Q}$. If a prime $p$ is ramified in the splitting field of $f$ then $f$ is reducible modulo $p$. For any unramified prime $p$ the polynomial $f$ is reducible modulo $p$ iff the Frobenius element of a prime above $p$ in the splitting field is not a length $n$ cycle, the latter condition being equivalent to the fact that $p$ is split in $K$. Thus, the set of primes split (including ramified) in $K$ is equal to $S$ with the possible exception of a finite set of ramified primes. 
The minimal polynomial of a generator of $\mathcal{O}_K$ satisfies the conclusion of the lemma. $\square$
Starting with any of the three sets $S$ the lemma gives a quadratic polynomial $x^2+ax+b$ with $a,b\in \mathbb{Z}$ that is reducible precisely at the primes from a set $S'$. Since we want it to be irreducible mod $2$, both $a$ and $b$ have to be odd.
This polynomial is irreducible modulo $p>2$ if and only if $D:=a^2-4b$ is not a square mod $p$.
Set 2: The number $(-D)$ is supposed to be a non-residue modulo all but finitely many primes, but that's impossible. This can be shown by a counting argument: if there was a finite set of primes $p_1,\dots, p_k$ such that $D+n^2$ is a product of powers of $p_i$'s then there would be $O((\log N)^k)$ numbers of the form $D+n^2$ in the interval $[1,\dots, N]$.
Sets 1 and 3: Here we want $(-D)$ to be a square modulo all but finitely many primes. That forces it to be a square in $\mathbb{Z}$. However, setting $-D=c^2$ gives $a^2+c^2=4b$. That is impossible for odd $a$.
