Factor A Degree 100000000 Polynomial

If $p$ is prime, then $a^j \equiv 1$ for all $1 \le a \le p-1$ , so that $x^{p-1} - 1 \; \equiv \; \prod_{j=1}^{p-1}(x - j)$ in $\mathbb{Z}_p[x]$ . Thus, if $f_p(x) \; = \; \prod_{j=1}^{p-1}(x-j) + 1 - p^2$ then $f_p(x) \,\equiv\, x^{p-1}$ in $\mathbb{Z}_p[x]$ . If $p^2$ fails to divide $(p-1)!+1$ , then $p^2$ does not divide the constant coefficient of $f_p(x)$ , and hence $f_p(x)$ is irreducible in $\mathbb{Z}[x]$ by Eisenstein's irreducibility criterion.

Thus the primes $p$ for which Eisenstein's Criterion, using the prime $p$ , fails to show that $f_p(x)$ is irreducible are the ones for which $p^2$ divides $(p-1)!+1$ . These primes are called Wilson primes . Only three Wilson primes are known up to $5 \times 10^8$ , these being $5$ , $13$ and $563$ . Since $f_5(x)$ has no constant term, it certainly is reducible. I haven't checked the reducibility of $f_{13}(x)$ and $f_{563}(x)$ , but it is clear that the number of primes $p$ between $1$ and $10^8$ for which $f_p(x)$ is reducible is at least $1$ and no more than $3$ , making $\boxed{\mbox{ between } 1 \mbox{ and } 9}$ the correct answer.