WOLFRAM

Wolfram Language & System Documentation Center
Wolfram Language Home Page »

PrimitiveRoot
✖
PrimitiveRoot

✖

gives a primitive root of n.

✖

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)Summary of the most common use cases

A primitive root of 9 is 2:

In[1]:=1
✖
https://wolfram.com/xid/0d6fzaol66-iv0
Out[1]=1

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

In[2]:=2
✖
https://wolfram.com/xid/0d6fzaol66-ijkmdx
Out[2]=2

A primitive root of 10:

In[1]:=1
✖
https://wolfram.com/xid/0d6fzaol66-bq53j8
Out[1]=1

The smallest primitive root of 10:

In[2]:=2
✖
https://wolfram.com/xid/0d6fzaol66-b2dajr
Out[2]=2

Scope  (3)Survey of the scope of standard use cases

Find the smallest primitive root:

In[1]:=1
✖
https://wolfram.com/xid/0d6fzaol66-jdy1nn
Out[1]=1

Find the primitive root greater than a number:

In[7]:=7
✖
https://wolfram.com/xid/0d6fzaol66-pzdpx
Out[7]=7

PrimitiveRoot works on large integers:

In[1]:=1
✖
https://wolfram.com/xid/0d6fzaol66-d29mhr
Out[1]=1

PrimitiveRoot automatically threads over lists:

In[1]:=1
✖
https://wolfram.com/xid/0d6fzaol66-b1evbg
Out[1]=1

Properties & Relations  (2)Properties of the function, and connections to other functions

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

In[1]:=1
✖
https://wolfram.com/xid/0d6fzaol66-vgc023
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0d6fzaol66-1ueaj6
Out[2]=2

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

In[1]:=1
✖
https://wolfram.com/xid/0d6fzaol66-47hl3g
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0d6fzaol66-h7y0pm
Out[2]=2

Possible Issues  (1)Common pitfalls and unexpected behavior

PrimitiveRoot is not defined for all integers:

In[1]:=1
✖
https://wolfram.com/xid/0d6fzaol66-584dca
Out[1]=1

Neat Examples  (1)Surprising or curious use cases

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

In[1]:=1
✖
https://wolfram.com/xid/0d6fzaol66-kxgi8r
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0d6fzaol66-i7r8o0
Out[2]=2
Wolfram Research (2007), PrimitiveRoot, Wolfram Language function, https://reference.wolfram.com/language/ref/PrimitiveRoot.html (updated 2015).
✖
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).

✖
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.

✖
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

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

BibTeX

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

✖
@misc{reference.wolfram_2025_primitiveroot, author="Wolfram Research", title="{PrimitiveRoot}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/PrimitiveRoot.html}", note=[Accessed: 05-June-2025 ]}

BibLaTeX

@online{reference.wolfram_2025_primitiveroot, organization={Wolfram Research}, title={PrimitiveRoot}, year={2015}, url={https://reference.wolfram.com/language/ref/PrimitiveRoot.html}, note=[Accessed: 05-June-2025 ]}

✖
@online{reference.wolfram_2025_primitiveroot, organization={Wolfram Research}, title={PrimitiveRoot}, year={2015}, url={https://reference.wolfram.com/language/ref/PrimitiveRoot.html}, note=[Accessed: 05-June-2025 ]}