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.
-
euler takes
n, a non-negative integer.
- euler(n) returns the number of integers larger than
1, less than n and relatively prime to n.
Example
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
(See Section 11.8.10.)