# How is 4 a quadratic residue of 7?

On Wolfram's dictionary, it shows that the quadratic residues of 7 are 1,2,4. It shows that the quadratic residues of 5 are 1,4. I tested 1 and 4, and as you can see: $$1^2 = 1 \pmod 5$$ and $$4^2= 16 \pmod 5 = 1 \pmod 5$$ since 5*3 = 15

If $4^2 = 16 \pmod 7 = 2 \pmod 7$

Doesn't this mean it would fail the criterion that a quadratic residue must be congruent to a perfect square modulo p (here, p = 7) ? Doesn't it need to always be congruent to $1 \pmod p$ ?

• $\;2^2=4=4\pmod 7\;$...in fact, $\;4\;$ (and any other natural square) is a quadratic residue modulo any prime...though not always a non-zero one. – DonAntonio Mar 5 '14 at 13:56
• Right, just realized that any time you get another perfect square as the remainder then the number that yielded that is a quadratic residue – Arthur Collé Mar 5 '14 at 14:05
• I believe you mean "$4$ is a quadratic residue mod $7$." This means that there is an $x$ so that $x^2\equiv4\pmod7$. – robjohn Apr 9 '15 at 9:51

In short, $2^2 \equiv 5^2 \equiv 4 \pmod 7$. Since $4$ appears as a square, we see that $4$ is a quadratic residue.
In fact, $4$ is always a square mod primes. When looking mod $2$, we see that $4$ is zero (so it's the trivial square). Otherwise, $4$ will always appear as the square of $2$, regardless of whatever prime we are modding by.
In fact you've just shown that it does not: $2\equiv4^2\pmod7$, hence $2$ is (by definition) a quadratic residue modulo $7$ because it is congruent to the square $4^2$.
The fact that $2$ itself is not a square does not mean it can't be a quadratic residue.