Quadratic Residues and the Legendre Symbol

If $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)$ and $x^2\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}n)$, then $[x{]}_n^2=[a{]}_n=[b{]}_n$, so $x^2\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)$; reversing the roles of $a$ and $b$ gives the converse.

By [L3], congruent representatives are simultaneously units. If $[x{]}_n^2=[a{]}_n$ and $[a{]}_n$ is a unit with inverse $v$, then $[x{]}_n([x{]}_{n}v)=[x{]}_n^{2}v=[1{]}_n$, so $[x{]}_n$ is a unit. Thus every quadratic-residue class lies in the image of squaring on $(\mathbb{Z}\mathrm{/}n{)}^{\times }$.

Conversely, let $u=[x{]}_n$ be a unit with $u^2=[a{]}_n$. By [L4] there is $v$ with $uv=[1{]}_n$, so $u^2{v}^2=[1{]}_n$ by [L5] and $[a{]}_n=u^2$ is itself a unit; [L3] then gives $\gcd (a,n)=1$, which is the hypothesis [L1] requires. Since $[x{]}_n^2=[a{]}_n$, [L2] gives $x^2\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}n)$, so [L1] makes $a$ a quadratic residue. Hence the quadratic-residue classes are exactly the displayed image.

By [L7], $\gcd (a,p)=1$. Facts [L2] and [L3] specialise [L1] to modulus $p$, while $\gcd (k,p-1)=1$ reduces its test to $a^{p-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$, which holds by [L6]. Thus the root congruence is soluble.

Applying [L4] with $n=p$ and $m=k$ gives exactly $\gcd (p-1,k)=1$ solution class, so the root is unique. It is nonzero because a zero root would give $x^k\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}p)$, contrary to $p\nmid a$.

By [L5], the congruence $k\mathrm{\ell }\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p-1)$ has one solution class and has nonnegative representatives. If $p=2$, every such $a^{\mathrm{\ell }}$ is odd, so it represents the sole unit class and hence the unique root from step 2.1. Suppose $p$ is odd. For a nonnegative representative $\mathrm{\ell }$, the congruence forces $\mathrm{\ell }>0$, so $k\mathrm{\ell }=1+t(p-1)$ with $t\ge 0$; then [L6] gives $(a^{\mathrm{\ell }}{)}^k=a^{1+t(p-1)}\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)$. Two nonnegative representatives differ by a multiple of $p-1$; ordering them and applying [L6] to the nonnegative difference shows that their powers of $a$ represent the same class.

By [L1] and [L3], choose $g\in G$ with $G=⟨g⟩$; then every $u\in G$ is $g^t$ for some $t\in \mathbb{Z}$ by [L2].

If $u=g^t$, then $u^2=g^{2t}$ by [L5], so every square lies in $⟨g^2⟩$; conversely $(g^2{)}^q=(g^q{)}^2$, so every element of $⟨g^2⟩$ is a square. By [L4], the quadratic-residue classes are therefore exactly $⟨g^2⟩$.

Write each exponent as $t=2q+r$ with $r\in \{0,1\}$ by [L6]. Then $g^t$ lies in $⟨g^2⟩$ when $r=0$ and in $g⟨g^2⟩$ when $r=1$. These cosets are distinct: if $g=g^{2q}$, then the order $p-1$ of $g$ would divide the odd integer $2q-1$, impossible because $p-1$ is even. Hence there are exactly two cosets, so the subgroup has index two by [L7].

Let $Q=\{u^2:u\in G\}$ be the subgroup of nonzero square classes, which by [L1] is exactly the set of quadratic-residue classes. By [L1], $[G:Q]=2$ for $G=(\mathbb{Z}\mathrm{/}p{)}^{\times }$, and [L6] gives $\mathrm{\mid }G\mathrm{\mid }=p-1$; hence [L2] gives $\mathrm{\mid }Q\mathrm{\mid }=(p-1)\mathrm{/}2$. Its complement in $G$ has the same cardinality, and since [L1] identifies $Q$ with the quadratic-residue classes, that complement consists exactly of the nonresidues.

If $a$ represents a class in $Q$, then $p\nmid a$, so [L7] gives $\gcd (a,p)=1$. Facts [L4] and [L5] discharge the prime specialisation of [L3], which gives $\gcd (p-1,2)=2$ roots because $p$ is odd.

A nonresidue has no square root by the description of $Q$ in [L1], while step 1.2 gives exactly two roots for each member of $Q$. Together with step 1.1, this proves all assertions.

By [L2], $p\mid (a-b)$, so $p\mid a$ exactly when $p\mid b$. Thus congruent numerators enter the zero branch of [L1] simultaneously.

If $p\nmid a$, then also $p\nmid b$ by step 1.1, and [L3] says that $a$ and $b$ are simultaneously quadratic residues or simultaneously nonresidues. Hence [L1] assigns them the same sign.

The three disjoint branches in [L1] give only the values $-1,0,1$; step 1.1 proves that divisibility gives value zero, and the two unit branches give nonzero values. Therefore the symbol is representative-independent and is zero exactly when $p$ divides its numerator.

By [L2] the quadratic-residue classes are exactly the members of $Q$, so [L7] assigns the value $1$ to every class in $Q$ and, every unit class outside $Q$ being a nonresidue, the value $-1$ to every class in the other coset; [L1] makes this independent of representatives. Thus its value-one set is exactly $Q$, and both values occur.

