# Finding solutions

1. Apr 10, 2005

### clueles

find the number of solutions in z103

x^2==22(mod103)

2. Apr 10, 2005

### shmoe

3. Apr 10, 2005

### clueles

no i haven't

4. Apr 10, 2005

### Hurkyl

Staff Emeritus
Legendre symbol?

5. Apr 13, 2005

### 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.)