PrimitiveRoot

PrimitiveRoot[n]

gives a primitive root of n.

PrimitiveRoot[n,k]

gives the smallest primitive root of n greater than or equal to k.

Details

  • PrimitiveRoot[n] gives a generator for the multiplicative group of integers modulo n relatively prime to n.
  • PrimitiveRoot[n] returns unevaluated if n is not 2, 4, an odd prime power, or twice an odd prime power.
  • PrimitiveRoot[n,1] computes the smallest primitive root of n.

Examples

open allclose all

Basic Examples  (2)

A primitive root of 9 is 2:

The primitive root generates all integers modulo 9 that are relatively prime to 9:

A primitive root of 10:

The smallest primitive root of 10:

Scope  (3)

Find the smallest primitive root:

Find the primitive root greater than a number:

PrimitiveRoot works on large integers:

PrimitiveRoot automatically threads over lists:

Properties & Relations  (2)

The multiplicative order of a primitive root modulo n is EulerPhi[n]:

For a prime p, there exist EulerPhi[p-1] primitive roots modulo p:

Possible Issues  (1)

PrimitiveRoot is not defined for all integers:

Neat Examples  (1)

Elements relatively prime to 22 are enumerated by the primitive root:

Wolfram Research (2007), PrimitiveRoot, Wolfram Language function, https://reference.wolfram.com/language/ref/PrimitiveRoot.html (updated 2015).

Text

Wolfram Research (2007), PrimitiveRoot, Wolfram Language function, https://reference.wolfram.com/language/ref/PrimitiveRoot.html (updated 2015).

CMS

Wolfram Language. 2007. "PrimitiveRoot." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/PrimitiveRoot.html.

APA

Wolfram Language. (2007). PrimitiveRoot. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/PrimitiveRoot.html

BibTeX

@misc{reference.wolfram_2023_primitiveroot, author="Wolfram Research", title="{PrimitiveRoot}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/PrimitiveRoot.html}", note=[Accessed: 19-March-2024 ]}

BibLaTeX

@online{reference.wolfram_2023_primitiveroot, organization={Wolfram Research}, title={PrimitiveRoot}, year={2015}, url={https://reference.wolfram.com/language/ref/PrimitiveRoot.html}, note=[Accessed: 19-March-2024 ]}