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.
All labels observed (6)
| Label | Occurrences |
|---|---|
| Euler totient function | 2 |
| Euler’s totient function | 2 |
| Euler’s totient function φ(n) canonical | 2 |
| Euler totient function φ(n) | 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 phi function
ⓘ
linked to:
Euler’s totient function φ(n)
|
| 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 |
OEIS sequence A000010
ⓘ
linked to:
Euler’s totient function φ(n)
|
| 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 cryptosystem ⓘ
linked to:
RSA
|
| 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
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Euler’s totient function φ(n) Description of subject: 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.
Referenced by (9)
Full triples — surface form annotated when it differs from this entity's canonical label.
linked to: Euler’s totient function φ(n)
linked to: Euler’s totient function φ(n)
linked to: Euler’s totient function φ(n)
linked to: Euler’s totient function φ(n)
linked to: Euler’s totient function φ(n)
linked to: Euler’s totient function φ(n)