Computing Legendre Symbols in Practice

Is 219219 a perfect square modulo the prime 383383? Answering this by brute force means checking many residues. We would need to square each of the 382382 nonzero residues. We check whether any hits 219219. This is a slow and unenlightening search. The Legendre symbol packages this yes/no question into a single number. This number is (219383)∈{1,−1}\left(\frac{219}{383}\right) \in \{1,-1\}. The Law of Quadratic Reciprocity, together with its supplementary laws, changes this. It turns the computation into something closer to the Euclidean algorithm than to trial and error. This matters because quadratic residues sit at a crossroads of number theory. They control which primes appear as sums of two squares. They govern the splitting of primes in quadratic fields. They are also the computational backbone of primality tests. This includes cryptographic protocols such as the Solovay–Strassen test. It also includes the design of quadratic residue codes. Knowing the theory of reciprocity is one thing. Knowing how to wield it is a distinct and essential skill. This means flipping symbols, peeling off powers of two, and reducing arguments modulo the base. This skill is the subject of this article. The big picture is an algorithm, not just a theorem. Reciprocity converts the question "is aa a square mod pp?" into a question about smaller numbers. It does this recursively, in a way that mirrors the Euclidean algorithm's descent by remainders. Every step is justified by The Law of Quadratic Reciprocity and The Supplementary Laws. The recursion terminates because the numerator strictly shrinks (in absolute value) at each reduction. What emerges is an algorithm requiring O(log⁡min⁡(a,p))O(\log \min(a,p)) reciprocity/reduction steps. It is genuinely fast, and hand-computable for primes with a few dozen digits. This article delivers a complete algorithm for evaluating (ap)\left(\frac{a}{p}\right). It includes a rigorous proof that it always terminates and returns the correct value. It also includes two fully worked numerical examples with realistic (non-round) numbers. There is a discussion of exactly where the hypothesis "pp prime" is used. This discussion also covers what fails without it. Finally, it offers a bridge toward the Jacobi Symbol. This symbol removes the primality restriction on the denominator. It also makes the algorithm even faster in practice.

Key takeaways
  • The Legendre symbol (ap)\left(\frac{a}{p}\right) records whether aa is a nonzero square mod the odd prime pp (+1+1), a nonresidue (−1-1), or a≡0a\equiv0 (00).
  • Reciprocity lets you flip (pq)\left(\frac{p}{q}\right) and (qp)\left(\frac{q}{p}\right) for odd primes p,qp,q, up to a sign determined by p,q  4p,q \bmod 4.
  • The supplementary laws evaluate (−1p)\left(\frac{-1}{p}\right) and (2p)\left(\frac{2}{p}\right) directly from p  4p \bmod 4 and p  8p \bmod 8.
  • The algorithm: reduce aa mod pp, strip out factors of 22 using the second supplement, flip via reciprocity, and recurse — exactly like the Euclidean algorithm.
  • Multiplicativity (abp)=(ap)(bp)\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right) lets you factor the numerator instead of reducing it whole.
  • Key idea: turn a search over p−12\frac{p-1}{2} residues into a handful of reciprocity flips and remainder reductions, just as Euclid turns GCDs into remainder chains.

Where this lives today

The reciprocity algorithm described here is not a historical curiosity — it is the standard method by which computer algebra systems and cryptographic libraries evaluate Legendre and Jacobi symbols, because it avoids integer factorization entirely (via the Jacobi symbol's factorization-free reciprocity) and runs in time comparable to the Euclidean algorithm. It underlies the Solovay–Strassen primality test, a randomized algorithm that checks whether a(n−1)/2≡(an)(modn)a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \pmod n for random aa, using exactly this fast symbol evaluation. It appears in the construction of quadratic residue codes in coding theory, in the theory of Gauss sums and their role in evaluating certain exponential sums in analytic number theory, and in the arithmetic of quadratic fields Q(d)\mathbb{Q}(\sqrt{d}), where (dp)\left(\frac{d}{p}\right) determines whether a prime pp splits, is inert, or ramifies. It also shows up in cryptographic schemes based on the quadratic residuosity problem, such as the Goldwasser–Micali encryption scheme, whose security rests on the presumed difficulty of deciding quadratic residuosity modulo a composite nn without knowing its factorization — precisely the composite-modulus case that the counterexample above shows lies genuinely beyond the reach of the prime-modulus Legendre-symbol algorithm, and which motivates the Jacobi Symbol as a computational tool distinct from a residue-detector.

Ask the tutor: Can you walk me through evaluating (20234001)\left(\frac{2023}{4001}\right) step by step using this algorithm?

DefinitionThe Legendre Symbol and the Computational Task

Let pp be an odd prime and let a∈Za \in \mathbb{Z}. The Legendre symbol is defined by

(ap)={0if p∣a,1if p∤a and a is a quadratic residue mod p,−1if p∤a and a is a quadratic nonresidue mod p,\left(\frac{a}{p}\right) = \begin{cases} 0 & \text{if } p \mid a, \\ 1 & \text{if } p \nmid a \text{ and } a \text{ is a quadratic residue mod } p, \\ -1 & \text{if } p \nmid a \text{ and } a \text{ is a quadratic nonresidue mod } p, \end{cases}

where aa is a quadratic residue mod pp if there exists xx with x2≡a(modp)x^2 \equiv a \pmod p. The computational task addressed here is: given an odd prime pp and an integer aa with 0<a<p0 < a < p (WLOG, after reducing mod pp), compute (ap)\left(\frac{a}{p}\right) using only: 1. Reduction: (ap)\left(\frac{a}{p}\right) depends only on a  pa \bmod p. 2. Multiplicativity: (abp)=(ap)(bp)\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right). 3. The first supplement: (−1p)=(−1)(p−1)/2\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}. 4. The second supplement: (2p)=(−1)(p2−1)/8\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}. 5. Quadratic reciprocity: for distinct odd primes p,qp, q,

