ForHosting KIT · Math

Quadratic non-residues list mod p

Lists every remainder that is never a square modulo an odd prime: modulo 7 the squares are 1, 2 and 4, so the non-residues are 3, 5 and 6. The count always equals (p − 1)/2, a built-in self-check. Free in your browser.

  • Free
  • Runs in your browser
  • No sign-up
  • Your data stays on your device
Run — free How it works & API
Use it from WebAPIEmailTelegramApp soon

Run — free

Worked example

If you enter
Power (W)
7
You get
Nonresidues
3, 5, 6
Quantity
3
Residue count
3
Expected count
3

A quadratic non-residue modulo an odd prime p is a nonzero residue class a for which the congruence x squared congruent to a modulo p has no integer solution. For every odd prime there are exactly half of the nonzero classes that are residues and half that are non-residues, so listing the non-residues is a complete constructive answer rather than a single yes-or-no test. Students, contest programmers, and cryptography learners often need the full set for tables, Legendre-symbol spot checks, and toy examples before they invoke heavier modular-square-root machinery. This capability accepts a single odd prime p, verifies primality, marks every square class with a deterministic scan, and returns the sorted list of non-residues in one through p minus one together with the theoretical counts.

Quadratic non-residues and why the list is half of 1..p−1

Fix an odd prime p. For each integer a not divisible by p, the polynomial X squared minus a either has two roots or none in the field of integers modulo p. Classes with roots are the nonzero quadratic residues; classes without roots are the quadratic non-residues.

Zero is always a square (zero squared), and textbooks usually treat it separately from the nonzero residue and non-residue partition. Multiplicative structure forces a perfect balance: the map x maps to x squared on the multiplicative group of order p minus one is two-to-one onto a subgroup of index two, so there are exactly (p minus one) over two residues and the same number of non-residues.

Classic small tables confirm the count: modulo seven the nonzero squares are one, two, and four, so the non-residues are three, five, and six; modulo eleven the non-residues are two, six, seven, eight, and ten. The Legendre symbol encodes the same partition as plus one or minus one, but a single symbol does not enumerate the whole set.

Where full non-residue lists show up in real work

Contest programmers use the set as an oracle when building generators that sample non-residues for hash tests or for constructing counterexamples to naive square-root guesses. Cryptography students verify textbook claims about the size of the non-residue set before studying quadratic reciprocity, Euler’s criterion, or Rabin-style ciphers that depend on residue structure. Engineers writing property tests for modular-arithmetic helpers can assert that the complement of their residue finder matches this list for every odd prime up to a modest bound.

If you only need a single Legendre symbol or a yes-or-no check for one a modulo a general modulus, prefer the sibling residue and symbol tools; this landing is dedicated to the complete non-residue list for an odd prime.

What you can do with it

Homework answer keys and tables

Generate the full sorted list of quadratic non-residues modulo a small odd prime for exercises, slides, and grading keys without building a CRT solver.

Contest and property-test oracles

Assert that a local residue finder and this non-residue list form a partition of 1..p-1 for every odd prime in a test range.

Cryptography course examples

Sample non-residues for toy Rabin or quadratic-reciprocity demonstrations where you need concrete classes, not only a Legendre-symbol sign.

FAQ

What is a quadratic non-residue modulo p?

For an odd prime p, an integer a not divisible by p is a quadratic non-residue modulo p when no integer x satisfies x² ≡ a (mod p). This tool returns every such a in 1..p-1, sorted ascending.

Why must p be an odd prime?

The classical nonzero residue / non-residue partition of size (p−1)/2 each is stated for odd primes.

What size of p is supported?

p must be an integer from 3 through 100,000 inclusive and must be an odd prime.

What does it cost?

The browser tool is free and runs locally.

What are the quadratic non-residues modulo 11?

They are 2, 6, 7, 8 and 10. That makes five, exactly half of the ten nonzero remainders, as happens for every odd prime.

Related tools

Quadratic residue checkerMathCipolla modular square rootMathNth power residue checkerMathLegendre symbol (a/p)MathModular nth root calculatorMathPrimitive root calculatorMathCoterminal angle calculatorMathWieferich prime checkerMath

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

POSThttps://api.kit.forhosting.com/numth/quadratic-nonresidues-list

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/quadratic-nonresidues-list \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"p":7}'

Example request

{
  "p": 7
}

Example response

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "numth.quadratic_nonresidues_list",
  "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

Per request$0.002

Published price — no tokens, no invented credits. A failed task is never charged.

Limits

min_p3
max_p100000

Errors

HTTPCodeMeaning
401unauthorizedMissing or invalid API key.
402insufficient_balanceYour balance doesn't cover the task price.
404unknown_typeThat task type doesn't exist.
429rate_limitedToo many requests. Use the webhook instead of polling.

Technical notes

Input contract, limits, and response fields

Send a single integer field p, the odd prime modulus. Example: for p equals seven the nonresidues array is three, five, six and count is three. Empty objects, decimal strings, and values above the documented maximum are rejected with an English message naming the field. Optional aliases prime, modulus, and mod are accepted with the same meaning. The value must lie between three and one hundred thousand inclusive and must actually be an odd prime; even numbers, composites such as nine or fifteen, the prime two, non-integers, and missing input all fail validation with invalid_input and are not charged. On success the payload includes p, nonresidues as the ascending list of every a in one through p minus one that is not a square modulo p, count equal to the length of that list, residue_count equal to the number of nonzero quadratic residues, and expected_count equal to (p minus one) over two. For a correct odd prime, count, residue_count, and expected_count all match that half-count identity, which is a useful self-check when you consume the API from scripts.

Where full non-residue lists show up in real work

Number-theory courses assign problems such as list all quadratic non-residues modulo seventeen or compare residue tables across small primes; a deterministic JSON list removes off-by-one mistakes from handwritten grids. Because the capability is a pure parse engine there is no model drift, no external API key, and no stored state: the same p always yields the same nonresidues array. API pricing is the published base of $0.002 per successful item; failed validation does not consume balance.

Technical questions

How many non-residues are there?

Exactly (p−1)/2. The response fields count and expected_count both report that value; residue_count matches it as well for the nonzero residues.

Read the full KIT documentation →