Euler’s totient function φ(n)
E54269
Euler’s totient function φ(n) is a fundamental arithmetic function in number theory that counts the positive integers up to n that are relatively prime to n and plays a key role in topics such as modular arithmetic and cryptography.
Observed surface forms (2)
| Surface form | Occurrences |
|---|---|
| Euler’s phi function | 1 |
| OEIS sequence A000010 | 1 |
Statements (53)
| Predicate | Object |
|---|---|
| instanceOf |
arithmetic function
ⓘ
multiplicative function ⓘ number-theoretic function ⓘ |
| alternativeName |
Euler’s totient function φ(n)
ⓘ
surface form:
Euler’s phi function
|
| asymptoticBehavior | φ(n) is typically of size ≈ n · 6/π² ⓘ |
| averageOrder | The average order of φ(n) is 6n/π² ⓘ |
| codomain | nonnegative integers ⓘ |
| computationalComplexity | φ(n) can be computed efficiently if the prime factorization of n is known ⓘ |
| cryptographicRelevance | Computing φ(n) for RSA modulus n = pq reveals the private key exponent ⓘ |
| definition | φ(n) is the number of positive integers ≤ n that are coprime to n ⓘ |
| DirichletConvolution |
φ * 1 = id where id(n) = n
ⓘ
φ = μ * id where μ is the Möbius function ⓘ |
| domain | positive integers ⓘ |
| EulerTheoremStatement | If gcd(a,n) = 1 then a^{φ(n)} ≡ 1 (mod n) ⓘ |
| evennessProperty | φ(n) is even for all n > 2 ⓘ |
| field | number theory ⓘ |
| formula |
If n = p₁^{a₁}…p_k^{a_k} then φ(n) = n ∏_{i=1}^k (1 − 1/p_i)
ⓘ
If n = p₁^{a₁}…p_k^{a_k} then φ(n) = ∏_{i=1}^k p_i^{a_i−1}(p_i − 1) ⓘ |
| groupTheoryInterpretation | φ(n) equals the order of the multiplicative group (ℤ/nℤ)× ⓘ |
| growthProperty |
φ(n) ≤ n − 1 for n > 1
ⓘ
φ(n) ≥ c n / log log n for some positive constant c and sufficiently large n ⓘ |
| minimumOnInterval | For n ≥ 3, φ(n) attains its minimum at prime powers ⓘ |
| namedAfter | Leonhard Euler ⓘ |
| OEIS |
Euler’s totient function φ(n)
self-linksurface differs
ⓘ
surface form:
OEIS sequence A000010
|
| primeFormula | φ(p) = p − 1 for prime p ⓘ |
| primePowerFormula | φ(p^k) = p^k − p^{k−1} for prime p and integer k ≥ 1 ⓘ |
| property |
φ is multiplicative: if gcd(m,n) = 1 then φ(mn) = φ(m)φ(n)
ⓘ
φ is not completely multiplicative ⓘ φ(n) counts integers k with 1 ≤ k ≤ n and gcd(k,n) = 1 ⓘ |
| relatedConcept | reduced residue system modulo n ⓘ |
| relatedFunction |
Carmichael function λ(n)
ⓘ
Jordan’s totient functions ⓘ |
| roleIn |
Carmichael function definition and comparison
ⓘ
Euler’s theorem ⓘ RSA ⓘ
surface form:
RSA cryptosystem
|
| specialValue | φ(2) = 1 is the only odd value for n > 1 ⓘ |
| summatoryIdentity |
∑_{d|n} φ(d) = n
ⓘ
∑_{d|n} φ(n/d) = n ⓘ |
| symbol | φ(n) ⓘ |
| usedIn |
group theory via units modulo n
ⓘ
modular exponentiation algorithms ⓘ primitive root theory ⓘ public-key cryptography ⓘ |
| valueAt |
φ(1) = 1
ⓘ
φ(10) = 4 ⓘ φ(2) = 1 ⓘ φ(3) = 2 ⓘ φ(4) = 2 ⓘ φ(5) = 4 ⓘ φ(6) = 2 ⓘ φ(7) = 6 ⓘ φ(8) = 4 ⓘ φ(9) = 6 ⓘ |
Referenced by (3)
Full triples — surface form annotated when it differs from this entity's canonical label.
this entity surface form:
OEIS sequence A000010
this entity surface form:
Euler’s phi function