Legendre and Jacobi Symbol Calculator

Use this Legendre and Jacobi Symbol Calculator to enter values, adjust options, and review results in a compact responsive workspace.

Results are calculated automatically as you enter data.

Reciprocity transformations
ResultEnter a and an odd modulus.

▼ See explanations and tips below ▼

Related Calculators

What Are Quadratic Residues?

A quadratic residue is a number that can be produced by squaring another number in modular arithmetic. In ordinary arithmetic, \(4\) is a square because \(2^2 = 4\). In modular arithmetic, a number \(r\) is a quadratic residue modulo \(n\) when there is some integer \(x\) such that

$$ x^2 \equiv r \pmod{n} $$

This means that \(x^2\) and \(r\) have the same remainder after division by \(n\).

For example, modulo \(13\),

$$ 6^2 = 36 \equiv 10 \pmod{13} $$

so \(10\) is a quadratic residue modulo \(13\). By contrast, \(5\) is not a square modulo \(13\), so it is a quadratic non-residue modulo \(13\).

The Legendre symbol and Jacobi symbol are compact ways to ask whether a number behaves like a square modulo an odd integer. The Legendre symbol is used when the modulus is an odd prime. The Jacobi symbol extends similar notation to odd composite moduli, but its interpretation is more subtle.

The notation looks like a fraction, such as \(\left(\frac{a}{n}\right)\), but it is not division. It is a symbol whose value is always one of three integers:

$$ -1,\quad 0,\quad 1 $$

Why These Symbols Matter

Quadratic residues appear throughout elementary number theory, modular arithmetic, and cryptography-related mathematics. They help answer questions such as:

  • Is a given congruence of the form \(x^2 \equiv a \pmod{n}\) even possible?
  • Can a number be classified as a square or non-square modulo an odd prime?
  • How can quadratic reciprocity turn a difficult-looking residue question into an easier one?
  • Why does a composite modulus behave differently from a prime modulus?

For students, Legendre and Jacobi symbols are a bridge between basic modular arithmetic and deeper tools such as Euler's criterion and quadratic reciprocity. For anyone studying cryptography-adjacent topics, they are also useful background for modular square roots, primality testing ideas, and quadratic residuosity.

Key Terms to Know

  • Modulus: The number \(n\) used in modular arithmetic. Working modulo \(n\) means comparing remainders after division by \(n\).
  • Residue class: The remainder form of a number modulo \(n\). For example, \(-3 \equiv 10 \pmod{13}\), so \(-3\) and \(10\) are in the same residue class modulo \(13\).
  • Quadratic residue: A residue class that equals \(x^2 \pmod{n}\) for some integer \(x\).
  • Quadratic non-residue: A residue class that is not a square modulo \(n\), usually discussed among values relatively prime to the modulus.
  • Greatest common divisor: \(\gcd(a,n)\) is the largest positive integer dividing both \(a\) and \(n\).
  • Legendre symbol: The symbol \(\left(\frac{a}{p}\right)\) for an odd prime modulus \(p\).
  • Jacobi symbol: The symbol \(\left(\frac{a}{n}\right)\) for an odd positive modulus \(n\), where \(n\) may be composite.
  • Quadratic reciprocity: A theorem that relates \(\left(\frac{p}{q}\right)\) to \(\left(\frac{q}{p}\right)\) for odd primes, and has a corresponding Jacobi-symbol form for odd integers.
  • Euler's criterion: A prime-modulus test connecting the Legendre symbol with modular exponentiation.

How the Legendre Symbol Works

For an odd prime \(p\) and an integer \(a\), the Legendre symbol is defined by

$$ \left(\frac{a}{p}\right)= \begin{cases} 0, & \text{if } p \mid a,\\ 1, & \text{if } a \text{ is a nonzero quadratic residue modulo } p,\\ -1, & \text{if } a \text{ is a quadratic non-residue modulo } p. \end{cases} $$

