1911 Encyclopædia Britannica/Number/Quadratic Residues

31. Quadratic Residues. Law of Reciprocity.—To an odd prime modulus $p$, the numbers $1,4,9,\dots (p-1)^{2}$ are congruent to ${\tfrac {1}{2}}(p-1)$ residues only, because $(p-x)^{2}\equiv x^{2}$. Thus for $p=5$, we have $1,4,9,16\equiv 1,4,4,1$ respectively. There are therefore ${\tfrac {1}{2}}(p-1)$ quadratic residues and ${\tfrac {1}{2}}(p-1)$ quadratic non-residues prime to $p$; and there is a corresponding division of incongruent classes of integers with respect to $p$. The product of two residues or of two non-residues is a residue; that of a residue and a non-residue is a non-residue; and taking any primitive root as base the index of any number is even or odd according as the number is a residue or a non-residue. Gauss writes $a\mathrm {R} p,a\mathrm {N} p$ to denote that $a$ is a residue or non-residue of $p$ respectively.

Given a table of indices, the solution of $x^{2}\equiv a{\pmod {p}}$ when possible, is found from $2\operatorname {ind} \ x\equiv \operatorname {ind} \ a{\pmod {\overline {p-1}}}$, and the result may be written in the form $x\equiv \pm r{\pmod {p}}$. But it is important to discuss the congruence $x^{2}\equiv a$ without assuming that we have a table of indices. It is sufficient to consider the case $x^{2}\equiv q{\pmod {p}}$, where $q$ is a positive prime less than $p$; and the question arises whether the quadratic character of $q$ with respect to $p$ can be deduced from that of $p$ with respect to $q$. The answer is contained in the following theorem, which is called the law of quadratic reciprocity (for real positive odd primes): if $p,q$ are each or one of them of the form $4n+1$, then $p,q$ are each of them a residue, or each a non-residue of the other; but if $p,q$ are each of the form $4n+3$, then according as $p$ is a residue or non-residue of $q$ we have $q$ a non-residue or a residue of $p$.

Legendre introduced a symbol $\left({\frac {m}{q}}\right)$ which denotes $+1$ or $-1$ according as $m\mathrm {R} q$ or $m\mathrm {N} q$ ($q$ being a positive odd prime and $m$ any number prime to $q$); with its help we may express the law of reciprocity in the form

$\left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{{\tfrac {1}{4}}(p-1)(q-1)}$.

This theorem was first stated by Legendre, who only partly proved it; the first complete proof, by induction, was published by Gauss, who also discovered five (or six) other more or less independent proofs of it. Many others have since been invented.

There are two supplementary theorems relating to $-1$ and $2$ respectively, which may be expressed in the form

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

where $p$ is any positive odd prime.

It follows from the definition that and that

$\left({\frac {p_{1}^{\alpha }p_{2}^{\beta }p_{3}^{\gamma }\dots }{q}}\right)=\left({\frac {p_{1}}{q}}\right)^{\alpha }\left({\frac {p_{2}}{q}}\right)^{\beta }\left({\frac {p_{3}}{q}}\right)^{\gamma }\dots$

and that $\left({\frac {m}{q}}\right)=\left({\frac {m'}{q}}\right)$, if $m=m'{\pmod {q}}$. As a simple application of the law of reciprocity, let it be required to find the quadratic character of $11$ with respect to $1907$. We have

$\left({\frac {11}{1907}}\right)=-\left({\frac {1907}{11}}\right)=-\left({\frac {6}{11}}\right)=1$

because $6\mathrm {N} 11$. Hence $11\mathrm {R} 1907$.

Legendre's symbol was extended by Jacobi in the following manner. Let $\mathrm {P}$ be any positive odd number, and let $p,p',p'',\!\!\And \!\!\!\!\mathrm {c} .$ be its (equal or unequal) prime factors, so that $\mathrm {P} =pp'p''\dots$. Then if $\mathrm {Q}$ is any number prime to $\mathrm {P}$, we have a generalized symbol defined by

$\left({\frac {\mathrm {Q} }{\mathrm {P} }}\right)=\left({\frac {\mathrm {Q} }{p}}\right)\left({\frac {\mathrm {Q} }{p'}}\right)\left({\frac {\mathrm {Q} }{p''}}\right)\dots$

This symbol obeys the law that, if $\mathrm {Q}$ is odd and positive,

$\left({\frac {\mathrm {P} }{\mathrm {Q} }}\right)\left({\frac {\mathrm {Q} }{\mathrm {P} }}\right)=(-1)^{{\tfrac {1}{4}}(\mathrm {P} -1)(\mathrm {Q} -1)}$,

with the supplementary laws

$\left({\frac {-1}{\mathrm {P} }}\right)=(-1)^{{\tfrac {1}{2}}(\mathrm {P} -1)}$, $\left({\frac {2}{\mathrm {P} }}\right)=(-1)^{{\tfrac {1}{8}}(\mathrm {P} ^{2}-1)}$.

It is found convenient to add the conventions that

$\left({\frac {\mathrm {Q} }{-\mathrm {P} }}\right)=\left({\frac {\mathrm {Q} }{\mathrm {P} }}\right)$

when $\mathrm {Q}$ and $\mathrm {P}$ are both odd; and that the value of the symbol is $0$ when $\mathrm {P} ,\mathrm {Q}$ are not co-primes.

In order that the congruence $x^{2}\equiv a{\pmod {m}}$ may have a solution it is necessary and sufficient that $a$ be a residue of each distinct prime factor of $m$. If these conditions are all satisfied, and $m=2^{\kappa }p^{\lambda }q^{\mu }\dots$, where $p,q,\!\!\And \!\!\!\!\mathrm {c} .$, are the distinct odd prime factors of $m$, being $t$ in all, the number of incongruent solutions of the given congruence is $2^{t},2^{t+1}{\mbox{ or }}2^{t+2}$, according as $\kappa <2,\kappa =2,{\mbox{ or }}\kappa >2$ respectively. The actual solutions are best found by a process of exhaustion. It should be observed that $\left({\frac {a}{m}}\right)=1$ is a necessary but not a sufficient condition for the possibility of the congruence.