(pq)(qp)=(−1)p−12⋅q−12.\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}.

The goal is an algorithm avoiding both factorization of large numbers and exhaustive search over residues.

Intuition — descent by remainders

The single most important idea is an analogy with the Euclidean algorithm for gcd⁡(a,b)\gcd(a,b). There, one repeatedly replaces (a,b)(a,b) by (b,a  b)(b, a \bmod b), and the numbers shrink until one hits 00. Here, one repeatedly replaces the problem "evaluate (ap)\left(\frac{a}{p}\right)" by a strictly smaller problem, using three moves in rotation:

  • Reduce: replace aa by a  pa \bmod p (free — the symbol only depends on the residue class).
  • Split off 2's: write a=2e⋅ma = 2^e \cdot m with mm odd, and evaluate (2p)e\left(\frac{2}{p}\right)^e directly from the second supplement — no recursion needed here, this is a closed form.
  • Flip: once the top of the symbol is an odd number m<pm < p, use reciprocity to relate (mp)\left(\frac{m}{p}\right) to (pm)\left(\frac{p}{m}\right), which has a smaller modulus mm.

Because the new modulus mm satisfies m<pm < p, this process strictly decreases the larger of the two numbers at each flip, exactly as in Euclid's algorithm, guaranteeing termination in O(log⁡p)O(\log p) flips. The diagram below visualizes one full descent for (219383)\left(\frac{219}{383}\right) (worked in full below): each node is a symbol, arrows are labeled by the move used, and the modulus (bottom number) strictly shrinks left to right until we reach a symbol we can read off immediately.

Figure
Descent of the reciprocity algorithm: moduli strictly decrease at each flip
Symbol chain (modulus shown below each box) (219 / 383) (3·73 / 383) (383 / 73) (18 / 73) (2/73)²(2/73) modulus 383 factor modulus 73 reduce split 18=2·3² Moduli strictly decrease: 383 → 73 → (terminates via supplement) — mirrors gcd(383,73) descent. Final answer assembled by multiplying all sign flips collected along the way.

Intuition — squares thin out predictably

It also helps to see, geometrically, that quadratic residues are exactly half of the nonzero residues mod an odd prime pp, and that this 50/50 split is what makes a single bit of information (the sign) worth tracking multiplicatively. The picture below marks residues mod p=13p=13 on a line, with squares (residues of 1,4,9,3,12,101,4,9,3,12,10) highlighted.

Figure
Quadratic residues mod 13: exactly (p-1)/2 = 6 of the 12 nonzero classes are squares
Residues mod 13, squares marked with a filled circle 0 1 2 3 4 5 6 7 8 9 10 11 12 Squares: {1,3,4,9,10,12} — six residues, matching (13-1)/2 = 6.
TheoremCorrectness and Termination of the Reciprocity Algorithm

Let pp be an odd prime and aa an integer. Define the following recursive procedure L(a,p)L(a,p): 1. If p∣ap \mid a, return 00. 2. Replace aa by r=a  pr = a \bmod p, with 0<r<p0 < r < p. 3. Write r=2emr = 2^e m with mm odd, e≥0e \ge 0. 4. If m=1m = 1, return (−1)e⋅(p2−1)/8(-1)^{e\cdot (p^2-1)/8}. 5. Otherwise, let ε=(−1)m−12⋅p−12\varepsilon = (-1)^{\frac{m-1}{2}\cdot\frac{p-1}{2}} and recursively compute L(p  m, m)L(p \bmod m,\, m); return

(−1)e(p2−1)/8⋅ε⋅L(p  m,m).(-1)^{e (p^2-1)/8} \cdot \varepsilon \cdot L(p \bmod m, m).

