1
$\begingroup$

Find all the prime numbers $p$ which have a solution to $x^2\equiv14\bmod p$.

I found that for $p=2,5,7$ there is a solution and for $p=3$ there's no solution.
I tried using Legendre symbol because the given equation has a solution iff $(\frac{14}{p})=1 \iff (\frac{2}{p})(\frac{7}{p})=1$ but I get too many sub cases.

$\endgroup$
4
$\begingroup$

The "second supplement to quadratic reciprocity" states that $\left(\frac2p\right)=1\iff p\equiv\pm1\bmod8$. It remains to work out $\left(\frac7p\right)$. $$\left(\frac7p\right)\left(\frac p7\right)=(-1)^{3(p-1)/2}$$ Since $\left(\frac p7\right)=1\iff p\equiv 1,2,4\bmod7$ and the RHS is $1$ iff $p\equiv1\bmod4$, $\left(\frac7p\right)=1$ iff an even number of $p\equiv 1,2,4\bmod7$ and $p\equiv1\bmod4$ are true. Then $\left(\frac{14}p\right)=1$ iff an odd number of $p\equiv 1,2,4\bmod7$, $p\equiv1\bmod4$, $p\equiv\pm1\bmod8$ are true.

The last two conditions can be combined rather easily: an even number of them are true iff $p\equiv1,3\bmod8$. Thus $\left(\frac{14}p\right)=1$ iff an even number of $p\equiv1,2,4\bmod7$ and $p\equiv1,3\bmod8$ are true. By the CRT, this combines into $$p\equiv1,5,9,11,13,25,31,35,43,45,47,51\bmod56$$

All along we have ignored the exceptional cases, but the question already provides them. So we have the final result: $$\left(\frac{14}p\right)=1\iff p\equiv1,2,5,7,9,11,13,25,31,35,43,45,47,51\bmod56$$

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