Because the modulus is prime, the interpretation is direct:

  • \(\left(\frac{a}{p}\right)=1\) means \(x^2 \equiv a \pmod{p}\) has a solution and \(a\) is not divisible by \(p\).
  • \(\left(\frac{a}{p}\right)=-1\) means \(x^2 \equiv a \pmod{p}\) has no solution.
  • \(\left(\frac{a}{p}\right)=0\) means \(a\) is divisible by \(p\).

The value depends only on the residue class of \(a\) modulo \(p\). For example, since \(-3 \equiv 10 \pmod{13}\), the symbols \(\left(\frac{-3}{13}\right)\) and \(\left(\frac{10}{13}\right)\) have the same value.

Euler's criterion gives a useful prime-modulus check. If \(p\) is an odd prime and \(p \nmid a\), then

$$ a^{\frac{p-1}{2}} \equiv \left(\frac{a}{p}\right) \pmod{p} $$

When the Legendre symbol is \(-1\), the modular exponentiation result appears as \(p-1\) modulo \(p\), because \(-1 \equiv p-1 \pmod{p}\).

How the Jacobi Symbol Works

The Jacobi symbol uses the same notation but allows an odd positive composite modulus. If

$$ n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k} $$

is the prime factorization of odd \(n\), then the Jacobi symbol is defined as

$$ \left(\frac{a}{n}\right)= \left(\frac{a}{p_1}\right)^{e_1} \left(\frac{a}{p_2}\right)^{e_2} \cdots \left(\frac{a}{p_k}\right)^{e_k} $$

Each factor on the right is a Legendre symbol. This definition explains why the Jacobi symbol agrees with the Legendre symbol when \(n\) is prime.

The important difference is interpretation. For composite \(n\):

  • \(\left(\frac{a}{n}\right)=-1\) rules out \(a\) as a square residue modulo \(n\).
  • \(\left(\frac{a}{n}\right)=0\) means \(a\) and \(n\) share a factor.
  • \(\left(\frac{a}{n}\right)=1\) means \(a\) passes a necessary test, but it does not guarantee that \(a\) is actually a square modulo \(n\).

That last point is one of the most common mistakes. A Jacobi value of \(1\) is not the same as saying “a square root exists” when the modulus is composite.

How Quadratic Reciprocity Helps Compute the Symbol

Quadratic reciprocity gives rules for turning one symbol into another, often with smaller numbers. For odd positive relatively prime values \(m\) and \(n\), the Jacobi-symbol reciprocity rule can be written as

$$ \left(\frac{m}{n}\right) = (-1)^{\frac{(m-1)(n-1)}{4}} \left(\frac{n}{m}\right) $$

This formula means that swapping the top and bottom of the symbol may or may not change the sign. The sign changes exactly when both odd values are congruent to \(3 \pmod{4}\).

The factor-of-\(2\) rule is also essential:

$$ \left(\frac{2}{n}\right) = (-1)^{\frac{n^2-1}{8}} $$

Equivalently, for odd \(n\):

$$ \left(\frac{2}{n}\right)= \begin{cases} 1, & \text{if } n \equiv 1 \text{ or } 7 \pmod{8},\\ -1, & \text{if } n \equiv 3 \text{ or } 5 \pmod{8}. \end{cases} $$

A reciprocity-based calculation usually follows this pattern:

  1. Reduce the top value \(a\) modulo the odd modulus \(n\).
  2. If the reduced value shares a factor with \(n\), the symbol is \(0\).
  3. Remove factors of \(2\) from the top value and apply the factor-of-\(2\) sign rule.
  4. Swap the top and bottom using quadratic reciprocity.
  5. Reduce again and repeat until the bottom reaches \(1\), or until a common factor forces the value to \(0\).

This is why the computation often resembles the Euclidean algorithm: it repeatedly reduces the numbers while tracking possible sign changes.