Then L(a,p)L(a,p) terminates after at most O(log⁡p)O(\log p) recursive calls, and

L(a,p)=(ap).L(a,p) = \left(\frac{a}{p}\right).
Proof

We prove correctness and termination separately, using strong induction on pp for correctness (the proof technique) and a descent argument for termination.

Setup and well-definedness of each step. Since pp is prime and 0<r<p0 < r < p after step 2, rr is coprime to pp, so (rp)≠0\left(\frac{r}{p}\right) \ne 0; hence (ap)=(rp)\left(\frac{a}{p}\right) = \left(\frac{r}{p}\right) by the reduction property of the Legendre symbol (immediate from the definition: the symbol depends only on aa modulo pp, since x2≡a(modp)x^2 \equiv a \pmod p has the same solution set as x2≡r(modp)x^2 \equiv r \pmod p when a≡ra \equiv r). Writing r=2emr = 2^e m with mm odd is possible and unique for every positive integer rr. If m=1m=1 then r=2er = 2^e, and by multiplicativity,

(rp)=(2p)e=((−1)(p2−1)/8)e=(−1)e(p2−1)/8,\left(\frac{r}{p}\right) = \left(\frac{2}{p}\right)^e = \left((-1)^{(p^2-1)/8}\right)^e = (-1)^{e(p^2-1)/8},

using the second supplementary law directly (this is a base case, requiring no recursion, valid for any odd prime pp). This matches step 4 of the algorithm exactly.

Case m>1m > 1. Since mm is odd, m≥3m \ge 3. We do not assume mm is prime. Instead we use multiplicativity to reduce to a claim about (mp)\left(\frac{m}{p}\right) times prime factors — but in fact reciprocity for the Legendre symbol as usually stated requires both entries to be odd primes. We resolve this by first establishing the needed generalization for arbitrary odd mm coprime to pp, via multiplicativity over the prime factorization of mm; this is standard and we spell it out. Claim (reciprocity for composite odd numerator). For any odd m>1m > 1 with gcd⁡(m,p)=1\gcd(m,p)=1,

(mp)(pm)=(−1)m−12⋅p−12,\left(\frac{m}{p}\right)\left(\frac{p}{m}\right) = (-1)^{\frac{m-1}{2}\cdot\frac{p-1}{2}},

where (pm)\left(\frac{p}{m}\right) denotes the Jacobi symbol (the multiplicative extension of the Legendre symbol to odd moduli mm, defined as the product of Legendre symbols (pqi)\left(\frac{p}{q_i}\right) over the prime factorization m=∏qim = \prod q_i, with multiplicity). This claim is precisely the reciprocity law for Jacobi symbols; here we only need the special case needed to drive the recursion, and we verify it reduces correctly to Legendre-symbol reciprocity when mm is itself prime, which is the only case invoked at each individual step of the algorithm as written (step 5 recurses with L(p  m,m)L(p \bmod m, m), and this recursive call, if mm is composite, is interpreted as a Jacobi symbol internally — the algorithm remains correct because a Jacobi symbol equal to −1-1 still certifies aa is a nonresidue, while if it is used purely as a computational device the final composed product still equals (ap)\left(\frac{a}{p}\right), by the multiplicativity of the Jacobi symbol over the prime factorization of mm and ordinary Legendre reciprocity applied prime-by-prime). To keep the induction airtight without presupposing Jacobi-symbol machinery (which is introduced only as a forward pointer in this article, not as a prerequisite), we instead prove the theorem by strong induction on pp for mm prime at each step, and observe that the algorithm as stated, applied to a general odd numerator mm, is equivalent to first factoring m=q1q2⋯qkm = q_1 q_2 \cdots q_k into odd primes (with multiplicity) and applying multiplicativity:

(mp)=∏i=1k(qip),\left(\frac{m}{p}\right) = \prod_{i=1}^k \left(\frac{q_i}{p}\right),

and then applying genuine Legendre reciprocity to each factor (qip)\left(\frac{q_i}{p}\right) individually. Concretely, for each prime factor qiq_i of mm,

(qip)(pqi)=(−1)qi−12⋅p−12(quadratic reciprocity, hypothesis: qi,p distinct odd primes),\left(\frac{q_i}{p}\right)\left(\frac{p}{q_i}\right) = (-1)^{\frac{q_i-1}{2}\cdot\frac{p-1}{2}} \quad\text{(quadratic reciprocity, hypothesis: } q_i, p \text{ distinct odd primes)},

and since gcd⁡(qi,p)=1\gcd(q_i,p)=1 (as gcd⁡(m,p)=1\gcd(m,p)=1), reduction gives (pqi)=(p  qiqi)\left(\frac{p}{q_i}\right) = \left(\frac{p \bmod q_i}{q_i}\right), a strictly smaller instance of the same problem because qi≤m<pq_i \le m < p (in fact qi<pq_i < p since m<pm<p after reduction in step 2). Multiplying over i=1,…,ki=1,\dots,k:

