Previous Up Next

7.1.24  Euler indicatrix

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.

Example

euler(21)
     
12           

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

Theorem 2 (Fermat)   If p is a prime number, then for any integer a, ap−1≡ 1 (mod p ).

Euler introduced his phi function to generalize Theorem 2.

Theorem 3 (Euler)   If a and n are relatively prime, then aeuler(n)≡ 1 (mod n ).

Example

powmod(5,12,21)
     
1           

(See Section 11.8.10.)


Previous Up Next