Primitive Root - Maple Help

NumberTheory

 PrimitiveRoot
 primitive root modulo n

 Calling Sequence PrimitiveRoot(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 PrimitiveRoot(n) command returns the smallest primitive root modulo n, if it exists.
 • The PrimitiveRoot(n, greaterthan = m) command returns the smallest primitive root modulo n greater than m.
 • The PrimitiveRoot(n, ith = i) command returns the ith smallest primitive root modulo n.
 • If the required primitive root does not exist, then an error message is displayed.
 • The integers that are coprime to n form a group of order Totient(n) under multiplication modulo n. If this group is cyclic, then a generator is called a primitive root modulo n. That is, if p is a primitive root modulo n, then every integer coprime to n is congruent to some power of p modulo n.
 • If a primitive root modulo n exists, then the number of primitive roots is Totient(Totient(n)).

Examples

 > $\mathrm{with}\left(\mathrm{NumberTheory}\right):$
 > $\mathrm{PrimitiveRoot}\left(4\right)$
 ${3}$ (1)
 > $\mathrm{Totient}\left(\mathrm{Totient}\left(4\right)\right)$
 ${1}$ (2)

So $3$ is the only primitive root modulo $4$.

 > $\mathrm{PrimitiveRoot}\left(7\right)$
 ${3}$ (3)
 > $\mathrm{Totient}\left(\mathrm{Totient}\left(7\right)\right)$
 ${2}$ (4)

So there are two primitive roots modulo $7$.

 > $\mathrm{PrimitiveRoot}\left(7,\mathrm{greaterthan}=3\right)$
 ${5}$ (5)

Both $3$ and $5$ are generators for the group of units under multiplication modulo $7$.

 > $\left[\mathrm{seq}\left({3}^{i}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}7,i=1..\mathrm{Totient}\left(7\right)\right)\right],\left[\mathrm{seq}\left({5}^{i}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}7,i=1..\mathrm{Totient}\left(7\right)\right)\right]$
 $\left[{3}{,}{2}{,}{6}{,}{4}{,}{5}{,}{1}\right]{,}\left[{5}{,}{4}{,}{6}{,}{2}{,}{3}{,}{1}\right]$ (6)

Since the maximal order modulo $8$ is less than $\mathrm{\phi }\left(8\right)$, a primitive root does not exist and an error message is displayed.

 > $\left[\mathrm{seq}\left({3}^{n}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}8,n=0..2\right)\right],\left[\mathrm{seq}\left({5}^{n}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}8,n=0..2\right)\right],\left[\mathrm{seq}\left({7}^{n}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}8,n=0..2\right)\right]$
 $\left[{1}{,}{3}{,}{1}\right]{,}\left[{1}{,}{5}{,}{1}\right]{,}\left[{1}{,}{7}{,}{1}\right]$ (7)
 > $\mathrm{Totient}\left(8\right)$
 ${4}$ (8)
 > $\mathrm{PrimitiveRoot}\left(8\right)$

List all the primitive roots modulo $27$, if any exist.

 > $\mathrm{PrimitiveRoot}\left(27\right)$
 ${2}$ (9)
 > $\mathrm{seq}\left(\mathrm{PrimitiveRoot}\left(27,\mathrm{ith}=i\right),i=1..\mathrm{Totient}\left(\mathrm{Totient}\left(27\right)\right)\right)$
 ${2}{,}{5}{,}{11}{,}{14}{,}{20}{,}{23}$ (10)

Compatibility

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