Pseudo Primitive Root - Maple Help

Home : Support : Online Help : Mathematics : Factorization and Solving Equations : Roots : NumberTheory/PseudoPrimitiveRoot

NumberTheory

 PseudoPrimitiveRoot
 pseudo primitive root modulo n

 Calling Sequence PseudoPrimitiveRoot(n, options)

Parameters

 n - positive integer options - (optional) at most one of greaterthan = m or ith = i, where m is a non-negative integer and i is a positive integer

Description

 • The PseudoPrimitiveRoot(n) command returns the smallest pseudo primitive root modulo n, if it exists.
 • The PseudoPrimitiveRoot(n, greaterthan = m) command returns the smallest pseudo primitive root modulo n greater than m.
 • The PseudoPrimitiveRoot(n, ith = i) command returns the ith smallest pseudo primitive root modulo n.
 • If the required pseudo primitive root does not exist, then an error message is displayed.
 • A pseudo primitive root is an integer $y$ such that $y$ and $n$ are coprime, and there does not exist an integer $x$ such that ${x}^{r}=y\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}n$ where $r$ is a divisor of $n$ not equal to $1$.
 • If a primitive root modulo n exists, then the pseudo primitive roots are exactly the primitive roots.

Examples

 > $\mathrm{with}\left(\mathrm{NumberTheory}\right):$
 > $\mathrm{PseudoPrimitiveRoot}\left(7\right)$
 ${3}$ (1)
 > $\mathrm{PseudoPrimitiveRoot}\left(2662,\mathrm{greaterthan}=2342\right)$
 ${2345}$ (2)

There does not exist a primitive root modulo $8$ but there are three pseudo primitive roots modulo $8$.

 > $\mathrm{PrimitiveRoot}\left(8\right)$
 > $\mathrm{seq}\left(\mathrm{PseudoPrimitiveRoot}\left(8,\mathrm{ith}=i\right),i=1..3\right)$
 ${3}{,}{5}{,}{7}$ (3)

An error message is displayed when the desired pseudo primitive root does not exist.

 > $\mathrm{PseudoPrimitiveRoot}\left(8,\mathrm{ith}=4\right)$
 > $\mathrm{PseudoPrimitiveRoot}\left(8,\mathrm{greaterthan}=7\right)$

Compatibility

 • The NumberTheory[PseudoPrimitiveRoot] command was introduced in Maple 2016.