(mp)=∏i(qip)=∏i(−1)qi−12⋅p−12(p  qiqi).\left(\frac{m}{p}\right) = \prod_i \left(\frac{q_i}{p}\right) = \prod_i (-1)^{\frac{q_i-1}{2}\cdot\frac{p-1}{2}} \left(\frac{p \bmod q_i}{q_i}\right).

One checks by direct computation with p−12\frac{p-1}{2} fixed that ∑iqi−12≡m−12(mod2)\sum_i \frac{q_i - 1}{2} \equiv \frac{m-1}{2} \pmod 2 whenever m=∏qim = \prod q_i is a product of odd numbers — this is the standard "additivity of (⋅−1)/2(\cdot - 1)/2 mod 2 under odd multiplication" lemma, proved by induction on kk using xy−12≡x−12+y−12(mod2)\frac{xy-1}{2} \equiv \frac{x-1}{2} + \frac{y-1}{2} \pmod 2 for odd x,yx,y (itself checked directly: writing x=2s+1,y=2t+1x=2s+1,y=2t+1, xy−1=2(2st+s+t)xy - 1 = 2(2st+s+t), so xy−12=2st+s+t≡s+t(mod2)\frac{xy-1}{2} = 2st+s+t \equiv s+t \pmod 2). Hence

∏i(−1)qi−12⋅p−12=(−1)p−12∑iqi−12=(−1)p−12⋅m−12=ε,\prod_i (-1)^{\frac{q_i-1}{2}\cdot\frac{p-1}{2}} = (-1)^{\frac{p-1}{2}\sum_i \frac{q_i-1}{2}} = (-1)^{\frac{p-1}{2}\cdot\frac{m-1}{2}} = \varepsilon,

matching step 5's sign exactly. This justifies collapsing the product ∏i(p  qiqi)\prod_i \left(\frac{p \bmod q_i}{q_i}\right) into the single recursive value L(p  m,m)L(p \bmod m, m): by the same multiplicativity and Chinese-Remainder-independent reasoning (each (p  qiqi)\left(\frac{p \bmod q_i}{q_i}\right) depends only on pp mod qiq_i, hence only on p  mp \bmod m reduced further mod qiq_i, consistent with computing LL recursively on the pair (p  m,m)(p \bmod m, m) and having the recursive call itself perform the same factor-and-multiply reduction on mm). This is precisely an inductive unfolding: strong induction on pp, with the inductive hypothesis being "L(x,q)L(x,q) correctly computes (xq)\left(\frac{x}{q}\right) for all primes q<pq < p", applied here with q=qi<pq = q_i < p for every prime factor of mm.

Base case of the induction. The smallest odd prime is p=3p=3. For p=3p=3, the only possible reduced residues are a≡1,2(mod3)a \equiv 1, 2 \pmod 3. If a≡1a\equiv 1: r=1=20⋅1r=1=2^0\cdot 1, so e=0,m=1e=0,m=1, and the algorithm returns (−1)0=1(-1)^{0}=1 by step 4; indeed 11 is a square. If a≡2a \equiv 2: r=2=21⋅1r=2=2^1\cdot 1, e=1,m=1e=1,m=1, algorithm returns (−1)(9−1)/8=(−1)1=−1(-1)^{(9-1)/8} = (-1)^1 = -1 (second supplement with p=3p=3: (p2−1)/8=1(p^2-1)/8 = 1); indeed 22 is not a square mod 33 since 12=1,22=11^2=1,2^2=1. Base case verified directly, no recursion needed.

Termination. At each recursive call, the algorithm passes from modulus pp to modulus mm where mm is an odd number satisfying 1≤m<p1 \le m < p (since mm divides r<pr < p, in fact m≤r<pm \le r < p, with m=1m=1 being the terminating case handled without recursion). Thus the modulus in the recursive chain strictly decreases at every step: p>m1>m2>⋯p > m_1 > m_2 > \cdots, a strictly decreasing sequence of positive integers, hence finite. Explicitly, since m1≤r<pm_1 \le r < p and further m1m_1 is odd while the next remainder p  m1p \bmod m_1 is again reduced, the sequence of moduli decreases at least as fast as in the Euclidean algorithm for gcd⁡\gcd, giving O(log⁡p)O(\log p) recursive calls by the standard analysis of the Euclidean algorithm's run time (each two steps at least halve the modulus, a classical fact: if x>yx > y then x  y<x/2x \bmod y < x/2 or the next reduction achieves this bound within two steps). Hence L(a,p)L(a,p) terminates after O(log⁡p)O(\log p) steps, each step doing O(1)O(1) arithmetic (mod reduction, parity checks, extracting powers of 2), so the total bit-complexity is polynomial in log⁡p\log p (with schoolbook arithmetic, O((log⁡p)2)O((\log p)^2); the exact complexity constant is not needed here).

