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.


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.

  • $\begingroup$ Fantastic! Thank you so much $\endgroup$ – 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}$.

  • 2
    $\begingroup$ 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$. $\endgroup$ – André Nicolas May 15 '13 at 20:59
  • $\begingroup$ 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? $\endgroup$ – Olivia77989 May 15 '13 at 21:31
  • $\begingroup$ 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). $\endgroup$ – André Nicolas May 15 '13 at 21:38
  • $\begingroup$ 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? $\endgroup$ – Olivia77989 May 15 '13 at 21:46
  • $\begingroup$ 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! $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.