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

The function primroot will compute the first primitive root of n that is greater than g, if possible, otherwise it returns FAIL.  The integers that are relatively prime to n form a group of order $\mathrm{\phi }\left(n\right)$ under multiplication mod n. If this group is cyclic then a generator of the group is called a primitive root of n (i.e. the order of primroot (g, n) is $\mathrm{\phi }\left(n\right)$).  If only one argument n is present (in this case $g=0$) then this function will return the smallest primitive root of the number n.

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

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

$\mathrm{primroot}\left(2\right)$

$1$

$\mathrm{primroot}\left(41\right)$

$6$

$\mathrm{primroot}\left(0\,41\right)$

$6$

$\mathrm{primroot}\left(7\,41\right)$

$11$

$\mathrm{order}\left(\,41\right)$

$40$

$\mathrm{\phi }\left(41\right)$

$40$

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

$\mathrm{FAIL}$