Examples of Legendre and Jacobi Symbols in Practice

Example 1: A Quadratic Residue Modulo a Prime

Consider \(a=10\) and \(p=13\). To see whether \(10\) is a square modulo \(13\), square small values:

$$ 1^2 \equiv 1 \pmod{13} $$
$$ 2^2 \equiv 4 \pmod{13} $$
$$ 3^2 \equiv 9 \pmod{13} $$
$$ 4^2 \equiv 3 \pmod{13} $$
$$ 5^2 \equiv 12 \pmod{13} $$
$$ 6^2 \equiv 10 \pmod{13} $$

Since \(6^2 \equiv 10 \pmod{13}\), \(10\) is a quadratic residue modulo \(13\):

$$ \left(\frac{10}{13}\right)=1 $$

Example 2: A Quadratic Non-Residue Modulo a Prime

Using the same prime modulus \(13\), the nonzero square residues are

$$ \{1,3,4,9,10,12\} $$

The value \(5\) is not in this set, so \(5\) is a quadratic non-residue modulo \(13\):

$$ \left(\frac{5}{13}\right)=-1 $$

Euler's criterion gives the same conclusion because

$$ 5^{\frac{13-1}{2}}=5^6 \equiv -1 \pmod{13} $$

A calculator that reports the Euler check as a nonnegative residue would show this as

$$ 12 \pmod{13} $$

because \(12 \equiv -1 \pmod{13}\).

Example 3: A Negative Top Value

Negative values are interpreted through their residue class. For \(a=-3\) and \(n=13\),

$$ -3 \equiv 10 \pmod{13} $$

So

$$ \left(\frac{-3}{13}\right)= \left(\frac{10}{13}\right)=1 $$

The sign of the original input is less important than its reduced value modulo \(n\).

Example 4: A Jacobi Value of 1 That Is Not a Square

Now use the composite modulus \(15\):

$$ 15=3\cdot 5 $$

The Jacobi symbol factors as

$$ \left(\frac{2}{15}\right) = \left(\frac{2}{3}\right) \left(\frac{2}{5}\right) $$

Since \(2\) is a non-residue modulo \(3\) and also a non-residue modulo \(5\),

$$ \left(\frac{2}{15}\right)=(-1)(-1)=1 $$

However, the actual square residues modulo \(15\) are

$$ \{x^2 \bmod 15 : x=0,1,\ldots,14\}=\{0,1,4,6,9,10\} $$

The value \(2\) is not in that set. So even though

$$ \left(\frac{2}{15}\right)=1 $$

there is no solution to

$$ x^2 \equiv 2 \pmod{15} $$

This example shows why a Jacobi value of \(1\) is only a necessary condition for composite moduli.

How to Interpret the Result

The meaning of the result depends on whether the calculation is Legendre or Jacobi.

Symbol value Legendre mode with odd prime modulus Jacobi mode with odd composite modulus
\(1\) \(a \bmod n\) is a nonzero quadratic residue. A square root is possible, but not guaranteed. Check the actual residue list when available.
\(0\) \(a\) is divisible by the prime modulus. \(a\) and \(n\) share a factor, so the symbol is not classifying a coprime residue.
\(-1\) \(a \bmod n\) is a quadratic non-residue. \(a \bmod n\) is not a square residue modulo \(n\).

The reduced value \(a \bmod n\) is the value that matters for residue testing. If the original input is negative or larger than the modulus, the result should be interpreted using the reduced residue class.

The \(\gcd(a,n)\) value is also important. A nontrivial greatest common divisor means the symbol is \(0\). In that case, the result is telling you about a shared factor, not about a clean residue-versus-non-residue classification among units modulo \(n\).

When the modulus is small enough for the residue table, the table gives direct evidence: it lists values of \(x^2 \bmod n\). If \(a \bmod n\) appears in that list, it is an actual square residue for that modulus. If it does not appear, no square root exists for that residue class.

