0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – user167857 May 18 '15 at 20:02
  • $\begingroup$ 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! $\endgroup$ – rogerl May 18 '15 at 20:04
  • $\begingroup$ Thank you very much roger, I will go try that now. $\endgroup$ – user167857 May 18 '15 at 20:04
  • $\begingroup$ I found out the primes that satisfy the congruence $\pmod{40}.$ Is my work correct? $\endgroup$ – user167857 May 18 '15 at 21:14
  • $\begingroup$ Yes, that is correct. $\endgroup$ – rogerl May 19 '15 at 14:53
1
$\begingroup$

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.

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