Euler's totient function

:For other meanings, see Euler function (disambiguation).

Other properties

The number φ(n) is also equal to the number of generators of the cyclic group Cn (and therefore also to the degree of the cyclotomic polynomial Φn). Since every element of Cn generates a cyclic subgroup and the subgroups of Cn are of the form Cd where d divides n (written as d|n), we get

Related Topics:
Cyclic group - Cyclotomic polynomial - Subgroup - Divides

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:sum_{dmid n}arphi(d)=n

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

where the sum extends over all positive divisors d of n.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

We can now use the Möbius inversion formula to "invert" this sum and get another formula for φ(n):

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

arphi(n)=sum_{dmid n} d mu(n/d)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

where mu is the usual Möbius function defined on the positive integers.

Related Topics:
Möbius function - Positive integers

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

If a is coprime to n, that is, gcd(a,n)=1 then

Related Topics:
Coprime - Gcd

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:a^{arphi(n)} equiv 1mod n.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~