# 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.

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.

• Fantastic! Thank you so much – Olivia77989 May 15 '13 at 20:53

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}$.

• You are welcome. You probably already ran into the fact that every positive integer of the form $4k+3$ has a prime divisor of the form $4k+3$. That fact plays a key role in the standard proof that there are infinitely many primes of the form $4k+3$. – André Nicolas May 15 '13 at 20:59
• A useful insight! So would I be right in thinking that in order to prove there are infinitely any primes of the form $4k +3$ , I would split $4k +3$ into its prime divisors $p1,p2...pn$ noting that at least one of these divisors is of the form $4k +3$, then, following a similar approach to Euclid's proof, consider N=4(p1. p2.....pn)+3 ? Or what would we equate N to and why? – Olivia77989 May 15 '13 at 21:31
• Yes, suppose there are finitely many primes $p_1,\dots,p_s$ of the right shape. Consider $N=4p_1\cdots p_s-1$. This is of the shape $4k+3$, so has a prime divisor of that shape, which must be different from the $p_i$. I am avoiding $N=4p_1\cdots p_s+3$, since maybe $N$ could be a power of $3$ (there are other ways around that issue). – André Nicolas May 15 '13 at 21:38
• I see. Possibly a silly question, but how do we know that the prime divisor of N in the form $4k+3$ is different from the $p_i$ already in our list? – Olivia77989 May 15 '13 at 21:46
• With $N=4p_1\cdots p_s -1$, if it was in list, it would divide $4p_1\cdots p_s$. Since it divides $4p_1\cdots p_s-1$, it would divide the difference, which is $1$. Impossible! – André Nicolas May 15 '13 at 21:56

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.