Important: The numtheory package has been deprecated.  Use the superseding command NumberTheory[PseudoPrimitiveRoot] instead.

The function pprimroot(g, n) computes the next primitive root larger than g or, if n does not have primitive roots, computes a number which is not a root of order of any of the factors of $\mathrm{\phi }\left(n\right)$.

Thus (in all cases), find an integer y, such that there is no $x$ for which $x^r=y\mathbf{mod}n$ when r is a divisor of $\mathrm{\phi }\left(n\right)$ greater than 1 and $\mathrm{igcd}\left(y\,n\right)=1$.

If only one argument n is present then this function will return the smallest primitive root of the number n. If there is no primitive root of n then this function will return the smallest integer y, such that there is no $x$ for which $x^r=y\mathbf{mod}n$ when r is a divisor of $\mathrm{\phi }\left(n\right)$ greater than 1 and $\mathrm{igcd}\left(y\,n\right)=1$.

The command with(numtheory,pprimroot) allows the use of the abbreviated form of this command.

$\mathrm{with}\left(\mathrm{numtheory}\right)\:$

$\mathrm{pprimroot}\left(1\,41\right)$

$6$

$\mathrm{pprimroot}\left(2\,8\right)$

$3$

$\mathrm{pprimroot}\left(24\right)$

$5$