Euler’s totient function φ(n)

E54269

arithmetic function multiplicative function number-theoretic function

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.

Try in SPARQL Jump to: Surface forms Statements Referenced by

All labels observed (5)

Label	Occurrences
Euler’s totient function	2
Euler’s totient function φ(n) canonical	2
Euler totient function	1
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 (7)

Full triples — surface form annotated when it differs from this entity's canonical label.

Leonhard Euler → notableWork → Euler’s totient function φ(n) ⓘ

Euler’s totient function φ(n) → alternativeName → Euler’s totient function φ(n) ⓘ

this entity surface form: Euler’s phi function

Euler’s totient function φ(n) → OEIS → Euler’s totient function φ(n) self-linksurface differs ⓘ

this entity surface form: OEIS sequence A000010

Lambert series → canEncode → Euler’s totient function φ(n) ⓘ

this entity surface form: Euler totient function

Euler’s theorem → usesConcept → Euler’s totient function φ(n) ⓘ

this entity surface form: Euler’s totient function

Euler’s theorem → hasComponent → Euler’s totient function φ(n) ⓘ

Ramanujan’s sum → relatedTo → Euler’s totient function φ(n) ⓘ

this entity surface form: Euler’s totient function