NumberTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Number Theory : NumberTheory/PrimitiveRoot

NumberTheory

  

PrimitiveRoot

  

primitive root modulo n

 

Calling Sequence

Parameters

Description

Examples

Compatibility

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

withNumberTheory:

PrimitiveRoot4

3

(1)

TotientTotient4

1

(2)

So 3 is the only primitive root modulo 4.

PrimitiveRoot7

3

(3)

TotientTotient7

2

(4)

So there are two primitive roots modulo 7.

PrimitiveRoot7,greaterthan=3

5

(5)

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

seq3imod7,i=1..Totient7,seq5imod7,i=1..Totient7

3,2,6,4,5,1,5,4,6,2,3,1

(6)

Since the maximal order modulo 8 is less than φ8, a primitive root does not exist and an error message is displayed.

seq3nmod8,n=0..2,seq5nmod8,n=0..2,seq7nmod8,n=0..2

1,3,1,1,5,1,1,7,1

(7)

Totient8

4

(8)

PrimitiveRoot8

Error, (in NumberTheory:-PrimitiveRoot) there does not exist a primitive root modulo 8

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

PrimitiveRoot27

2

(9)

seqPrimitiveRoot27,ith=i,i=1..TotientTotient27

2,5,11,14,20,23

(10)

Compatibility

• 

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

• 

For more information on Maple 2016 changes, see Updates in Maple 2016.

See Also

NumberTheory

NumberTheory[MultiplicativeOrder]

NumberTheory[PseudoPrimitiveRoot]