# Find the values of $p$ such that $\left( \frac{7}{p} \right )= 1$ (Legendre Symbol)

Show that if $p$ is an odd prime coprime to $7$, then $\left( \frac{7}{p} \right) = 1$ if and only if $p \equiv \pm 1, \pm 3,$ or $\pm 9 \pmod{28}$. HINT: If $p$ is an odd prime, determine which values can $p$ take $\mod28$, and consider each of these values in turn. Note that if we know $p \mod 28$ then we know $p \mod 4$, and hence we know whether $\frac{p-1}{2}$ is odd or even.

Here, $\left( \frac{a}{b} \right)$ is the Legendre symbol.

The bit I don't understand in the hint is, what do they mean by consider the values that $p$ can take $\mod 28$. Do they mean the values that would make $p$ a quadratic residue $\mod 28$, i.e all the $x$ values satisfying $x^2 \equiv \mod 28$, because then isn't this just $1,4,9,16,25$?

What do they mean the to "consider each of these values in turn"?

Hint: Apply quadratic reciprocity to $\bigl(\frac{7}{p}\bigr)$. You will see that the only relevant things affecting the outcome are what $p$ is modulo 4, and what $p$ is modulo 7. By the Chinese remainder theorem, that is the same information as what $p$ is modulo 28.

• I was going to do QR, but then I got stuck because I got $(-1)^{(3)(p-1)/2}$ which could be both odd or even. What does that mean though, that "what $p$ is modulo $4$? I.e what $p$ value gives me $4 \mod 7$? – Kaish Apr 24 '13 at 22:22
• That's not getting stuck; that's an indication that you should break your work into cases. Can you characterize which $p$'s will have $\frac{6(p-1)}{2}$ be even, and which $p$'s will have it be odd? – Zev Chonoles Apr 24 '13 at 22:23
• Why do we consider the case $\mod 4$? I mean, I can see that this is needed as the solution is in terms of $\mod 28$, but why do we use $\mod 4$? Would this always be the case in these types of questions? – Kaish May 27 '13 at 8:38
• @Kaish: The Chinese remainder theorem tells you that if the prime factorization of $n$ is $p_1^{a_1}\cdots p_k^{a_k}$, then knowing $x\bmod n$ is equivalent to knowing $x\bmod p_1^{a_1}$ and $x\bmod p_2^{a_2}$ and ... and $x\bmod p_k^{a_k}$. The prime factorization of $28$ is $2^2\cdot 7$. – Zev Chonoles May 27 '13 at 8:51
• So literally the only reason we pick $4$ is because we have a $7$ and can see it's $\mod 28$? If they gave me say $21$ or $63$, then I would pick my values $\mod 3$ or $\mod 9$?. Also, I'm working through it and I said that if I chose $(p-1)/2$ odd, then I use $p\equiv 3 \mod 4$ as I get $(p-1)2 = 2k + 1 \implies p - 1 \equiv 4k + 2 \implies p \equiv 4k + 3$, but for some reason I have to use $1 \mod 4$? Why is this? Isn't that if $(p-1)/2$ is even? – Kaish May 27 '13 at 8:56

Let $p \neq 7$ be an odd prime.

Suppose first that $p \equiv 1 \pmod{4}$. Then by Quadratic Reciprocity $(\frac{7}{p}) = (\frac{p}{7})$, so $(\frac{7}{p}) = 1$ iff $p$ is a square modulo $7$, i.e., iff $p \equiv 1,2,4 \pmod{7}$. We need to consolidate this mod $7$ information with our assumption that $p \equiv 1 \pmod{4}$: since $4$ and $7$ are relatively prime, this is accomplished by the Chinese Remainder Theorem, and the answer will be a set of congruence classes modulo $28$.

Next you have to do the case that $p \equiv 3 \pmod{4}$, so you have to apply the case of Quadratic Reciprocity in which your two odd primes are both $3 \pmod{4}$: there is an extra minus sign. Again you can use the Chinese Remainder Theorem to compile this into a list of congruence classes modulo $28$.

Here is a solution that avoids the casework suggested by Zev Chonoles. Note that the computation of $\left(\tfrac{-7}{p}\right)$ is much easier. Once we know this, the computation of $\left(\tfrac{7}{p}\right)$ falls to CRT. By the Quadratic Reciprocity law, $$\left(\frac{-7}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{7}{p}\right)=\left(\frac{p}{7}\right)(-1)^{(p-1)/2}(-1)^{(p-1)(7-1)/4}=\left(\frac{p}{7}\right)(-1)^{2(p-1)}=\left(\frac{p}{7}\right)=p^3.$$ Thus, in order for $\left(\tfrac{-7}{p}\right)=1$, we want $p^3\equiv 1\pmod{7}$. A difference of cubes factorization yields $(p-1)(p^2+p+1)\equiv 0\pmod{7}$, so $p\equiv 1\pmod{7}$ or $p^2+p+1\equiv 0\pmod{7}$. In order to make the latter case easy to work with, note that $$p^2+p+1\equiv p^2+p-6=(p+3)(p-2)\equiv 0\pmod{7},$$ so $p\equiv -3,2\pmod{7}$. Summarizing, $\left(\frac{-7}{p}\right)=1\iff p\equiv 1,2,4\pmod{7}$. Now, using that $\left(\frac{7}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{-7}{p}\right)$ along with a straightforward application of CRT should yield the required result.

EDIT: I'm being silly - no need to solve the cubic, just note that the quadratic residues modulo $7$ are $1$, $2$, and $4$.