# Find all prime p such that Legendre symbol of $\left(\frac{10}{p}\right)$ =1

In the given question I have been able to break down $\left(\frac{10}{p}\right)$= $\left(\frac{5}{p}\right)$ $\left(\frac{2}{p}\right)$. But what needs to be done further to obtain the answer.

• Use the formula $\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \mod p$ for $p$ an uneven prime and then consider cases $p\equiv 1$ or $3\mod 4$. May 1, 2016 at 21:29

Hint:

By the second supplementary law of quadratic reciprocity,$\biggl(\dfrac 2p\biggr)=1$ if and only if $p\equiv \pm 1\mod 8$.

On the other hand, $\biggl(\dfrac 5p\biggr)=\biggl(\dfrac p5\biggr)=1\;$ if and only if $p\equiv \pm 1\mod 5$.

So you have to solve the systems of congruences: \begin{align*} \begin{cases} p\equiv \pm 1\mod8\\p\equiv\pm 1\mod 5 \end{cases}&& \begin{cases} p\equiv \pm3\mod8\\p\equiv\pm 2\mod 5 \end{cases} \end{align*}

This is done with the Chinese remainder theorem. I'll show for one, say $p\equiv 3\mod 8,\;p\equiv 2\mod 5$: start from the Bézout's relation $\:2\cdot 8-3\cdot 5=1$. The solutions are then $$p\equiv 3\cdot (2\cdot 8)-2\cdot(3\cdot 5)\equiv18\mod 40.$$ There is no prime number in this congruence class.

• could you briefly explain why $(5/p) = 1$ iff $p \equiv 1, -1$ mod $5$ ? Mar 4, 2020 at 0:46
• @mathmajor: This is simply because it is equal to $\bigl(\frac p5\bigr)$ (by quadratic reciprocity) and the only non-zero squares modulo $5$ are $1$ and $-1$. Mar 4, 2020 at 9:27

Let $p$ be an odd prime $\ne 5$.

Note that $(2/p)=1$ if and only if $p\equiv \pm 1\pmod{8}$, and $(5/p)=1$ if and only if $p\equiv \pm 1\pmod{5}$. The first is a standard fact that has probably been proved in your book/course. The second can be proved using Quadratic Reciprocity.

So $(10/p)=1$ if $p\equiv \pm 1\pmod{8}$ and $p\equiv \pm 1\pmod{5}$.

But also $(10/p)=1$ if $(2/p)=-1$ and $(5/p)=-1$. This is the case if $p\equiv \pm 3\pmod{8}$ and $p\equiv \pm 3\pmod{5}$.

Our conditions can be "simplified" by expressing them modulo $40$. After some work, we find that the odd prime $p$ satisfies our conditions if and only if $p\equiv \pm 1\pmod{40}$, $\pm 3\pmod{40}$, $\pm 9\pmod{40}$, or $\pm 13\pmod{40}$.