Statements (24)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
arithmetic function
|
| gptkbp:alsoKnownAs |
gptkb:Euler's_totient_function
|
| gptkbp:codomain |
non-negative integers
|
| gptkbp:defines |
number of positive integers up to n that are coprime to n
|
| gptkbp:domain |
positive integers
|
| gptkbp:firstFewValues |
φ(1)=1, φ(2)=1, φ(3)=2, φ(4)=2, φ(5)=4, φ(6)=2, φ(7)=6, φ(8)=4, φ(9)=6, φ(10)=4
|
| gptkbp:form |
φ(n) = n ∏_{p|n} (1 - 1/p)
|
| https://www.w3.org/2000/01/rdf-schema#label |
Euler's phi function
|
| gptkbp:introduced |
gptkb:Leonhard_Euler
|
| gptkbp:introducedIn |
1763
|
| gptkbp:multiplicative |
true
|
| gptkbp:namedAfter |
gptkb:Leonhard_Euler
|
| gptkbp:property |
φ(mn) = φ(m)φ(n) if gcd(m, n) = 1
sum_{d|n} φ(d) = n n = ∑_{d|n} φ(d) |
| gptkbp:sequence |
gptkb:A000010_(OEIS)
|
| gptkbp:symbol |
φ(n)
|
| gptkbp:usedIn |
gptkb:RSA_algorithm
cryptography number theory |
| gptkbp:valueAtPrime |
φ(p) = p - 1 for prime p
|
| gptkbp:valueAtPrimePower |
φ(p^k) = p^k - p^{k-1}
|
| gptkbp:bfsParent |
gptkb:Euler's_totient_function_φ(n)
|
| gptkbp:bfsLayer |
6
|