In Legendre mode, the Euler check is a cross-check using modular exponentiation:

$$ a^{\frac{n-1}{2}} \bmod n $$

It is shown only for prime moduli. It is not used as the Jacobi interpretation for composite moduli.

Common Mistakes and Misconceptions

Mistake 1: Treating the symbol as a fraction.
The notation \(\left(\frac{a}{n}\right)\) is not division. It is a number-theory symbol with value \(-1\), \(0\), or \(1\).

Mistake 2: Using Legendre mode with a composite modulus.
The Legendre symbol requires an odd prime modulus. If the modulus is odd but composite, use Jacobi mode or Auto mode.

Mistake 3: Assuming Jacobi value \(1\) proves a square root exists.
For composite \(n\), \(\left(\frac{a}{n}\right)=1\) does not guarantee that \(x^2 \equiv a \pmod{n}\) has a solution.

Mistake 4: Forgetting to reduce \(a\) modulo \(n\).
Values such as \(-3\), \(10\), and \(23\) can represent the same residue class modulo \(13\). The reduced value is what matters.

Mistake 5: Confusing the symbol with a square root.
A symbol value tells whether a residue is a square, is not a square, or shares a factor in the relevant sense. It does not construct a value of \(x\) such that \(x^2 \equiv a \pmod{n}\).

Mistake 6: Expecting the residue wheel for every modulus.
The symbol can still be evaluated for larger supported moduli, but the residue visualization and table are generated only when the modulus is at or below the chosen residue-list limit.

When to Use Legendre and Jacobi Symbols

Use these symbols when you want to:

  • classify whether an integer is a quadratic residue modulo an odd prime;
  • study or practice quadratic reciprocity;
  • compare a symbolic residue test with actual square residues for small moduli;
  • understand why prime and composite moduli behave differently;
  • test a necessary condition for quadratic residuosity modulo an odd composite integer;
  • build intuition for modular arithmetic topics that appear in elementary number theory and cryptography-related courses.

Limitations and Things to Keep in Mind

The Legendre and Jacobi symbols are powerful, but they do not answer every modular-arithmetic question.

The Legendre symbol applies to odd prime moduli. The Jacobi symbol applies to odd positive moduli, including odd composite moduli, but its value must be interpreted with care. In particular, a Jacobi value of \(1\) is not a proof that a modular square root exists.

The calculator accepts \(a\) as a plain integer, optionally prefixed with a minus sign, with up to 256 decimal digits. It does not accept decimals, fractions, infinite values, or scientific notation. The modulus must be odd and must satisfy

$$ 3 \le n \le 1{,}000{,}000{,}000 $$

The residue-list limit must be an integer from \(9\) to \(101\). If \(n\) is larger than the selected limit, the symbol is still evaluated, but the residue wheel and residue table are skipped.

Enter \(a\) as a plain integer, optionally prefixed with a minus sign, with up to 256 digits, and \(n\) as plain decimal digits from \(3\) through \(1{,}000{,}000{,}000\). The symbol algorithm and Euler check use exact integer arithmetic; scientific notation and decimal inputs are not accepted.

The calculator evaluates one pair \((a,n)\) at a time. It does not batch-process many symbols, and it does not compute modular square roots. If you need an actual solution to

$$ x^2 \equiv a \pmod{n} $$

you need a modular square-root method, not only a Legendre or Jacobi symbol.

Prime-versus-composite detection is used to choose the appropriate mode in Auto mode and to enforce Legendre mode. It should not be treated as a substitute for a specialized primality-testing workflow in demanding cryptographic or research settings.

