# 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 ```

GAP 3.4.4
April 1997