Idempotents modulo n calculator
Modulo 12 there are four residues that stay the same when squared: 0, 1, 4 and 9. Enter any modulus up to one trillion to get the complete sorted list, plus the prime-power factors that explain why there are exactly that many. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- N
- 12
- Idempotents
- 0, 1, 4, 9
- Quantity
- 4
- Prime power factors
- 4, 3
An idempotent modulo n is a residue that does not change when multiplied by itself: x squared is congruent to x modulo n. This calculator returns the complete sorted list from zero through n minus one, not merely a count or a single example. It factors the modulus into pairwise coprime prime powers and uses the Chinese remainder theorem to construct every answer exactly. The response also includes those prime-power factors, making the result easy to inspect, teach, test, or feed into another modular-arithmetic workflow.
What an idempotent residue means
The defining congruence is x² ≡ x (mod n), which is equivalent to saying that n divides x(x − 1). Zero and one always qualify: squaring either residue leaves it unchanged. Composite moduli can have additional solutions because different prime-power parts of n may divide different neighboring factors, x and x − 1.
For example, modulo twelve the complete set is zero, one, four, and nine. Four works because sixteen differs from four by twelve, while nine works because eighty-one differs from nine by seventy-two. The returned idempotents array contains canonical representatives only, so each value lies between zero and n minus one and appears once.
Results are sorted numerically, making comparisons and snapshot tests straightforward. The count field reports the array length. For n equal to one there is one residue class, represented canonically by zero, and it is idempotent.
How the complete list is constructed
First, the algorithm factors n into maximal prime powers. These factors are pairwise coprime and their product is n. Over a prime power, the congruence x² ≡ x has exactly two residue classes: zero and one.
The Chinese remainder theorem then says that choosing zero or one independently for every prime-power factor determines exactly one residue modulo n. If n has k distinct prime factors, the calculator therefore constructs 2^k idempotents. It does not scan every integer from zero to n minus one, which would waste work for a large modulus.
For each prime-power factor q, the solver forms n/q and computes its exact modular inverse modulo q. Those CRT basis terms are combined according to every binary choice pattern, reduced modulo n, converted to canonical numeric residues, and sorted. Integer factorization uses deterministic trial division, while CRT multiplication and inversion use BigInt arithmetic so intermediate products cannot be rounded by floating point.
No network request, clock, random source, or mutable cache participates.
What you can do with it
Teach the Chinese remainder theorem
Show how independent zero-or-one choices on prime-power factors become concrete residues modulo a composite integer.
Explore finite ring structure
List the elements that behave like projections under multiplication in the ring of integers modulo n.
FAQ
Are zero and one always included?
Yes. They are always idempotent; when n is one, both names represent the single canonical residue zero.
How many idempotents are there?
For n greater than one with k distinct prime factors, there are exactly 2^k. The modulus one has one residue class.
Why are prime powers returned?
They show the pairwise-coprime components used by the Chinese remainder theorem and explain the number of solutions.
Does the calculator test every residue?
No. It factors n and constructs the complete set directly with CRT basis terms.
What are the idempotents modulo 12?
They are 0, 1, 4 and 9. For example, 4 squared is 16, which leaves remainder 4 when divided by 12, and 9 squared is 81, which leaves 9. Since 12 has two distinct prime factors, there are four of them.
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/idempotents-mod-n \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"n":12}'const res = await fetch("https://api.kit.forhosting.com/numth/idempotents-mod-n", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"n": 12
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/idempotents-mod-n",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"n": 12
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/idempotents-mod-n", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"n":12}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"n":12}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/idempotents-mod-n", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Example request
{
"n": 12
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.idempotents_mod_n",
"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_n | 1000000000000 |
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
What an idempotent residue means
The prime_power_factors field explains the arithmetic structure used by the solver without exposing repeated primes separately. Thus twelve is represented as four times three, not two times two times three. This output is useful when a lesson, proof, or program needs every solution rather than a yes-or-no test for one candidate.
How the complete list is constructed
The public input is bounded at one trillion to keep factorization latency predictable, and every returned residue remains a safe JSON integer. The same accepted n always produces the same factors, ordering, count, and list in both the browser path and API execution.
Supplying a modulus and using the response
Values above the published one-trillion limit are also rejected instead of starting an unexpectedly expensive factor search. A useful consistency check is that count equals two raised to the number of distinct prime factors; n equal to one is the empty-factor special case and still returns count one. You can verify any listed x independently by checking that the nonnegative remainder of x times x minus x modulo n is zero. Send n as a positive JSON integer or as a plain decimal integer string. The alias modulus is accepted for forms that prefer a descriptive field name. A leading plus sign is allowed in a string, but fractions, exponential notation, hexadecimal prefixes, whitespace, negative numbers, zero, missing values, arrays, and unrelated objects are rejected with invalid_input. On success, read idempotents for the full ascending solution set, count for its size, and prime_power_factors for the pairwise-coprime decomposition.
Integration use cases
Test modular arithmetic code
Generate an exact sorted fixture for checking ring, congruence, or residue-class implementations.
Technical questions
What inputs are rejected?
Missing values, non-integers, values below one, malformed decimal strings, and moduli above the published limit return invalid_input.