The Euler indicatrix: euler phi

6.5.23 The Euler indicatrix: euler phi

The Euler phi function (also called the Euler totient function) finds the number of positive integers less than a given integer and relatively prime. The euler command computes the Euler phi function.

euler takes one argument:
n, a non-negative integer.
euler(n) returns the number of integers larger than 1, less than n and relatively prime to n.

Example.
Input:

euler(21)

Output:

In other words the set of integers less than 21 and coprime with 21, {2,4,5,7,8,10,11,13,15,16,17,19}, has 12 elements.

The little Fermat theorem states:

If p is a prime number, then for any integer a, a^p−1=1 modp.

Euler introduced his phi function to generalize the little Fermat theorem:

If a and n are relatively prime, then a^euler(n)=1 mod n.

Example.
Input:

powmod(5,12,21)

(see section Section 6.34.10)
Output: