Solutions to x^2==22(mod103) in Z103

[clueles]

find the number of solutions in z103

x^2==22(mod103)

 

[shmoe]

Have you seen quadratic reciprocity?

 

[clueles]

no i haven't

 

[Hurkyl]

Legendre symbol?

 

[CRGreathouse]

The Legendre symbol $$\left(\frac{a}{p}\right)$$ is defined as 1 if $$x^2\equiv a\pmod p$$ has solutions, and -1 otherwise. (It's undefined or 0 if $$p\mid a$$.)

Thus for $$x^2\equiv22\pmod{103}$$ you're trying to decide the value of the Legendre symbol $$\left(\frac{22}{103}\right)$$.

Here's the 3-part Law of Quadratic Reciprocity:

$$\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$$

$$\left(\frac{2}{p}\right)=(-1)^{\frac{p^2-1}{8}}$$

$$\left(\frac{a}{p}\right)=(-1)^{\frac{(p-1)(a-1)}{4}}\left(\frac{p}{a}\right)$$

(If you're using a definition that doesn't include 0, you can move the two Legendre symbols to the same side for aesthetics.)