I have asked these questions as comments [here](https://mathoverflow.net/questions/352105/a-sufficient-condition-for-a-set-of-primes-to-be-the-set-of-reducibility-of-an-i/352109#352109) (these are related to the question there). The questions are: Let $S$ be one of the following sets of primes:


1. All primes of the form $4k+1$ ;
2. All primes of the form $4k+3$;
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$.



Primes mod 4 and integer polynomials
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$.


