Euler phi function
For any positive integer n, φ(n) is the number of positive integers less than or equal to n which are coprime to n. The function φ is known as the φ function. This function may also be denoted by ϕ.
Among the most useful of φ are the facts that it is multiplicative (meaning if gcd(a,b)=1, then φ(ab)=φ(a)φ(b)) and that φ(pk)=pk-1(p-1) for any prime p and any positive integer k. These two facts combined give a numeric computation of φ for all positive integers:
φ(n) | =n∏p|n(1-1p). | (1) |
For example,
φ(2000) | =2000∏p|2000(1-1p) | ||
=2000(1-12)(1-15) | |||
=2000(12)(45) | |||
=800010 | |||
=800. |
From equation (1), it is clear that φ(n)≤n for any positive integer n with equality holding exactly when n=1. This is because
∏p|n(1-1p)≤1, |
with equality holding exactly when n=1.
Another important fact about the φ function is that
∑d|nφ(d)=n, |
where the sum extends over all positive divisors of n. Also, by definition, φ(n) is the number of units in the ring ℤ/nℤ of integers modulo n.
The sequence {φ(n)} appears in the OEIS as sequence http://www.research.att.com/ njas/sequences/A000010A000010.
Title | Euler phi function |
---|---|
Canonical name | EulerPhiFunction |
Date of creation | 2013-03-22 11:45:11 |
Last modified on | 2013-03-22 11:45:11 |
Owner | Wkbj79 (1863) |
Last modified by | Wkbj79 (1863) |
Numerical id | 19 |
Author | Wkbj79 (1863) |
Entry type | Definition |
Classification | msc 11A25 |
Classification | msc 11-00 |
Classification | msc 14F35 |
Classification | msc 14H30 |
Classification | msc 20F34 |
Synonym | Euler totient function |
Synonym | Euler φ function |
Synonym | Euler ϕ function |
Related topic | ProofThatEulerPhiIsAMultiplicativeFunction |
Related topic | ValuesOfNForWhichVarphintaun |
Related topic | PrimeResidueClass |
Related topic | EulerPhiAtAProduct |
Related topic | SummatoryFunctionOfArithmeticFunction |