Euler's totient function φ(n)

GPTKB entity

Predicate	Object
gptkbp:instanceOf	arithmetic function
gptkbp:alsoKnownAs	gptkb:Euler's_phi_function
gptkbp:application	gptkb:RSA_cryptosystem gptkb:Euler's_theorem
gptkbp:codomain	non-negative integers
gptkbp:defines	number of positive integers less than or equal to n that are coprime to n
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 * Π_{p\|n} (1 - 1/p), where p runs over the distinct prime divisors of n
gptkbp:hasSpecialCase	φ(1) = 1 φ(p) = p-1 for prime p
https://www.w3.org/2000/01/rdf-schema#label	Euler's totient function φ(n)
gptkbp:inverseFunction	not injective
gptkbp:multiplicative	true
gptkbp:namedAfter	gptkb:Leonhard_Euler
gptkbp:notation	φ(n) phi(n)
gptkbp:property	φ(mn) = φ(m)φ(n) if gcd(m, n) = 1 sum_{d\|n} φ(d) = n
gptkbp:relatedTo	gptkb:Carmichael_function gptkb:Möbius_function primitive roots
gptkbp:sequence	gptkb:A000010_(OEIS)
gptkbp:usedIn	cryptography group theory
gptkbp:bfsParent	gptkb:Multiplicative_group_modulo_n
gptkbp:bfsLayer	5