All primitive roots modulo n

It first determines whether the modulus belongs to one of the families that can have primitive roots, then computes Euler's totient, finds a generator, and derives every other generator from it. The response includes the modulus, totient, number of roots, and full root list. Invalid values below two and moduli without primitive roots produce a clear error instead of an empty or misleading answer. The same deterministic arithmetic supports quick browser checks and reproducible API automation at $0.002 per successful request.

What the complete primitive-root list means

A primitive root modulo n is a residue whose repeated powers generate every invertible residue class modulo n. The important word here is every: a number may be coprime to n and still cycle through only a proper subgroup, so being a unit is necessary but not sufficient. This capability returns all positive representatives between 1 and n minus 1 that have multiplicative order exactly phi(n). For modulus 14, for example, the unit group has six elements and the complete generator set contains two residues. The response reports n, Euler's totient phi, the number of primitive roots, and a numerically sorted primitive_roots array. The count provides a useful consistency check: whenever primitive roots exist, their number is phi(phi(n)). Sorting is part of the stable output contract, not a mathematical claim about preference among generators. The special modulus 2 correctly has the single root 1. A modulus that has no generator for its entire unit group is rejected explicitly; an empty list would wrongly suggest that the calculation merely found nothing rather than that the group is noncyclic.

How existence and each generator are verified

Primitive roots do not exist for every modulus. The classification theorem says that the multiplicative group modulo n is cyclic exactly when n is 2, 4, an odd prime power, or twice an odd prime power. The calculator factors n and checks that structural condition before searching. For an admissible modulus it computes phi(n), factors that group order, and tests candidate units using modular exponentiation. A candidate g has full order phi(n) precisely when g raised to phi(n) divided by q is not congruent to 1 modulo n for every distinct prime divisor q of phi(n). Once one such g is known, every primitive root is a power g to the k where k is coprime to phi(n), and those are all the primitive roots. The implementation enumerates those exponents, computes their residues exactly with integer modular exponentiation, and sorts the result. This route avoids checking the entire power cycle separately for every possible residue. It uses no random witnesses, external tables, network requests, or current time, so identical input always produces byte-for-byte equivalent numerical content.

Using the result in mathematics and software

Complete generator lists are useful when a problem asks for more than the least primitive root. Students can compare the returned residues with hand-built power tables and see why the number of generators equals phi(phi(n)). Teachers can build answer keys that include every valid answer rather than accepting only one chosen generator. Software authors can generate fixtures for multiplicative-order routines, verify enumeration code, or select among several generators according to a separate application rule. The calculator also makes the failure cases instructive: trying modulus 8 or 15 demonstrates that many familiar composite moduli have unit groups that are not cyclic, even though they contain plenty of invertible residues. Input is limited to 10,000 because the requested response is exhaustive and may contain many roots; the bound keeps browser rendering, API payload size, and runtime predictable. Supply n as an integer, or use a plain decimal integer string through clients that preserve textual form. Successful API requests cost $0.002; interactive use can rely on the same pure solver, and validation failures clearly identify unsupported or malformed input.