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. 
 A: Assuming $x$ is odd, $x\equiv1\pmod2$ so $2|x-1$ so $2|(x-1)+2=x+1,$
so $4|(x-1)(x+1)=x^2-1=x^2+2-3, $ so $ x^2+2\equiv3\pmod4$.
Let $p$ be a factor of $x^2+2$.  $p$ must be odd because $x$ and therefore $x^2+2$ is.
If all such factors were $\equiv1\pmod4$ then their product would be $\equiv1\pmod4$, a contradiction.
So $x^2+2$ has a prime factor $\equiv3\pmod4$.
A: It is the special case $\,n = 2\,$ below.
Theorem $\ \ \color{#0a0}{a\equiv b}\pmod{\!n}\,\Rightarrow\, a^{\large n}\equiv b^{\large n}\pmod{\!n^{\large 2}}\ $ for all integers$\ a,b,n\,$ with $\,n\ge 0$.
Proof $\ \ \ a^{\large n}-b^{\large n} = (a\!-\!b)f(a,b)\,$ for $\, f(a,b) = a^{\large n-1}\!+ a^{\large n-2}b\ +\ldots +a b^{\large n-2}\!+b^{\large n-1}$
$\!\bmod\color{#c00}n\!:\,\ \color{#0a0}{a\equiv b}\,\Rightarrow\, f(\color{#0a0}a,b)\equiv f(\color{#0a0}b,b)\equiv \color{#c00}n\,b^{\large n-1}\equiv 0\, $ by the Polynomial Congruence Rule.
Hence $\,n\mid a\!-\!b, f(a,b)\,\Rightarrow\, n^{\large 2}\mid (a\!-\!b)f(a,b) = a^{\large n}-b^{\large n}$
Remark $ $ Alternatively we can prove it via the Binomial Theorem or Double Root Test, e.g. see here. See also LTE = Lifting The Exponent
A: For a more quick way: Notice, $x^2+2$ is always odd, as $x$ is odd. Therefore, all prime divisors of $x^2+2$ are either of form $4k+1$ or $4k+3$. Now, if all of them are of form $4k+1$, then simply check that $x^2+2\equiv 1\pmod{4}$. However, since $x$ is odd, $x^2+2\equiv 3\pmod{4}$, which is yielding a contradiction. 
A: 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$.