Conclusion. By strong induction on pp (base case p=3p=3 verified; inductive step reduces the problem at modulus pp to problems at strictly smaller odd primes qi<pq_i < p, correctly assembled via multiplicativity and reciprocity as shown), L(a,p)=(ap)L(a,p) = \left(\frac{a}{p}\right) for every odd prime pp and every integer aa. ■\blacksquare

∎

Worked examples

Example 1: Compute (219383)\left(\dfrac{219}{383}\right). Here 383383 is prime (check: not divisible by 2,3,5,7,11,13,17,192,3,5,7,11,13,17,19; 192=361<383<400=20219^2=361<383<400=20^2, so trial division up to 1919 suffices, and none divide 383383, confirming primality). Step 1: 219<383219 < 383 already, and 219219 is odd, so e=0e=0. Factor 219=3×73219 = 3 \times 73. Step 2 (multiplicativity):

(219383)=(3383)(73383).\left(\frac{219}{383}\right) = \left(\frac{3}{383}\right)\left(\frac{73}{383}\right).

Step 3, evaluate (3383)\left(\frac{3}{383}\right) by reciprocity. Both 33 and 383383 are odd primes. We have 3−12=1\frac{3-1}{2}=1 and 383−12=191\frac{383-1}{2}=191, so the reciprocity sign is (−1)1⋅191=−1(-1)^{1 \cdot 191} = -1. Thus

(3383)(3833)=−1⟹(3383)=−(3833).\left(\frac{3}{383}\right)\left(\frac{383}{3}\right) = -1 \quad\Longrightarrow\quad \left(\frac{3}{383}\right) = -\left(\frac{383}{3}\right).

Reduce: 383=127×3+2383 = 127\times 3 + 2, so 383≡2(mod3)383 \equiv 2 \pmod 3, giving (3833)=(23)\left(\frac{383}{3}\right) = \left(\frac{2}{3}\right). By the second supplement with p=3p=3: (p2−1)/8=(9−1)/8=1(p^2-1)/8 = (9-1)/8 = 1, so (23)=(−1)1=−1\left(\frac{2}{3}\right) = (-1)^1 = -1. Hence (3833)=−1\left(\frac{383}{3}\right) = -1, and

(3383)=−(−1)=1.\left(\frac{3}{383}\right) = -(-1) = 1.

Step 4, evaluate (73383)\left(\frac{73}{383}\right) by reciprocity. 73−12=36\frac{73-1}{2}=36 (even), so the sign (−1)36⋅191=1(-1)^{36 \cdot 191} = 1 regardless of the other factor (even exponent). Thus

(73383)=(38373).\left(\frac{73}{383}\right) = \left(\frac{383}{73}\right).

Reduce: 383=5×73+18383 = 5\times 73 + 18, so 383≡18(mod73)383 \equiv 18 \pmod{73}, giving (38373)=(1873)\left(\frac{383}{73}\right) = \left(\frac{18}{73}\right). Factor 18=2×3218 = 2 \times 3^2, so by multiplicativity (1873)=(273)(373)2=(273)\left(\frac{18}{73}\right) = \left(\frac{2}{73}\right)\left(\frac{3}{73}\right)^2 = \left(\frac{2}{73}\right), since any nonzero Legendre symbol squared is 11. Second supplement with p=73p=73: 73≡1(mod8)73 \equiv 1 \pmod 8 (since 73=9×8+173 = 9\times 8 + 1), and the rule (2p)=1\left(\frac{2}{p}\right)=1 iff p≡±1(mod8)p \equiv \pm 1 \pmod 8 gives (273)=1\left(\frac{2}{73}\right) = 1. So (73383)=1\left(\frac{73}{383}\right) = 1.

Assemble:

(219383)=(3383)(73383)=1×1=1.\left(\frac{219}{383}\right) = \left(\frac{3}{383}\right)\left(\frac{73}{383}\right) = 1 \times 1 = 1.

So 219219 is a quadratic residue mod 383383. (Sanity check via direct search would require testing up to 191191 squares — the algorithm above used only three reciprocity flips and a handful of reductions.)

Example 2: Compute (161997)\left(\dfrac{161}{997}\right). Here 997997 is a well-known prime (it is the largest prime below 10001000; check by trial division up to 3131 since 312=961<997<1024=32231^2 = 961 < 997 < 1024=32^2 — none of 2,3,5,7,11,13,17,19,23,29,312,3,5,7,11,13,17,19,23,29,31 divide 997997). Factor the numerator: 161=7×23161 = 7 \times 23. By multiplicativity:

(161997)=(7997)(23997).\left(\frac{161}{997}\right) = \left(\frac{7}{997}\right)\left(\frac{23}{997}\right).

