Existence of a prime If $x$ is odd and natural and ${x^2}+2\equiv3\mod 4$, how can I show there exists a prime $p$ such that $p|x^2+2$ and $p\equiv3\mod 4$.
 A: Let $n=x^2+2$. Note that $n$ is odd. If all the prime divisors of $n$ were of the shape $4k+1$, then $n$ also would be. For the product of any two numbers congruent to $1$ modulo $4$ is itself congruent to $1$ modulo $4$. 
Remark: The $x^2+2$ stuff is just intended to distract you. Not nice!
A: Any number $n$ of the form $3 \pmod4$, must have a prime factor of the form $3 \pmod4$. If all the primes dividing $n$ were to be of the form $1 \pmod4$, then the product of these primes (including multiplicity) is again of the form $1 \pmod 4$, since $$\left(1 \pmod 4 \right) \times \left( 1 \pmod4 \right) \equiv (1 \times 1) \pmod4 \equiv 1 \pmod4$$

Additional note
We can in fact say something more, if we consider all the primes of the form $3 \pmod 4$ dividing $n$, say $q_1,q_2,\ldots,q_k$, and we write $n$ as
$$n = p_1^{a_1} p_2^{a_2} \cdots p_l^{a_l} q_1^{b_1} q_2^{b_2} \cdots  q_k^{b_k}$$ where $p_j \equiv 1 \pmod 4$, since $n \equiv 3 \pmod4$, we must have $\displaystyle \sum_{j=1}^k b_j \equiv 1 \pmod 2$.
