GAP Manual: 11.5. IsPrimitiveRootMod

IsPrimitiveRootMod( r, m )

IsPrimitiveRootMod returns true if the integer r is a primitive root modulo the positive integer m and false otherwise. If r is less than 0 or larger than m it is replaced by its remainder.

The integers relatively prime to m form a group under multiplication modulo m, called the prime residue group. It can be computed with PrimeResidues (see PrimeResidues). phi(m) (see Phi) is the order of this group, lambda(m) (see Lambda) the exponent. If and only if m is 2, 4, an odd prime power p^e, or twice an odd prime power 2 p^e, this group is cyclic. In this case the generators of the group, i.e., elements of order phi(m), are called primitive roots (see also PrimitiveRootMod).

    gap> IsPrimitiveRootMod( 2, 541 );
    true
    gap> IsPrimitiveRootMod( -539, 541 );
    true        # same computation as above
    gap> IsPrimitiveRootMod( 4, 541 );
    false
    gap> ForAny( [1..29], r -> IsPrimitiveRootMod( r, 30 ) );
    false        # there does not exist a primitive root modulo 30