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 

Previous Up Top Next
Index