Deduce that there exists a prime $p$ where $p$ divides $x^2 +2$ and $p≡3$ (mod 4) I am revising for a number theory exam and have a question that I am struggling with, any help would be greatly appreciated.
First I am asked to show that for an odd number $x$, $x^2+2 ≡3$(mod 4).  
I can do this part of the question, but next I am asked to deduce that there exists a prime $p$ where $p$ divides $x^2 +2$ and $p≡3$ (mod 4)
I am struggling to see how to attempt the second part and how the first part relates.
My thoughts so far are that I want to show $x^2≡-2$(mod p) ?
 And perhaps Fermat's Little Theorem could be of use here somehow?
Not sure if I'm barking up the wrong tree though.    
Thanks in advance.
 A: Our number $x^2+2$ is odd, and greater than $1$, so it is a product of odd not necessarily distinct primes. If all these primes were congruent to $1$ modulo $4$, their product would be congruent to $1$ modulo $4$. But you have shown that $x^2+2\equiv 3\pmod{4}$.
A: Consider the prime factorization of $x^2+2$. Since $x$ is odd, $x^2+2$ is odd implying $2$ will not show up in the factorization. Now consider the primes that DO show up in the prime factorization. If they are all $1$ in modulo 4, then their product will also be one in modulo $4$. This is not true though, since you know that $x^2+2$ is $3$ modulo $4$. Therefore, there must be a prime that in the prime factorization of $x^2+2$ s.t. it is not $1$ modulo 4. Since primes other than 2 that are not $1$ modulo 4 are $3$ modulo $4$, this completes the reasoning. 
A: The question, as asked, has been answered.  Nevertheless, I'll show how quadratic residues can help in problems like these, and show that moreover $x^2+2$ ($x$ odd) has a prime factor congruent to $3 \!\!\!\mod 8$:
Suppose that $x$ is odd.  If $p$ divides $x^2+2$, then $p$ is odd and $x^2 \equiv -2 \!\!\mod p$.  In particular, $-2$ is a square mod $p$, hence
$$1=\left(\frac{-2}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/2} (-1)^{(p-1)/2}=(-1)^{(p^2+p-2)/2}.$$
This implies $p \equiv 1,3 \!\!\mod \!8$.  If each prime $p$ dividing $x^2+2$ were congruent to $1 \!\!\mod 8$, then $x^2+2$ would be congruent to $1\!\! \mod 8$.  This is a contradiction, hence there exists some $p \mid x^2+2$ congruent to $3 \!\!\mod 8$.  (In fact, there must be an odd number of such primes.)
Of course, any one of the primes is congruent to $3 \!\!\mod 4$, which gives your result.
We can ignore quadratic residues in your particular problem because there are only two odd residues mod $4$.  In more difficult questions, looking at quadratic residues can give more information.