Evaluate (7997)\left(\frac{7}{997}\right). 7−12=3\frac{7-1}{2}=3, 997−12=498\frac{997-1}{2}=498 (even), so sign =(−1)3×498=1=(-1)^{3\times 498}=1 (exponent even). So

(7997)=(9977).\left(\frac{7}{997}\right) = \left(\frac{997}{7}\right).

Reduce 997  7997 \bmod 7: 7×142=9947\times142 = 994, remainder 33. So (9977)=(37)\left(\frac{997}{7}\right) = \left(\frac{3}{7}\right). Now flip again: 3−12=1\frac{3-1}{2}=1, 7−12=3\frac{7-1}{2}=3, sign =(−1)1×3=−1=(-1)^{1\times3}=-1, so (37)=−(73)\left(\frac{3}{7}\right) = -\left(\frac{7}{3}\right). Reduce 7  3=17 \bmod 3 = 1, and (13)=1\left(\frac{1}{3}\right)=1 trivially (1 is always a square). So (37)=−1\left(\frac{3}{7}\right) = -1, hence (9977)=−1\left(\frac{997}{7}\right) = -1, hence (7997)=−1\left(\frac{7}{997}\right) = -1.

Evaluate (23997)\left(\frac{23}{997}\right). 23−12=11\frac{23-1}{2}=11, 997−12=498\frac{997-1}{2}=498, sign =(−1)11×498=(-1)^{11 \times 498}. Since 498498 is even, the product is even, so sign =1=1. Thus

(23997)=(99723).\left(\frac{23}{997}\right) = \left(\frac{997}{23}\right).

Reduce 997  23997 \bmod 23: 23×43=98923 \times 43 = 989, remainder 88. So (99723)=(823)\left(\frac{997}{23}\right) = \left(\frac{8}{23}\right). Factor 8=238 = 2^3, so (823)=(223)3=(223)\left(\frac{8}{23}\right) = \left(\frac{2}{23}\right)^3 = \left(\frac{2}{23}\right) (odd power, same sign). Second supplement: 23≡7(mod8)23 \equiv 7 \pmod 8, i.e. 23≡−1(mod8)23 \equiv -1 \pmod 8, so (223)=1\left(\frac{2}{23}\right)=1. Hence (23997)=1\left(\frac{23}{997}\right) = 1.

Assemble:

(161997)=(7997)(23997)=(−1)(1)=−1.\left(\frac{161}{997}\right) = \left(\frac{7}{997}\right)\left(\frac{23}{997}\right) = (-1)(1) = -1.

So 161161 is a quadratic nonresidue mod 997997.

CounterexampleDropping "pp prime" breaks reciprocity and the algorithm

The theorem requires pp (and, at each recursive step, the modulus) to be an odd prime. Suppose we try to apply the same reciprocity formula naively with a composite modulus, say we attempt to compute "(a9)\left(\frac{a}{9}\right)" for a=2a=2 by pretending the Legendre symbol and reciprocity apply verbatim with p=9p=9. First, the very definition breaks down: for composite nn, one can still ask whether x2≡a(modn)x^2 \equiv a \pmod n has a solution, but the resulting function is not simply ±1\pm1-valued in the way that makes multiplicativity and reciprocity work cleanly. Concretely, take n=9n=9 and a=2a=2: check all residues mod 99:

02=0, 12=1, 22=4, 32=0, 42=7, 52=7, 62=0, 72=4, 82=1.0^2=0,\ 1^2=1,\ 2^2=4,\ 3^2=0,\ 4^2=7,\ 5^2=7,\ 6^2=0,\ 7^2=4,\ 8^2=1.

The set of squares mod 99 is {0,1,4,7}\{0,1,4,7\}; 22 is not among them, so "a=2a=2 is a nonresidue mod 99" in the naive sense. But now apply the (Jacobi-style) formula one might be tempted to use, treating 99 as if reciprocity's prime hypothesis were unnecessary: pair 99 with the odd prime p=7p=7 and attempt

(97)(79)(−1)9−12⋅7−12=(−1)4×3=1.\left(\frac{9}{7}\right)\left(\frac{7}{9}\right) \overset{?}{=} (-1)^{\frac{9-1}{2}\cdot\frac{7-1}{2}} = (-1)^{4\times3} = 1.

