Statements (29)
Predicate | Object |
---|---|
gptkbp:instanceOf |
arithmetical 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 up to n that are coprime to n
|
gptkbp:domain |
positive integers
|
gptkbp:field |
number theory
|
gptkbp:firstValues |
1,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8,16,6,18,8,12,10,22,8,20,12,18,12,28,8,30,16,20,16,24,12,36,18,24,16,40,12,42,20,24,22,46,16,42,20,32,24,52,18,40,24,36,28,58,16,60,30,36,32,48,20,66,32,44,24,70,24,72,36,40,36,60,24,78,32,54,40,82,24,64,42,56,40,88,24,72,44,60,46,72,32,96,42,60,40
|
gptkbp:form |
φ(n) = n * product over p|n of (1 - 1/p)
|
gptkbp:hasSpecialCase |
φ(1) = 1
φ(p) = p-1 for prime p |
https://www.w3.org/2000/01/rdf-schema#label |
Euler 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 φ(p^k) = p^k - p^{k-1} for prime p |
gptkbp:relatedTo |
gptkb:Carmichael_function
gptkb:Möbius_function gptkb:Dirichlet_convolution Jordan's totient function |
gptkbp:sequence |
gptkb:A000010_(OEIS)
|
gptkbp:symbol |
φ(n)
|
gptkbp:bfsParent |
gptkb:A000010_(OEIS)
|
gptkbp:bfsLayer |
7
|