How to Use This Calculator

  1. Enter the top integer \(a\).
  2. Enter an odd modulus \(n\) from \(3\) to \(1{,}000{,}000{,}000\).
  3. Choose Auto, Legendre, or Jacobi mode. Auto uses Legendre mode for odd prime \(n\) and Jacobi mode for odd composite \(n\).
  4. Set the residue-list limit from \(9\) to \(101\). This controls when the residue wheel and actual square-residue table are shown.
  5. Read the main symbol value, the calculation type, \(a \bmod n\), \(\gcd(a,n)\), the modulus type, and the Euler check if it is shown.
  6. For small moduli, compare the symbol value with the residue wheel and residue table.
  7. Review the step-by-step work to see the reductions, factor-of-\(2\) rules, reciprocity swaps, and sign changes.
  8. Use the example buttons to load a residue example, a non-residue example, or a Jacobi example.

Frequently Asked Questions

Is the Jacobi symbol the same as the Legendre symbol?

They agree when the bottom value is an odd prime. The Legendre symbol is defined for an odd prime modulus, while the Jacobi symbol is defined for odd positive moduli that may be composite. The same notation can therefore have a different level of interpretation depending on whether the modulus is prime or composite.

What does a symbol value of 0 mean?

A value of \(0\) means the top value and modulus are not coprime. In practical terms, the reduced \(a\) value shares a factor with \(n\). In Legendre mode, this happens exactly when the prime modulus divides \(a\).

Why does a Jacobi value of 1 not guarantee a square root?

For composite \(n\), the Jacobi symbol multiplies Legendre-symbol information across the prime factors of \(n\). Two non-residue factors can multiply to a Jacobi value of \(1\), even when the original number is not a square modulo the composite modulus. This is why \(\left(\frac{2}{15}\right)=1\), although \(2\) is not a square modulo \(15\).

Why must the modulus be odd?

The standard Legendre symbol uses an odd prime modulus, and the standard Jacobi symbol uses an odd positive modulus. Even moduli require different conventions and related symbols, so they are outside the scope of this calculator.

Does the calculator find modular square roots?

No. It evaluates the Legendre or Jacobi symbol and, for small moduli, lists actual square residues. Finding a value of \(x\) such that \(x^2 \equiv a \pmod{n}\) is a separate modular square-root problem.

Sources and References

Books

  1. Victor Shoup. A Computational Introduction to Number Theory and Algebra. 2nd ed., Cambridge University Press, 2009. Chapter 12, especially §§12.1–12.3 on the Legendre symbol, Jacobi symbol, and computing the Jacobi symbol. Official author version 2.1: https://www.shoup.net/ntb/ntb-v2_1.pdf. Publisher front matter: https://assets.cambridge.org/97805215/16440/frontmatter/9780521516440_frontmatter.pdf.
  1. William Stein. Elementary Number Theory: Primes, Congruences, and Secrets: A Computational Approach. Springer New York, 2009. Chapter 4, especially §4.1 on quadratic residues and the Legendre symbol, §4.2 on Euler's criterion, and Exercise 4.9 on the Jacobi symbol. Official book page and free legal PDF: https://wstein.org/ent/. Springer page: https://link.springer.com/book/10.1007/b13279.

Online and Educational Sources

  1. MIT OpenCourseWare. “Quadratic Residues, Quadratic Reciprocity, Lecture 9 Notes.” 18.781 Theory of Numbers, Spring 2012, accessed June 29, 2026. https://ocw.mit.edu/courses/18-781-theory-of-numbers-spring-2012/resources/mit18781s12lec9/.
  1. Eric W. Weisstein. “Legendre Symbol.” MathWorld—A Wolfram Resource, accessed June 29, 2026. https://mathworld.wolfram.com/LegendreSymbol.html.
  1. Eric W. Weisstein. “Jacobi Symbol.” MathWorld—A Wolfram Resource, accessed June 29, 2026. https://mathworld.wolfram.com/JacobiSymbol.html.
  1. Eric W. Weisstein. “Euler's Criterion.” MathWorld—A Wolfram Resource, accessed June 29, 2026. https://mathworld.wolfram.com/EulersCriterion.html.