PrimitiveRootList

Every primitive root of $n$ — every generator of $(\mathbb{Z}/n)^\times$ — ascending.

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguagePrimitiveRootList!↗

PrimitiveRootList(n)the generators of the unit group mod $n$, or $\{\}$ when it is not cyclic

SageMathenumeratio_primitive_root_list(n)

Typed signatures

Type	Package	Applies
(integer) -> list<integer>	compute-engine	always
(integer) -> list<integer>	residuesreplaces compute-engine	always

Domain: Modular arithmetic

Details

• $(\mathbb{Z}/n)^\times$ is cyclic exactly for $n = 1, 2, 4, p^k, 2p^k$ with $p$ an odd prime; otherwise there are no primitive roots and the list is empty.
• When there is one generator $g$ there are $\varphi(\varphi(n))$: the powers $g^k$ with $\gcd(k, \varphi(n)) = 1$.
• A candidate $g$ is a generator iff $g^{\varphi(n)/q} \not\equiv 1$ for every prime $q \mid \varphi(n)$, so $\varphi(n)$ has to be factored.
• At most 100 000 roots are listed; past that the call stays unevaluated. PrimitiveRoot gives the least one at any size.

Examples

2 more kept as data, checked against the oracles

Basic #

live ↗

In$\mathrm{PrimitiveRootList}(7)$Out$\bigl\lbrack3, 5\bigr\rbrack$

All generators of $(\mathbb Z/9)^\times$, which is cyclic of order 6

live ↗

In$\mathrm{PrimitiveRootList}(9)$Out$\bigl\lbrack2, 5\bigr\rbrack$

Scope #

$10 = 2 \cdot 5$ is of the form $2p$

live ↗

In$\mathrm{PrimitiveRootList}(10)$Out$\bigl\lbrack3, 7\bigr\rbrack$

an odd prime power: $\varphi(\varphi(25)) = 8$ generators

live ↗

In$\mathrm{PrimitiveRootList}(25)$Out$\bigl\lbrack2, 3, 8, 12, 13, 17, 22, 23\bigr\rbrack$

$n = 4$ is one of the small cyclic cases

live ↗

In$\mathrm{PrimitiveRootList}(4)$Out$\bigl\lbrack3\bigr\rbrack$

threads over a list

live ↗

In$\mathrm{PrimitiveRootList}(\bigl\lbrack9, 11\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack2, 5\bigr\rbrack, \bigl\lbrack2, 6, 7, 8\bigr\rbrack\bigr\rbrack$

$18 = 2 \cdot 3^2$ is of the form $2p^k$

live ↗

In$\mathrm{PrimitiveRootList}(18)$Out$\bigl\lbrack5, 11\bigr\rbrack$

live ↗

In$\mathrm{Length}(\mathrm{PrimitiveRootList}(1\,009))$Out$288$

Properties #

there are $\varphi(\varphi(n))$ of them

live ↗

In$\mathrm{Length}(\mathrm{PrimitiveRootList}(1\,009))=\mathrm{Totient}(\mathrm{Totient}(1\,009))$Out$\mathrm{True}$

the first is PrimitiveRoot

live ↗

In$\mathrm{First}(\mathrm{PrimitiveRootList}(1\,009))=\mathrm{PrimitiveRoot}(1\,009)$Out$\mathrm{True}$

Possible issues #

$(\mathbb{Z}/12)^\times \cong C_2 \times C_2$ is not cyclic either

live ↗

In$\mathrm{PrimitiveRootList}(12)$Out$\bigl\lbrack\bigr\rbrack$

$(\mathbb{Z}/8)^\times \cong C_2 \times C_2$ is not cyclic

live ↗

In$\mathrm{PrimitiveRootList}(8)$Out$\bigl\lbrack\bigr\rbrack$

past 100 000 roots the list is not built, but its length is still $\varphi(\varphi(n))$

live ↗

In$\mathrm{Length}(\mathrm{PrimitiveRootList}(1\,000\,003))$Out$333\,332$

The unit group of $\mathbb Z/1$ is trivial, generated by $0$ ($\equiv 1$)

live ↗

In$\mathrm{PrimitiveRootList}(1)$Out$\bigl\lbrack0\bigr\rbrack$

The smallest modulus with a nonzero root: $(\mathbb Z/2)^\times = \{1\}$

live ↗

In$\mathrm{PrimitiveRootList}(2)$Out$\bigl\lbrack1\bigr\rbrack$

About

Examples	17
Checked against	Wolfram Language 14 agree2 differSageMath 12 agree1 differ1 error
Crosswalk	Wolfram LanguageSageMath

Implementation

mappedwolframpackages/oracle/src/mappings.ts

Sage's primitive_root gives one root only; run.ts's SAGE_PREAMBLE walks the powers coprime to phi(n).

mappedsagepackages/oracle/src/mappings.ts

Sage's primitive_root gives one root only; run.ts's SAGE_PREAMBLE walks the powers coprime to phi(n).

See also: PrimitiveRoot, MultiplicativeOrder, PowerModList