<s>[INST] Show that $x^2+2 \equiv 3 \mod 4$ and deduce that there exists a prime $p$ with $p|x^2+2$ and $p \equiv 3 \mod 4$. Let $x$ be an odd natural number. Show that $x^2+2 \equiv 3 \mod 4$ and deduce that there exists a prime $p$ with $p|x^2+2$ and $p \equiv 3 \mod 4$.
For the first part I would assume 
$$x \equiv 1 \mod 2$$
$$x^2 \equiv 1^2 \mod 2^2$$
$$x^2 +2 \equiv 1^2+2 \mod 2^2$$
$$x^2 +2 \equiv 3 \mod 4$$
Can someone briefly tell me if this is correct and if it is a rule that squaring the number on the left means you square both numbers on the right?
Also I don't know how to start with the second part. 
Note: This question is to do with rings in general. 
 [/INST] First, you can square both sides in the congruence relation but you must not square the number that you are "moding".
If $x$ is odd, then $x\equiv1$ or $3$ (mod $4$). So, by some calculations, 
$$x^2\equiv1(\mod 4)$$
$$x^2+2=3(\mod 4)$$
Then, for the next part, we will use prove by contradiction.
First, we can see that all of the factors of $x^2+2$ is odd because $x^2+2$ is odd.
If $x^2+2$ has no prime factor which has a remainder of $3$ when divided by $4$, then $x^2+2$ should have only prime factors which has a remainder of $1$ when divided by $4$. As the product of any number of numbers that leaves a remainder of $1$ when divided by $4$ also has a remainder of $1$ when divided by $4$, so it contradicts that $x^2+2\equiv3 (\mod 4)$
$\therefore x^2+2 $ has at least one factor that leaves a remainder of $3$ when divided by $4$.
</s>