11.2 Phi

Phi( m )

Phi returns the value of the Euler totient function phi(m) for the integer m. phi(m) is defined as the number of positive integers less than or equal to m that are relatively prime to m.

Suppose that m = p_1^{e_1} p_2^{e_2} ... p_k^{e_k}. Then phi(m) is p_1^{e_1-1} (p_1-1) p_2^{e_2-1} (p_2-1) ... p_k^{e_k-1} (p_k-1). It follows that m is a prime if and only if phi(m) = m - 1.

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

Phi usually spends most of its time factoring m (see FactorsInt).

    gap> Phi( 12 );
    4
    gap> Phi( 2^13-1 );
    8190        # which proves that $2^{13}-1$ is a prime
    gap> Phi( 2^15-1 );
    27000 

Previous Up Top Next
Index