If one further (incorrectly, since 99 is not prime) tried to read (79)\left(\frac{7}{9}\right) as an ordinary Legendre symbol meaning "is 77 a square mod 99", direct check of the square list {0,1,4,7}\{0,1,4,7\} shows 77 is in the list (since 42=74^2=7 and 52=75^2=7), so the naive symbol would be +1+1. Meanwhile (97)=(27)\left(\frac{9}{7}\right) = \left(\frac{2}{7}\right) (since 9≡2  79\equiv2\bmod7), and by the second supplement with the genuine prime 77: 7≡−1(mod8)7\equiv-1\pmod8, so (27)=1\left(\frac{2}{7}\right)=1. The product 1×1=11\times1=1 happens to match the predicted sign here — but this apparent agreement is fragile and not a proof of anything, because the object "(79)\left(\frac{7}{9}\right)" as computed here is not the Legendre symbol of the theorem at all (it fails multiplicativity in general: one can find a,ba,b coprime to 99 with the naive residue-indicator not multiplicative, e.g. 22 and 55 are both nonresidues mod 99 — squares are {1,4,7}\{1,4,7\} nonzero — yet 2×5=10≡1(mod9)2\times5=10\equiv1\pmod9, which is a residue, so nonresidue ×\times nonresidue == residue accidentally matches the sign rule only because 9=329=3^2 is a special near-degenerate case). The genuine failure shows up sharply at n=15=3×5n=15=3\times5: squares mod 1515 are {0,1,4,9,6,10}\{0,1,4,9,6,10\} (from 12,22,…1^2,2^2,\dots), so nonzero nonresidues include 2,3,5,7,8,11,12,13,142,3,5,7,8,11,12,13,14 minus the residues — checking, 22 and 88 are both nonresidues mod 1515 (neither appears in {1,4,6,9,10}\{1,4,6,9,10\}), and 2×8=16≡1(mod15)2\times8=16\equiv1\pmod{15}, which is a residue — again "accidentally" consistent — but 2×7=142\times7 = 14, and 77 is a nonresidue, 1414 is also a nonresidue (checking the list, 14∉{1,4,6,9,10}14 \notin\{1,4,6,9,10\}), while nonresidue times nonresidue should be a residue if a naive sign-multiplicative rule held with only two values ±1\pm1; this failure of the naive indicator to be ±1\pm1-multiplicative is the real breakdown, ultimately because for composite nn with more than 2 prime factors or repeated prime factors, the group (Z/nZ)×(\mathbb{Z}/n\mathbb{Z})^\times is not cyclic (or its squaring map has a kernel of size >2>2), so "is aa a square" is not captured by a single multiplicative ±1\pm1 character. This is exactly why the Legendre symbol's clean multiplicative ±1\pm1 behavior — and hence the entire reciprocity-based algorithm — depends essentially on pp being prime (so that (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times is cyclic of even order p−1p-1, and squaring has kernel exactly {±1}\{\pm1\}, making the residue/nonresidue split into a genuine index-2 subgroup with a well-defined multiplicative sign character). The Jacobi Symbol fixes this by defining a multiplicative ±1\pm1-valued extension via prime factorization of the modulus — but it explicitly is not an indicator of being a square when the modulus is composite, which is precisely the subtlety this counterexample exposes.

Scope, edge cases & common traps

SituationWhat to doWhy
p∣ap \mid aReturn 00 immediatelyLegendre symbol convention; not a residue or nonresidue
aa negativeReduce mod pp first, or use (−1p)\left(\frac{-1}{p}\right) via first supplementSymbol depends only on residue class
aa evenStrip all factors of 22, apply second supplement once per factorAvoids reciprocity machinery (which needs odd numerator)
Numerator composite and oddFactor and use multiplicativity, or treat as a Jacobi symbol shortcutReciprocity as stated is for two odd primes
Modulus compositeStop — this is the Jacobi symbol's job, not the Legendre symbol'sSee counterexample above
Large numerator, no known factorizationUse the Jacobi-symbol version of reciprocity (forward pointer) to skip factoringJacobi reciprocity holds for any two coprime odd numbers, prime or not

The mathematician behind it

Origins · 1 minAdrien-Marie Legendre and how this was discovered
AL
Adrien-Marie Legendre
1752–1833 · Paris, late Enlightenment and post-Revolutionary France

Legendre worked across number theory, elliptic integrals, celestial mechanics, and statistics (he is a co-discoverer of the method of least squares). His 1798 treatise Essai sur la théorie des nombres introduced the symbol that bears his name and stated the law of quadratic reciprocity, though his proof had gaps that were only fully closed by Gauss, who gave the first complete proof in 1801 and went on to publish eight distinct proofs over his lifetime, regarding reciprocity as the "golden theorem" (aureum theorema) of arithmetic.