Choose $h\in G\setminus Q$, which is possible because [L2] gives index two. The two left cosets are $Q$ and $hQ$, so every element outside $Q$ has the form $hq$ with $q\in Q$. The cyclic group $G$ from [L5] is abelian, and $h^2$ is a square, hence belongs to $Q$ by [L2]. It follows that products from $Q\cdot Q$, $Q\cdot hQ$, and $hQ\cdot hQ$ lie respectively in $Q$, $hQ$, and $Q$. The corresponding signs multiply as $1\cdot 1=1$, $1\cdot (-1)=-1$, and $(-1{)}^2=1$. Hence ${\chi }_p(xy)={\chi }_p(x){\chi }_p(y)$, so [L4] makes ${\chi }_p$ a homomorphism; step 1.1 and [L3] give its kernel and surjectivity.

Choose a generator $g$ of $G$ by [L5]. Were $g\in Q$, every power of $g$ would lie in the subgroup $Q$ and so $G=⟨g⟩\subseteq Q$, contradicting the index two of [L2]; hence $g\mathrm{\notin }Q$ and step 1.1 gives ${\chi }_p(g)=-1$, so ${\chi }_p(g^n)=(-1{)}^n$ by [L6]. If a homomorphism $\psi :G\to \{\pm 1\}$ sent $g$ to $1$, then [L6] would make $\psi (g^n)=1$ for every integer $n$, so $\psi$ would be trivial. Every nontrivial $\psi$ therefore sends $g$ to $-1$, and [L6] gives $\psi (g^n)=(-1{)}^n={\chi }_p(g^n)$ for every $n$. Since $g$ generates $G$, $\psi ={\chi }_p$.

If $p\mid a$, then [L1] gives $(a\mathrm{/}p)=0$, while $(p-1)\mathrm{/}2\ge 1$ and hence $a^{(p-1)\mathrm{/}2}\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}p)$. The criterion holds in this case.

Suppose $p\nmid a$. By [L9], $\gcd (a,p)=1$; [L3] and [L4] specialise [L2] with $m=2$ and $d=2$. Thus $a$ is a square modulo $p$ exactly when $a^{(p-1)\mathrm{/}2}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$.

Put $y=[a^{(p-1)\mathrm{/}2}{]}_p$. By [L5], $y^2=[1{]}_p$. Facts [L6] and [L7] make $\mathbb{Z}\mathrm{/}p$ an integral domain, and [L8] says that the degree-two polynomial $X^2-1$ has at most two roots there. The two distinct roots $[1{]}_p$ and $[-1{]}_p$ already exist because $p$ is odd, so $y$ is one of them.

In the unit case, step 1.2 gives $y=[1{]}_p$ exactly for a quadratic residue; otherwise step 1.3 forces $y=[-1{]}_p$. These are precisely the two values prescribed by [L1]. Combining this with step 1.1 proves the congruence for every integer $a$.

If $p$ divides $a$ or $b$, then it divides $ab$. By [L1], the left side is zero and one factor on the right is zero, so the identity holds.

If $p$ divides neither factor, then [L2] makes $[a{]}_p$ and $[b{]}_p$ units. The homomorphism identity in [L3] gives the displayed multiplicativity.

If $p\nmid c$, then $[c{]}_p^2$ lies in the kernel described by [L3], so $(c^2\mathrm{/}p)=1$. Applying the proved multiplicative identity to $a$ and $c^2$ gives $(a{c}^2\mathrm{/}p)=(a\mathrm{/}p)$.

If $p\mid a$, the equation in the field [L2] is $[x{]}_p^2=[0{]}_p$. Since [L3] gives no zero divisors, $[x{]}_p=[0{]}_p$ is the unique solution. This count is $1+0$ by [L1].

Suppose $p\nmid a$. By [L7], $\gcd (a,p)=1$. If $(a\mathrm{/}p)=1$, the congruence is soluble by [L1], and [L4], [L5], and [L6] give exactly $\gcd (p-1,2)=2$ roots. If $(a\mathrm{/}p)=-1$, [L1] says that no root exists.

The three possible symbol values $0,1,-1$ therefore give respectively one, two, and zero solution classes, which in every case equals $1+(a\mathrm{/}p)$.

In the commutative ring [L1], the identity $(2Ax+B{)}^2-\mathrm{\Delta }=4A(A{x}^2+Bx+C)$ holds.

Since $p$ is odd and $p\nmid A$, the prime $p$ divides neither $2A$ nor $4A$, so [L2] makes both classes units. Fact [L3] then says that $x\mapsto 2Ax+B$ is a bijection of the residue classes, and cancellation of the unit $4A$ in step 1.1 shows that the original congruence is equivalent to $(2Ax+B{)}^2\equiv \mathrm{\Delta }(\mathrm{m}\mathrm{o}\mathrm{d}p)$.

The bijection in step 2.1 preserves the number of solutions, and [L4] gives exactly $1+(\mathrm{\Delta }\mathrm{/}p)$ solutions to the square congruence.

For $1\le j\le m$, [L1] gives the standard representative $s_j$ of $aj$. It is nonzero because [L2] permits cancellation of the nonzero classes $[a{]}_p$ and $[j{]}_p$. If $s_j\le m$, set $({\epsilon }_j,r_j)=(1,s_j)$; if $s_j>m$, set $({\epsilon }_j,r_j)=(-1,p-s_j)$. Since $p=2m+1$, this gives the stated unique signed representative with $1\le r_j\le m$.

If $r_j=r_k$, then $aj\equiv ak$ or $aj\equiv -ak(\mathrm{m}\mathrm{o}\mathrm{d}p)$. Cancelling $[a{]}_p$ by [L2] gives $j\equiv k$ or $j\equiv -k(\mathrm{m}\mathrm{o}\mathrm{d}p)$. In the first case $\mathrm{\mid }j-k\mathrm{\mid }<p$ forces $j=k$; in the second, $2\le j+k\le p-1$, so $p\nmid (j+k)$, a contradiction. Thus $j\mapsto r_j$ is injective.