11.3 Lambda

`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
April 1997