Quadratic Reciprocity and the Jacobi Symbol

For each $1\le x\le m$, [L2] gives $qx=p{t}_x+{\rho }_x$ with $0\le {\rho }_x<p$; since $p\nmid qx$, one has $0<{\rho }_x<p$. The positive integers $y$ satisfying $py<qx=p{t}_x+{\rho }_x$ are exactly $1,\dots ,t_x$, so $S_{p,q}={\sum }_{x=1}^m{t}_x$.

In the notation of [L3], ${\rho }_x=u_x$ when ${\epsilon }_x=1$ and ${\rho }_x=p-u_x$ when ${\epsilon }_x=-1$; the negative signs are exactly the residues counted by $N(q,p)$. Summing the equations of step 1.1 and reducing modulo $2$ gives ${\sum }_{x}x\equiv S_{p,q}+{\sum }_x{\rho }_x(\mathrm{m}\mathrm{o}\mathrm{d}2)$, because $p$ and $q$ are odd. Also ${\sum }_x{\rho }_x\equiv {\sum }_x{u}_x+N(q,p)(\mathrm{m}\mathrm{o}\mathrm{d}2)$, while the permutation in [L3] gives ${\sum }_x{u}_x={\sum }_{x}x$. Hence $S_{p,q}\equiv N(q,p)(\mathrm{m}\mathrm{o}\mathrm{d}2)$, and [L1] yields $\left(\frac{q}{p}\right)=(-1{)}^{S_{p,q}}$.

No point $(x,y)\in R$ lies on the diagonal $py=qx$: equality would give $p\mid qx$, so [L2] would give $p\mid q$ or $p\mid x$; distinctness of the primes rules out the first alternative, while $1\le x\le (p-1)\mathrm{/}2<p$ rules out the second. Thus every point of $R$ satisfies exactly one of $py<qx$ and $qx<py$.

The points of $R$ with $py<qx$ are exactly those counted by $S_{p,q}$: the inequality itself forces $y<q\mathrm{/}2$, hence $y\le (q-1)\mathrm{/}2$; after interchanging the coordinates and the primes, the points with $qx<py$ are exactly those counted by $S_{q,p}$. By step 1.1 these two sets partition $R$, whose cardinality is $((p-1)\mathrm{/}2)((q-1)\mathrm{/}2)=(p-1)(q-1)\mathrm{/}4$.

Applying [L1] in both orientations, multiplying, and then using [L2] gives $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1{)}^{S_{q,p}+S_{p,q}}=(-1{)}^{(p-1)(q-1)\mathrm{/}4}$.

The exponent is $((p-1)\mathrm{/}2)((q-1)\mathrm{/}2)$, which is odd exactly when both factors are odd, equivalently when $p\equiv q\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}4)$. Since the Legendre symbols are signs for distinct primes, their product is then $-1$, and in every other case it is $1$, proving the equivalent formulation.

The uniqueness in [L2] fixes the set of prime factors and every exponent in [L1]; changing their order does not change a finite product of integers. Each factor belongs to $\{-1,0,1\}$ by [L3], so their product does too, and at $n=1$ the empty product is $1$.

If $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)$, then $a\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}p)$ for every prime factor $p$ of $n$, so [L3] makes every corresponding factor in [L1] equal. The product is zero exactly when some prime factor $p$ of $n$ divides $a$, which gives $\gcd (a,n)>1$; conversely, if $\gcd (a,n)>1$, [L4] supplies a prime divisor of the gcd, hence a prime factor of $n$ dividing $a$, and [L3] makes that Legendre factor zero.

Apply [L2] to every prime factor in [L1] and regroup the finite product: $\left(\frac{ab}{n}\right)={\prod }_i{\left(\frac{a}{p_i}\right)}^{e_i}{\prod }_i{\left(\frac{b}{p_i}\right)}^{e_i}=\left(\frac{a}{n}\right)\left(\frac{b}{n}\right)$. This remains valid when a Legendre factor is zero.

By [L5], choose finite prime factorisations of $m$ and $n$; concatenating their factor lists gives a prime factorisation of $mn$. Grouping equal primes and using [L3] and [L4], the exponent of each prime in $mn$ is the sum of its exponents in $m$ and $n$. Substituting those sums in [L1] and regrouping gives $\left(\frac{a}{mn}\right)=\left(\frac{a}{m}\right)\left(\frac{a}{n}\right)$. If either denominator is $1$, its factor list is empty and its contribution is $1$.

