GAP Manual: 11.6. PrimitiveRootMod

PrimitiveRootMod( m )
PrimitiveRootMod( m, start )

PrimitiveRootMod returns the smallest primitive root modulo the positive integer m and false if no such primitive root exists. If the optional second integer argument start is given PrimitiveRootMod returns the smallest primitive root that is strictly larger than start.

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 IsPrimitiveRootMod).

    gap> PrimitiveRootMod( 409 );
    21        # largest primitive root for a prime less than 2000
    gap> PrimitiveRootMod( 541, 2 );
    10
    gap> PrimitiveRootMod( 337, 327 );
    false        # 327 is the largest primitive root mod 337
    gap> PrimitiveRootMod( 30 );
    false        # the exists no primitive root modulo 30