# For which primes $p \ne 2,5$ does the congruence $x^2 \equiv 10 \mod p$ have a solution?

For which primes $p \ne 2,5$ does the congruence $x^2 \equiv 10 \mod p$ have a solution?

Using the Legendre symbol, we have $\left(\dfrac{10}{p}\right) = \left(\dfrac{5}{p}\right) \left(\dfrac{2}{p}\right).$

Observe that:

$\left(\dfrac{2}{p} \right) = \left\{ \begin{array}{lr} 1 & : p \equiv 1 \pmod 8 \text{ or } p \equiv 7 \pmod 8 \\ -1 & : p \equiv 3 \pmod 8 \text{ or } p \equiv 5 \pmod 8 \end{array} \right.$

and for an odd prime $p \ne 5,$ we have:

$\left(\dfrac{5}{p} \right) = \left\{ \begin{array}{lr} 1 & : p \equiv 1 \pmod 5 \text{ or } p \equiv 4 \pmod 5\\ -1 & : p \equiv 2 \pmod 5 \text{ or } p \equiv 3 \pmod 5 \end{array} \right.$

The congruence $x^2\equiv 10\mod{p}$ has a solution if $\left(\dfrac{2}{p} \right) = \left(\dfrac{5}{p} \right).$ Thus $\left(\dfrac{2}{p} \right) = \left(\dfrac{5}{p} \right) = 1$ for $(1,1),(1,4),(7,1),(7,4) \in \mathbb{Z}/8\mathbb{Z} \times \mathbb{Z}/5 \mathbb{Z}$ and $\left(\dfrac{2}{p} \right) = \left(\dfrac{5}{p} \right) = -1$ for $(3,2),(3,3),(5,2),(5,3) \in \mathbb{Z}/8\mathbb{Z} \times \mathbb{Z}/5 \mathbb{Z}.$ To determine where these elements get mapped to in $\mathbb{Z}/ 40 \mathbb{Z},$ note that $8 \cdot 7 \equiv 1 \pmod 5$ and that $5 \cdot 5 \equiv 1 \pmod 8.$

Hence:

$5 \cdot 5 \cdot 1 + 8 \cdot 7 \cdot 1 = 81 \equiv 1 \mod 40,$

$5 \cdot 5 \cdot 1 + 8 \cdot 7 \cdot 4 = 249 \equiv 9 \mod 40,$

$5 \cdot 5 \cdot 7 + 8 \cdot 7 \cdot 1 = 231 \equiv 31 \mod 40,$

$5 \cdot 5 \cdot 7 + 8 \cdot 7 \cdot 4 = 399 \equiv 39 \mod 40,$

$5 \cdot 5 \cdot 3 + 8 \cdot 7 \cdot 2 = 187 \equiv 27 \mod 40,$

$5 \cdot 5 \cdot 3 + 8 \cdot 7 \cdot 3 = 243 \equiv 3 \mod 40,$

$5 \cdot 5 \cdot 5 + 8 \cdot 7 \cdot 2 = 237 \equiv 37 \mod 40,$

$5 \cdot 5 \cdot 5 + 8 \cdot 7 \cdot 3 = 293 \equiv 13 \mod 40,$

meaning that $(1,1) \mapsto 1, \hspace{1mm} (1,4) \mapsto 9, (7,1) \mapsto 31, (7,4) \mapsto 39, (3,2) \mapsto 27, (3,3) \mapsto 3, (5,2) \mapsto 37,$ and $(5,3) \mapsto 13.$

Therefore the congruence has solutions for primes $p \equiv 1,3,9,13,27,31,37,39 \pmod {40}.$

$x^2\equiv 10\mod{p}$ has a solution if $\left(\dfrac{2}{p} \right) = \left(\dfrac{5}{p} \right)$; that is, if the are both $1$ or both $-1$. This will give you a set of pairs of congruences modulo $5$ and $8$; now use the Chinese Remainder Theorem to turn these into congruence classes modulo $5\cdot 8$.

• Do I need to check where all the ordered pairs are sent under the chinese remainder theorem isomorphism? The ordered pairs from these congruences that I can think of are $(1,1),(1,2),(1,3),(1,4),(3,1),(3,2),(3,3),(3,4),(7,1),(7,2),\ldots,(5,4) \in \mathbb{Z}/8\mathbb{Z} \times \mathbb{Z}/5\mathbb{Z}.$ Seems like a lot to check – user167857 May 18 '15 at 20:02
• You only need to check the ones that arise from the two Legendre symbols being equal: $(1,1)$, $(1,4)$, $(7,1)$, $(7,4)$, $(3,2)$, $(3,3)$, $(5,2)$, $(5,3)$. Still a lot, but only half as many as you thought! – rogerl May 18 '15 at 20:04
• Thank you very much roger, I will go try that now. – user167857 May 18 '15 at 20:04
• I found out the primes that satisfy the congruence $\pmod{40}.$ Is my work correct? – user167857 May 18 '15 at 21:14
• Yes, that is correct. – rogerl May 19 '15 at 14:53

Just in case you don't know about Chinese Remainder Theorem:

For example, if $p\equiv 1\pmod 8$ and $p\equiv4\pmod 5$, then you have to look what number meets both congruences, from $1$ to $5\times 8=40$. It is $9$. It is not a prime, but $89$ or $409$ are.

By the way, Dirichlet's theorem implies that there are infinitely many solutions.