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 Disambiguation Statements Elicitation 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

How this entity was disambiguated

This entity first appeared as the object of triple T426768 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.

NED1 Entity disambiguation (via context triple) gpt-5-mini-2025-08-07

Target entity: Euler’s totient function φ(n)
Context triple: [Leonhard Euler, notableWork, Euler’s totient function φ(n)]

A. Riemann–Siegel formula
The Riemann–Siegel formula is an asymptotic expression that efficiently approximates the Riemann zeta function on the critical line, playing a key role in the numerical study of its zeros.
B. Über die Anzahl der Primzahlen unter einer gegebenen Grösse
Über die Anzahl der Primzahlen unter einer gegebenen Grösse is Bernhard Riemann’s seminal 1859 paper that introduced the Riemann zeta function and laid the foundations of analytic number theory, including the famous Riemann Hypothesis.
C. Riemann zeta function
The Riemann zeta function is a complex-valued function central to analytic number theory, whose properties—especially the distribution of its zeros—are deeply connected to the distribution of prime numbers.
D. Gauss’s constant
Gauss’s constant is a mathematical constant arising in number theory and complex analysis, particularly in connection with the lemniscate and elliptic functions.
E. Gauss’s lemma in number theory
Gauss’s lemma in number theory is a result that relates the Legendre symbol to the number of sign changes in a certain sequence of multiples, providing a practical criterion for determining quadratic residues modulo an odd prime.
F. None of above. chosen
G. Unsure - the case is ambiguous/there is not enough information to decide.

NED2 Entity disambiguation (via description) gpt-5-mini-2025-08-07

Target entity: Euler’s totient function φ(n)
Target entity description: 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.

A. Riemann–Siegel formula
The Riemann–Siegel formula is an asymptotic expression that efficiently approximates the Riemann zeta function on the critical line, playing a key role in the numerical study of its zeros.
B. Über die Anzahl der Primzahlen unter einer gegebenen Grösse
Über die Anzahl der Primzahlen unter einer gegebenen Grösse is Bernhard Riemann’s seminal 1859 paper that introduced the Riemann zeta function and laid the foundations of analytic number theory, including the famous Riemann Hypothesis.
C. Riemann zeta function
The Riemann zeta function is a complex-valued function central to analytic number theory, whose properties—especially the distribution of its zeros—are deeply connected to the distribution of prime numbers.
D. Gauss’s constant
Gauss’s constant is a mathematical constant arising in number theory and complex analysis, particularly in connection with the lemniscate and elliptic functions.
E. Gauss’s lemma in number theory
Gauss’s lemma in number theory is a result that relates the Legendre symbol to the number of sign changes in a certain sequence of multiples, providing a practical criterion for determining quadratic residues modulo an odd prime.
F. None of above. chosen

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 ⓘ

How these facts were elicited

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) ⓘ