Statements (30)
Predicate | Object |
---|---|
gptkbp:instanceOf |
arithmetic function
|
gptkbp:alsoKnownAs |
phi function
|
gptkbp:application |
gptkb:RSA_cryptosystem
gptkb:Euler's_theorem primitive roots |
gptkbp:codomain |
non-negative integers
|
gptkbp:defines |
number of positive integers less than or equal to n that are coprime to n
|
gptkbp:designer |
no simple closed form
|
gptkbp:domain |
positive integers
|
gptkbp:field |
number theory
|
gptkbp:firstValues |
φ(1)=1, φ(2)=1, φ(3)=2, φ(4)=2, φ(5)=4, φ(6)=2, φ(7)=6, φ(8)=4, φ(9)=6, φ(10)=4
|
gptkbp:form |
φ(n) = n × ∏(1 - 1/p) over all distinct prime divisors p of n
|
gptkbp:hasSpecialCase |
φ(1) = 1
|
https://www.w3.org/2000/01/rdf-schema#label |
Euler's totient function
|
gptkbp:introducedIn |
18th century
|
gptkbp:multiplicative |
true
|
gptkbp:namedAfter |
gptkb:Leonhard_Euler
|
gptkbp:property |
even for n > 2
sum of φ(d) over all divisors d of n equals n φ(mn) = φ(m)φ(n) if gcd(m, n) = 1 |
gptkbp:relatedTo |
gptkb:Carmichael_function
gptkb:Möbius_function order of multiplicative group modulo n |
gptkbp:sequence |
gptkb:A000010_(OEIS)
|
gptkbp:symbol |
φ(n)
|
gptkbp:valueAtPrime |
φ(p) = p - 1 for prime p
|
gptkbp:bfsParent |
gptkb:Leonhard_Euler
gptkb:Number_theory gptkb:RSA_encryption |
gptkbp:bfsLayer |
5
|