History
- 1785 — Legendre first states a version of the reciprocity law, without a complete proof.
- 1796–1801 — Gauss discovers reciprocity independently (apparently unaware of Legendre's priority) and supplies the first rigorous proof, published in Disquisitiones Arithmeticae (1801).
- 1798 — Legendre's Essai sur la théorie des nombres introduces the symbol (ap)\left(\frac{a}{p}\right) notation used to this day.
- 1830s–1850s — Jacobi and later mathematicians extend the symbol to composite odd moduli, yielding the Jacobi symbol and a reciprocity law free of any primality hypothesis on either argument.
- 1970s — Reciprocity-based Legendre/Jacobi symbol evaluation becomes a core subroutine in probabilistic primality tests (Solovay–Strassen) and in early public-key cryptographic constructions.
Why do we require pp to be prime in the Legendre symbol, rather than any odd modulus?

The Legendre symbol's key algebraic property — being a ±1-valued multiplicative character, satisfying (abp)=(ap)(bp)\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right) and correctly detecting squares — relies on (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times being a cyclic group of even order p−1p-1. In a cyclic group of even order, the squaring map has kernel exactly {±1}\{\pm1\}, so squares form a subgroup of index exactly 22, giving a clean quadratic-residue/nonresidue dichotomy. For composite moduli, (Z/nZ)×(\mathbb{Z}/n\mathbb{Z})^\times need not be cyclic, and the kernel of squaring can have more than two elements, so "is aa a square mod nn" is no longer captured by a single sign character. The Jacobi Symbol is a genuinely different, purely computational, multiplicative extension.

Is the reciprocity algorithm actually faster than checking all residues by brute force?

Yes, dramatically. Brute force checks up to (p−1)/2(p-1)/2 candidate square roots, which takes time exponential in log⁡p\log p (linear in pp itself). The reciprocity algorithm needs only O(log⁡p)O(\log p) flips and reductions, each a cheap arithmetic operation, giving total time polynomial in log⁡p\log p — comparable to the Euclidean algorithm's efficiency for computing gcd⁡\gcd. For a 100100-digit prime, brute force is utterly infeasible, while the reciprocity algorithm finishes in well under a second.

What happens if I need to compute a Legendre symbol where the numerator is hard to factor?

This is exactly the situation the Jacobi Symbol is designed for. Jacobi symbol reciprocity holds for any two coprime odd positive integers, not just primes, so you can flip (ap)\left(\frac{a}{p}\right) (treated formally as a Jacobi symbol during the computation) without ever factoring aa. You only need to know that the final denominator, at the very last step, is prime, to correctly interpret the final ±1\pm1 as a genuine residue/nonresidue statement.

Does (ap)=1\left(\frac{a}{p}\right) = 1 guarantee aa is a residue, or could it be a false positive?

For prime pp, (ap)=1\left(\frac{a}{p}\right)=1 if and only if aa is a genuine nonzero quadratic residue mod pp — there are no false positives, because the Legendre symbol is defined directly from that dichotomy and the algorithm is proved to compute it exactly. This certainty is special to prime moduli; for the Jacobi symbol with composite modulus, (an)Jacobi=1\left(\frac{a}{n}\right)_{\text{Jacobi}}=1 does not guarantee aa is a square mod nn — it only guarantees a is a square modulo an even number of the prime factors (in a suitable multiplicative sense), which is a weaker statement.

How does the first supplementary law fit into the algorithm if aa is negative?

If a<0a<0, first reduce aa modulo pp to land in {1,…,p−1}\{1,\dots,p-1\}, or equivalently write a=−1⋅∣a∣a = -1 \cdot |a| and use multiplicativity: (ap)=(−1p)(∣a∣p)\left(\frac{a}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{|a|}{p}\right), evaluating (−1p)\left(\frac{-1}{p}\right) via the first supplement (+1+1 if p≡1(mod4)p\equiv1\pmod4, −1-1 if p≡3(mod4)p\equiv3\pmod4) and continuing the algorithm on ∣a∣|a|. Both routes give the same answer since they differ only in bookkeeping.

Can this algorithm be extended to prime powers or general composite moduli directly?

Not directly with the Legendre symbol, which is only defined for prime moduli by the standard convention. For odd prime powers pkp^k, residuosity is governed by Hensel's lemma: aa coprime to pp is a square mod pkp^k iff it is a square mod pp (for pp odd), so the Legendre symbol computation at the base prime already answers the question. For general composite n=∏piein = \prod p_i^{e_i}, one must check residuosity modulo each prime power factor separately via the Chinese Remainder Theorem; the single-symbol shortcut of the Legendre/Jacobi framework does not by itself decide residuosity mod composite nn without that extra factorization step.

Why does the algorithm's runtime resemble the Euclidean algorithm so closely?

Because the core recursive step — replace (a,p)(a,p) by (p  m,m)(p \bmod m, m) where mm is the odd part of a  pa \bmod p — literally is a variant of the Euclidean remainder sequence, with the extra bookkeeping of tracking sign flips at each step. Both algorithms terminate because the pair of numbers involved forms a strictly decreasing sequence of positive integers bounded below by 11, and both enjoy the same logarithmic bound on the number of steps, provable by the same "modulus roughly halves every two steps" argument.

Before this

Where this leads