# the law of quadratic reciprocity

Finding the roots of a polynomial over some ring is always an interesting subject in mathematics. To find the number of roots of a polynomial over the complex number field is trivial. To find such a number over the real number field is a bit difficult but still we find various algorithms to solve this problem. For example, the Sturm sequence is usually implemented in most computer algebra systems. Another case is over the finite fields or fields of characteristic $>0$, the problem in this case is more interesting and also more fruitful.

For example, if we want to consider the polynomial $x^2=a$ in the field $\mathbb{F}_p$. Not every value $a$ in this field provides a solution for this polynomial. We call quadratic residu for those $a$ such that the corresponding polynomial has solutions in $\mathbb{F}_p$. Most often we consider the case that $a\neq 0$. And thus we can define the Legendre symbol$(\frac{a}{p})$(of course this symbol is defined for all the integers). Using Fermat’s little theorem, we can easily show that

$(\frac{a}{p})=a^{(p-1)/2}$

Using the homomorphism

$\phi:\mathbb{F}_p\rightarrow\{1,-1\}, x\mapsto x^{(p-1)/2}$

we can conclude that the product of two quadratic residues or two non-quadratic residues is again a quadratic residue, while the product of a quadratic residue and a non-quadratic residue is a non-quadratic residue.

So one question arises: when an integer $a$ will be a quadratic residue modulo $p$? The law of quadratic reciprocity resolves this problem(completely in some sense). The following is the content of the theorem:

Suppose that $p,q$ are two distinct odd primes, then $(\frac{p}{q})(\frac{q}{p})=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$.And for the case of $2$, we have $(\frac{2}{p})=(-1)^{\frac{p^2-1}{2}}$.

Another problem concerning the finite fields is the multiplicative generator of the multiplicative group of this field. One conjecture of Artin says that for an integer $a$ which is neither a square of some other integer nor equal to $-1$, then there are infinitely many primes $p$ such that $a$ is a generator for the group $\mathbb{F}_p^*$.