3
$\begingroup$

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"?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Kaish Apr 24 '13 at 22:22
  • 1
    $\begingroup$ 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? $\endgroup$ – Zev Chonoles Apr 24 '13 at 22:23
  • $\begingroup$ 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? $\endgroup$ – Kaish May 27 '13 at 8:38
  • $\begingroup$ @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$. $\endgroup$ – Zev Chonoles May 27 '13 at 8:51
  • $\begingroup$ 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? $\endgroup$ – Kaish May 27 '13 at 8:56
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.