Jacobi symbol calculator
The Jacobi symbol (5/13) is −1, which tells you 5 is not a square modulo 13. Enter any integer and any odd positive denominator to get −1, 0 or +1 through quadratic reciprocity, without factoring the denominator first. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- First text
- 5
- N
- 13
- Jacobi
- -1
- Symbol
- -1
The Jacobi symbol (a/n) extends the Legendre symbol from prime moduli to any odd positive integer n. It returns 0 when a and n share a common factor greater than one, and otherwise +1 or −1 according to the product of Legendre symbols over the prime factors of n—without requiring you to factor n first. This Jacobi symbol calculator implements the classic quadratic reciprocity algorithm: strip powers of two from the numerator, apply the supplementary law for (2/n), swap with the reciprocity sign when both sides are 3 mod 4, and reduce.
What the Jacobi symbol (a/n) means
For an odd positive integer n and any integer a, the Jacobi symbol (a/n) is defined multiplicatively from the Legendre symbol. When n is an odd prime p, Jacobi coincides with Legendre: (a/p) is 0 if p divides a, +1 if a is a nonzero quadratic residue modulo p, and −1 if a is a quadratic non-residue modulo p. When n factors as a product of odd primes, (a/n) is the product of the Legendre symbols of a at those primes (with multiplicity).
Consequently (a/n) = 0 precisely when gcd(a, n) is greater than one; if the symbol is −1 then a is not a square mod n; but if the symbol is +1, a may still fail to be a square when n is composite—so Jacobi is a necessary condition for quadratic residuosity, not always a sufficient one.
The value is completely multiplicative in both arguments (with the usual caveats on the domain of n), and the famous laws of quadratic reciprocity give an efficient way to evaluate it: reduce a modulo n into a non-negative residue, peel off factors of two using (2/n) = (−1)^((n²−1)/8), and when both current odd parts are 3 mod 4 flip the running sign on each swap.
That procedure never factors n and finishes in a logarithmic number of arithmetic steps, which is why hand calculations and machine implementations share the same textbook algorithm. Negative numerators are reduced into the standard residue system before the loop, so (−1/n) follows the supplementary law (−1)^((n−1)/2) automatically. This capability rejects even n and n below 1 because the classical Jacobi symbol is not defined for those denominators; the Kronecker symbol extends the notion further but is a different tool with a different search intent.
Limits, performance, and where it fits
The reciprocity algorithm performs a constant amount of modular arithmetic per bit of the inputs, so cost scales with the bit length of n rather than with a trial-division factorization of n. Teachers use it to verify hand calculations of (a/n) before students submit proofs. Developers wire it into property tests for Solovay–Strassen style scaffolding, into puzzle and CTF solvers that need a quick quadratic character, and into pipelines that must not reimplement reciprocity in every language.
What you can do with it
Check homework and contest (a/n) answers
Students and coaches can verify Jacobi symbol calculations from quadratic reciprocity without hand-tracking every sign flip or trusting a calculator that loses integer precision.
Scaffold primality and residuosity tests
Scripts that need a deterministic Jacobi step for Solovay–Strassen demos, Euler-criterion checks, or residue-class assertions can call this instead of shipping their own BigInt loop.
FAQ
What is the Jacobi symbol?
It is an integer-valued function (a/n) for odd positive n that generalizes the Legendre symbol. This calculator returns −1, 0, or +1 as jacobi (and the same value as symbol).
Why must n be odd and at least 1?
The classical Jacobi symbol is defined only for odd positive denominators.
Does (a/n)=1 mean a is a square mod n?
Not always. If the symbol is −1 then a is not a quadratic residue mod n. If it is +1, a may still fail to be a square when n is composite. When n is prime, Jacobi equals Legendre and +1 does mean a nonzero square.
How does the Jacobi symbol calculator work?
It uses quadratic reciprocity over BigInt: reduce a mod n, strip factors of 2 with the (2/n) law, swap with a sign flip when both parts are 3 mod 4, and finish when the remainder chain hits 0.
Is the Jacobi symbol calculator free?
The browser tool is free and runs locally.
Related tools
For developers — API access
Everything on this page is available programmatically. This section is for teams who want to wire it into their own systems; everyone else can just use the tool above.
API endpoint
Prefer to automate it? One authenticated POST creates the task; the result comes back by webhook or a signed link. The same capability also runs here on the web, by email and from Telegram — and soon from our app too.
Call it from your stack
curl -X POST https://api.kit.forhosting.com/numth/jacobi-symbol \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":"5","n":"13"}'const res = await fetch("https://api.kit.forhosting.com/numth/jacobi-symbol", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": "5",
"n": "13"
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/jacobi-symbol",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": "5",
"n": "13"
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/jacobi-symbol", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":"5","n":"13"}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":"5","n":"13"}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/jacobi-symbol", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Example request
{
"a": "5",
"n": "13"
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.jacobi_symbol",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}The API is asynchronous: the call returns a task_id immediately and the result arrives by webhook. Polling is capped at 1 req/s per task.
Pricing
Published price — no tokens, no invented credits. A failed task is never charged.
Limits
max_digits | 2048 |
Errors
| HTTP | Code | Meaning |
|---|---|---|
401 | unauthorized | Missing or invalid API key. |
402 | insufficient_balance | Your balance doesn't cover the task price. |
404 | unknown_type | That task type doesn't exist. |
429 | rate_limited | Too many requests. Use the webhook instead of polling. |
Technical notes
Use it for number-theory homework, contest checks, primality-test scaffolding, and deterministic API steps that need exact (a/n) without floating-point or ad-hoc scripts.
How to call the API and read the result
Send a JSON body with two required fields: a (the numerator) and n (the odd positive denominator). Each may be a decimal integer string or a JSON number; prefer strings when values exceed JavaScript’s safe integer range. Aliases numerator or top for a, and denominator, modulus, or m for n, are accepted so forms and hand-written clients share one contract. On success the response echoes a and n as normalized decimal strings, jacobi as the integer −1, 0, or 1, and symbol as the same value written as a string for clients that prefer text fields. Classic checks: a=5 and n=13 yields jacobi −1; a=2 and n=15 yields +1; a=1001 and n=9907 yields −1; a=0 and n=9 yields 0; a=1 and any odd n yields +1. Failed validation—missing fields, non-integers, fractions, n even, n less than 1, or a value longer than the published digit limit—returns invalid_input and is never charged. Pricing is a flat $0.002 per successful request (unit item with zero marginal unit price).
Limits, performance, and where it fits
This capability caps each of a and n at 2048 decimal digits—large enough for contest problems, classroom crypto demos, and multiprecision homework—yet small enough that pure Worker BigInt stays interactive. If you need the Kronecker symbol for even or zero denominators, a full residue-class lattice library, or constant-time crypto primitives, use a dedicated multiprecision stack; this lightweight parse tool is the shared calculator and API step for exact Jacobi evaluation. Pair it with modular exponentiation or inverse tools when a workflow needs the broader modular toolkit; this endpoint answers only the Jacobi question so the search intent stays clear and the response stays minimal.
Integration use cases
CTF, puzzles, and number-theory pipelines
Challenge authors and solvers who need exact (a/n) for odd n get a stable API and free browser tool with the same core, including clear invalid_input when n is even.