By [L1], the value $\left(\frac{a}{n}\right)$ depends only on the residue class. By [L3] and [L4], a unit class has $\gcd (a,n)=1$, so [L1] rules out the value zero; hence ${\chi }_n$ is a well-defined function from $(\mathbb{Z}\mathrm{/}n{)}^{\times }$ to $\{\pm 1\}$.

For unit classes $[a{]}_n$ and $[b{]}_n$, [L2] gives ${\chi }_n([a{]}_n[b{]}_n)={\chi }_n([ab{]}_n)={\chi }_n([a{]}_n){\chi }_n([b{]}_n)$, which is the condition in [L5]. Thus ${\chi }_n$ is a group homomorphism, including when $n=1$ and the unit group has one element.

Expand $\left(\frac{-1}{n}\right)$ through [L1], applying [L3] to every prime factor with multiplicity and [L2] to multiply the contributions. For odd $u,v$, the difference $(uv-1)\mathrm{/}2-(u-1)\mathrm{/}2-(v-1)\mathrm{/}2=(u-1)(v-1)\mathrm{/}2$ is even, so iteration through the factor list gives $\left(\frac{-1}{n}\right)=(-1{)}^{(n-1)\mathrm{/}2}$; for the empty factor list $n=1$, both sides are $1$.

Similarly, [L1] and [L4] give the product of the signs $(-1{)}^{(p^2-1)\mathrm{/}8}$ with multiplicity. For odd $u,v$, the difference $((uv{)}^2-1)\mathrm{/}8-(u^2-1)\mathrm{/}8-(v^2-1)\mathrm{/}8=(u^2-1)(v^2-1)\mathrm{/}8$ is even, because each of $u^2-1$ and $v^2-1$ is divisible by $8$. Iterating this identity gives $\left(\frac{2}{n}\right)=(-1{)}^{(n^2-1)\mathrm{/}8}$, again with value $1$ at $n=1$.

By [L5], $m$ and $n$ have finite prime factorisations; grouping equal factors and using [L4], write their canonical forms as $m={\prod }_i{p}_i^{{\alpha }_i}$ and $n={\prod }_j{q}_j^{{\beta }_j}$. Expanding both Jacobi symbols by [L2] and [L3] expresses their product as ${\prod }_{i,j}{\left[\left(\frac{p_i}{q_j}\right)\left(\frac{q_j}{p_i}\right)\right]}^{{\alpha }_i{\beta }_j}$. Coprimality makes every $p_i$ distinct from every $q_j$, so [L1] turns this into $(-1{)}^E$, where $E={\sum }_{i,j}{\alpha }_i{\beta }_j(p_i-1)(q_j-1)\mathrm{/}4$.

For a product of odd integers, repeated use of $(uv-1)\mathrm{/}2\equiv (u-1)\mathrm{/}2+(v-1)\mathrm{/}2(\mathrm{m}\mathrm{o}\mathrm{d}2)$ gives $(m-1)\mathrm{/}2\equiv {\sum }_i{\alpha }_i(p_i-1)\mathrm{/}2$ and $(n-1)\mathrm{/}2\equiv {\sum }_j{\beta }_j(q_j-1)\mathrm{/}2$ modulo $2$. Their product is congruent to $E$, so step 1.1 gives the stated sign. If either integer is $1$, the relevant prime list and cross-product are empty and both sides equal $1$.

Maintain the invariant $\left(\frac{a}{n}\right)=\epsilon \left(\frac{A}{N}\right)$. By [L2] and [L6], replacing $A$ by $r$ preserves the current symbol. If $r=2^{s}b$, then [L3] and [L4] give $\left(\frac{r}{N}\right)=(-1{)}^{s(N^2-1)\mathrm{/}8}\left(\frac{b}{N}\right)$. When $\gcd (b,N)=1$, [L5] gives $\left(\frac{b}{N}\right)=(-1{)}^{(b-1)(N-1)\mathrm{/}4}\left(\frac{N}{b}\right)$; when the gcd exceeds $1$, [L1] makes both Jacobi symbols zero, so the same signed equality remains true. Thus every nonterminal update preserves the invariant.

