Motivation
The Legendre symbol detects squares modulo a prime, but its definition already assumes a prime denominator. The Jacobi symbol extends the arithmetic reciprocity rules to every positive odd denominator. Its definition uses prime factorization, yet reciprocity lets us evaluate it without finding those factors.
That distinction is useful computationally and dangerous conceptually. A Jacobi value one need not certify a square modulo a composite, and a quickly evaluated symbol does not certify that the denominator is prime. We will prove the exact rules, maintain a signed invariant through the algorithm, and identify precisely what its output does establish.
Use the earlier prime quadratic reciprocity and supplements, unique factorization, Euclidean remainders and gcd. No primality or factorization algorithm is hidden in the input requirements. All denominators here are positive and odd; the Kronecker extension to even denominators is outside this chapter.
Definitions
Definition 6.3.1
(A factorization definition without a factorization input)
For odd with prime factorization define
The symbols on the right are Legendre symbols. Set for every integer , including . The Jacobi symbol is exactly when ; otherwise it is or . It depends only on modulo and is multiplicative in the numerator. It is also multiplicative in the odd denominator, without requiring the two denominator factors to be coprime.
The notation is mathematical rather than a rational quotient. At a prime it is the Legendre symbol; at a composite it combines the prime answers with their multiplicities and may lose information.
Concept lensCombinatorial
The symbol as the sign of a permutation
For odd and , multiplication by permutes the residues modulo , and the Jacobi symbol equals the sign of that permutation; this description is stated here without proof. For , the cycles are , , , and . Four cycles of even length give sign , matching . This description needs no factorization either, but it handles all residues, far more work than the Euclidean algorithm.
Theorems
Theorem 6.3.2
(Reciprocity and the two supplements for odd denominators)
For every positive odd ,
For coprime positive odd ,
More generally the rearranged rule
remains valid for all positive odd : when they share a factor, both sides are zero.
Theorem 6.3.3
(A signed Euclidean algorithm evaluates the symbol)
For any integer and positive odd the following algorithm returns . Reduce modulo , initialize , and repeat while :
- Write with odd. If is odd and or , replace by .
- If , replace by .
- Replace by .
At termination return if , and otherwise. The modulus decreases by at least a factor two within every two nonterminal iterations, so there are iterations after the initial reduction. With -bit reduced input and ordinary school arithmetic, bit operations is a valid conservative bound. The cost of reducing an initially longer numerator is additional.
Proof sketch or proof idea
Proof
(Odd-denominator reciprocity from the prime laws)
Residue and product rules. Every prime factor has the Legendre residue and multiplicative properties, so their product does too. A common factor forces at least one zero Legendre factor; absence of a common factor makes every factor a sign. Multiplying odd denominators adds their prime exponents, proving denominator multiplicativity even if their factorizations overlap.
The supplements. For odd ,
an even integer because . So the parity of is the sum of the parities for and . Multiplying the prime -supplements with multiplicity therefore gives . Likewise
is even, because and . Multiplying the prime two-supplements gives . These arguments also handle prime powers, where treating the denominator as squarefree would give incorrect signs.
Reciprocity. Assume and are coprime. Each cross-pair of primes contributes the prime reciprocity sign times, giving total parity
By the odd-product parity identity, the two factors are congruent modulo to and . Thus reciprocity follows. If a prime divides both and , both Jacobi symbols are zero; this gives the rearranged rule needed by the algorithm even before the gcd is known. The product statement keeps its coprimality hypothesis: the product of two zero symbols does not equal the displayed sign.
Proof
(Correctness of the signed Euclidean algorithm)
At every stage the invariant is
where are the original inputs and is odd. Initial reduction preserves it, since the symbol depends only on modulo . Removing multiplies the current symbol by , which is exactly the first sign update. The rearranged reciprocity rule gives with the second sign update, and gives the new pair. These steps preserve the invariant whether or not a common factor exists, and the new denominator is odd.
The current denominator strictly decreases, because after reduction, so the loop terminates with . The symbol is for and for by the empty-product convention. This proves the return rule. The gcd is also preserved: because is odd, and . Thus the final equals , and a zero answer is not a partial sign left over from an unfinished calculation.
Proof X-ray
Where oddness, the zero rule and the invariant are used
The proof never computes the symbol directly; it carries the equation original symbol equals times current symbol and changes only the current pair. Three hypotheses are used at specific points. Oddness of the current denominator is what allows both supplements and reciprocity to be applied at all, and it is also what makes stripping twos harmless for the gcd; the algorithm keeps it by only ever moving the odd part into the denominator. The second sign update uses the rearranged reciprocity rule that is valid when the gcd exceeds one; the coprime product form would require knowing the gcd in advance, which is precisely what the algorithm has not computed. Finally, the two-supplement is read from the current denominator, because the invariant concerns the current symbol.
The argument closes at , where two facts meet: the empty-product convention gives the value one at denominator one, and gcd preservation says the terminal denominator is the original gcd. Without the second fact the returned zero would be unexplained. No prime factor of the input is requested anywhere, which is why a fast evaluation is not a primality or square-root certificate.
Proof
(Iteration and bit-cost bounds)
After reduction, the positive numerator is smaller than the denominator , and so is its odd part , which becomes the next denominator. If , one iteration halves the denominator. Otherwise ; if this is zero the algorithm stops, and if not, the following denominator is its odd part, which is at most . Hence every two iterations halve the denominator, and removing extra factors of two can only decrease it further.
Let the initial reduced denominator have bits. There are iterations. Reading residues modulo or and stripping trailing zero bits use bit work, and school remainder division between numbers of at most bits costs . The total bound follows. This is a conservative proved bound, not a claim of optimal fast arithmetic. For a numerator with many more bits than , its initial modular reduction must be charged separately; a bound in terms of alone would omit part of the input.
Worked examples
Worked example 6.3.4
(A multi-step evaluation with no denominator factorization)
For , the successive reduced pairs are
The even numerator contributes one factor two with denominator , so it does not change the sign. No reciprocity swap has both odd arguments congruent to modulo . At the pair , removing three factors of two changes the sign because . The final odd numerator is , producing the final pair . Therefore the symbol is . The remainder checks include and ; no factorization of was used or asserted.
Worked example 6.3.5
(A common factor is detected by the terminal denominator)
For , the first swap has , so no sign change, and gives . Removing one factor two changes the sign because , leaving odd part . The next remainder is , so the terminal denominator is . The returned value is , agreeing with the common factor .
The intermediate sign was negative, but it is multiplied by the terminal zero symbol. Returning that sign alone would confuse a partial invariant with the answer. The algorithm detects a nontrivial gcd without first factoring either integer.
Worked example 6.3.6
(A Jacobi value one is not a square certificate)
For , the prime factors give and , hence their product is . Yet is not a square modulo , because reduction modulo would require a square congruent to . Equivalently, reciprocity gives .
The lost information is the separate prime signs: two negative answers multiply to a positive one. For an odd square denominator the loss is even more pronounced; every coprime numerator has symbol because every prime exponent is even. Primality tests must compare the symbol with additional modular exponentiation information, rather than treating it as a standalone verdict.
Common mistakes
Counterexample mode
The coprime product version cannot be used with common factors
Taking gives a product of Jacobi symbols equal to zero, whereas the reciprocity sign is minus one, since both numbers are three modulo four. There is no contradiction: that product equality required coprimality. The rearranged algorithmic rule reads zero equals a signed zero and remains valid. The two displayed forms are equivalent only when the symbols are nonzero signs.
Common mistake
(Reading the two-supplement from the original denominator)
The sign for removed factors of two depends on the current denominator modulo . In the factor two is removed at the pair , and gives no sign change. Using instead would flip the sign and return , while the correct value is . Factors of two are removed only from the numerator; the denominator always stays odd.
Common mistake
(Returning the accumulated sign when the terminal denominator exceeds one)
The convention applies only at denominator . If the loop ends at with , the answer is whatever is; in the accumulated sign is but the symbol is .
Quick check
Quick check
(If the algorithm outputs , must the original numerator be modulo ?)
Solution · Answer
No. Output means that the terminal denominator, which equals , exceeds . For , the output is although ; the gcd is .
Quick check
(If the output is and , must have a square root modulo ?)
Solution · Answer
No. , but is not a square modulo , hence not modulo . Two negative prime signs multiply to .
Exercises
Exercise 6.3.7
(Evaluate by the algorithm, accounting for every sign update and residue reduction.)
Foundation
Solution(3)
- 1
Reduce and make the first swap
. Since is odd and , no sign changes, and the next pair is .
- 2
Remove the factor two and swap
and , so the two-supplement is positive. Now , so , and the next pair is .
- 3
Finish the loop
gives and the pair , then . The answer is , consistent with .
Exercise 6.3.8
(Prove that for odd , when and otherwise. Give a coprime nonsquare example modulo .)
CoreProof
Solution(3)
- 1
Write the square denominator by its factorization
If then , so .
- 2
Use that every exponent is even
Key step
If , each Legendre factor is and its even power is . If , some gives a zero factor.
- 3
Exhibit the example
∎The unit squares modulo are . So is coprime to with , but it is not a square modulo .
Exercise 6.3.9
(Verify the two-iteration halving argument when the next odd denominator is larger than half the old denominator . Why does stripping twos not spoil the bound?)
CoreProof
Solution(3)
- 1
Compute the next remainder
.
Because: forces the quotient to be .
- 2
Follow one more iteration
If the algorithm has terminated. Otherwise the following denominator is the odd part of , which is at most .
- 3
Account for the removed twos
∎Stripping twos replaces a number by a divisor of it, so it can only decrease the next denominator. After at most two steps the old size has halved.
Exercise 6.3.10
(Explain how a factorization of the denominator can verify a Jacobi computation, why finding it is not a step of the algorithm, and give one valid and one invalid conclusion from output .)
Synthesis
Solution(3)
- 1
Independent check by factorization
Given , one may multiply the Legendre symbols ; this recomputes the same quantity by the definition.
- 2
Why the algorithm does not need it
Key step
The signed invariant uses only proved reciprocity, the supplements and Euclidean remainders, so the prime factors are never requested.
- 3
Valid and invalid conclusions
Output shows is not a square modulo : a square coprime to would make every Legendre factor . It does not show is prime; for example with composite.
Solutions and related notes
The solutions are attached to the exercises above. This chapter supplies full odd-denominator Jacobi reciprocity and a proved evaluation method. Kronecker symbols, Euler–Jacobi probable-prime testing and advanced bit-complexity algorithms require further arguments.