Quadratic Reciprocity

The law of quadratic reciprocity, noticed by Euler and Legendre and proved by Gauss, helps greatly in the computation of the Legendre symbol.

Theorem: Let $p,q$ be distinct odd primes. If $p=q=-1(mod4)$, then $$(\frac{p}{q})=-(\frac{q}{p})$$ otherwise $$(\frac{p}{q})=(\frac{q}{p}).$$ which we can state as $$(\frac{p}{q})(\frac{q}{p})=(-1{)}^{\frac{p-1}{2}\frac{q-1}{2}}$$

Proof: TODO

Example: $$(\frac{31}{103})=-(\frac{103}{31})=-(\frac{10}{31})=-(\frac{2}{31})(\frac{5}{31})=-(-1)(\frac{5}{31})$$ since $2=-5(mod8)$. Next, $$(\frac{5}{31})=-(\frac{31}{5})=-(\frac{1}{5})=-1.$$ Hence $31$ is a quadratic nonresidue modulo $103$.

Note we had to factor a number during this computation, so for large numbers this method is not efficient without a fast factoring algorithm. Of course, to compute the Legendre symbol, we can simply perform a modular exponentiation, but it turns out by extending the Legendre symbol we can salvage the above method.

The Jacobi Symbol

The Jacobi symbol $(\frac{a}{b})$ is defined for all odd positive integers $b$ and all integers $a$. When $b$ is prime, it is equivalent to the Legendre symbol (which is why we reuse the notation). If $b=1$, define $(\frac{a}{1})=1$. Lastly, for other values of $b$, factor $b$ into primes: $b=p_1^{k_1}...p_n^{k_n}$ and define $$(\frac{a}{b})={(\frac{a}{p_1})}^{k_1}...{(\frac{a}{p_n})}^{k_n}$$

Thus for odd positive integers $b,b_1,b_2$ we have $$(\frac{a}{b_1{b}_2})=(\frac{a}{b_1})(\frac{a}{b_2})$$ Other properties of the Legendre symbol carry over. By inducting on the number of primes in the factorization of $b$, one can show: $$(\frac{2}{b})=(-1{)}^{(b-1)/2}$$ $$(\frac{-1}{b})=(-1{)}^{(b^2-1)/8}$$ $$(\frac{a}{b})(\frac{b}{a})=(-1{)}^{\frac{a-1}{2}\frac{b-1}{2}}$$

The last property allows us to compute the Jacobi symbol without factoring.

Example: $$(\frac{31}{103})=-(\frac{103}{31})=-(\frac{-21}{31})=-(\frac{-1}{31})(\frac{21}{31})$$ $$=(\frac{31}{21})=(\frac{-11}{21})=(\frac{-1}{21})(\frac{11}{21})=(\frac{21}{11})=(\frac{-1}{11})=-1.$$ Hence $31$ is a quadratic nonresidue modulo $103$.