At a nonterminal update, $0<r<N$ and the new denominator is the positive odd part $b\le r$, so it is strictly smaller than $N$. A strictly decreasing chain of positive integers cannot have more terms than its initial value, so the procedure reaches a terminal state.

If $N=1$, [L1] and the invariant give $\left(\frac{a}{n}\right)=\epsilon$. If $r=0$ while $N>1$, then $N$ divides $A$, so [L1] gives $\left(\frac{A}{N}\right)=0$ and the invariant gives the returned value $0$. These are all terminal states, proving correctness and termination; only division, extraction of powers of $2$, and sign updates were used, not a factorisation of $n$.

By [L2], $[a{]}_n$ is a unit. If $v$ is its inverse, then $[x{]}_n([x{]}_{n}v)=[x{]}_n^{2}v=[a{]}_{n}v=[1{]}_n$, so $[x{]}_n$ is also a unit and lies in the domain of [L1].

Applying [L1] to $[a{]}_n=[x{]}_n^2$ gives $\left(\frac{a}{n}\right)={\chi }_n([a{]}_n)={\chi }_n([x{]}_n{)}^2=1$, since ${\chi }_n([x{]}_n)\in \{\pm 1\}$.

If $a$ were a square modulo $n$, the gcd hypothesis would make it a unit square and [L1] would give $\left(\frac{a}{n}\right)=1$.

This contradicts the given value $\left(\frac{a}{n}\right)=-1$, so $a$ is not a square modulo $n$.

Reducing the given congruence modulo $p$ shows that $p\mid x_k$ would force $p\mid a$, contrary to the hypothesis. If $p\mid 2x_k$, [L2] would give $p\mid 2$ or $p\mid x_k$; both are impossible because $p$ is odd. Hence $p\nmid 2x_k$, and [L3] gives $\gcd (2x_k,p)=1$.

Write $x_k^2-a=c{p}^k$. Every class modulo $p^{k+1}$ reducing to $x_k$ modulo $p^k$ has a unique form $x_k+t{p}^k$ with $t$ modulo $p$, and expansion gives $(x_k+t{p}^k{)}^2-a=p^k(c+2x_{k}t+t^2{p}^k)$. Since $k\ge 1$, the lift is a root modulo $p^{k+1}$ exactly when $2x_{k}t\equiv -c(\mathrm{m}\mathrm{o}\mathrm{d}p)$. By step 1.1 and [L1], this linear congruence has exactly one solution class $t$ modulo $p$.

Any root modulo $p^k$ reduces to a root modulo $p$. Since $p\nmid a$, [L3] makes $(a\mathrm{/}p)$ a sign, and [L2] says that a root exists only when $1+(a\mathrm{/}p)=2$, equivalently when $(a\mathrm{/}p)=1$.

Conversely, if $(a\mathrm{/}p)=1$, [L2] gives exactly two root classes modulo $p$. For $k=1$ these are the required roots. For $k>1$, repeatedly apply [L1] from exponent $1$ through exponent $k-1$ to lift each class uniquely; the two lifted classes remain distinct because their reductions modulo $p$ are distinct.

Every root modulo $p^k$ reduces to one of the two roots modulo $p$, and at every successive exponent [L1] forces it to be the unique lift of that reduction. Thus step 1.2 constructs all roots, so there are exactly two. Together with step 1.1 this proves both directions of the criterion and the count.

Modulo $2$, the unique odd class is $1$ and its square is $1$. Modulo $4$, the odd classes $1$ and $3$ both square to $1$, so an odd target is soluble exactly when it is $1$ modulo $4$, and then both odd classes are roots.

Let $k\ge 3$ and write a unit uniquely as $(-1{)}^{\epsilon }{5}^j$ by [L1]. Squaring sends $(\epsilon ,j)$ to $(0,2j)$, so a unit is a square exactly when $\epsilon =0$ and $j$ is even. Modulo $8$, the four coordinate-parity possibilities give residues $1,5,7,3$, respectively, so this condition is equivalent to $a\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}8)$.

The kernel of the squaring map in the coordinates of [L1] has the two choices for $\epsilon$ and the two solutions of $2j=0$ modulo $2^{k-2}$, hence has four elements. Every nonempty fibre of a group homomorphism is a translate of its kernel, so every soluble target for $k\ge 3$ has exactly four roots. Together with step 1.1, this proves all criteria and counts.