Lambda( m )
Lambda
returns the exponent of the group of relatively prime residues
modulo the integer m.
lambda(m) is the smallest positive integer l such that for every a relatively prime to m we have a^l=1 mod m. Fermat's theorem asserts a^{phi(m)}=1 mod m, thus lambda(m) divides phi(m) (see Phi).
Carmichael's theorem states that lambda can be computed as follows lambda(2)=1, lambda(4)=2 and lambda(2^e) = 2^{e-2} if 3 <= e, lambda(p^e) = (p-1) p^{e-1} (= phi(p^e)) if p is an odd prime, and lambda(n m) = Lcm(lambda(n),lambda(m)) if n, m are relatively prime.
Composites for which lambda(m) divides m - 1 are called Carmichaels. If 6k+1, 12k+1 and 18k+1 are primes their product is such a number. It is believed but unproven that there are infinitely many Carmichaels. There are only 1547 Carmichaels below 10^{10} but 455052511 primes.
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) 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
IsPrimitiveRootMod, PrimitiveRootMod).
Lambda
usually spends most of its time factoring m (see
FactorsInt).
gap> Lambda( 10 ); 4 gap> Lambda( 30 ); 4 gap> Lambda( 561 ); 80 # 561 is the smallest Carmichael number
GAP 3.4.4