Euler's totient function
Encyclopedia
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, the totient
of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprimeCoprime
In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
to n (i.e. having no common positive factors other than 1).
In particular
since 1 is coprime to itself (1 being the only natural number with this property).For example,
since the six numbers 1, 2, 4, 5, 7 and 8 are coprime to 9.The function
so defined is the totient function.The totient is usually called the Euler totient or Euler's totient, after the Swiss
Switzerland
Switzerland name of one of the Swiss cantons. ; ; ; or ), in its full name the Swiss Confederation , is a federal republic consisting of 26 cantons, with Bern as the seat of the federal authorities. The country is situated in Western Europe,Or Central Europe depending on the definition....
mathematician Leonhard Euler
Leonhard Euler
Leonhard Euler was a pioneering Swiss mathematician and physicist. He made important discoveries in fields as diverse as infinitesimal calculus and graph theory. He also introduced much of the modern mathematical terminology and notation, particularly for mathematical analysis, such as the notion...
, who studied it. The totient function is also called Euler's phi function or simply the phi function, since it is commonly denoted by the Greek letter phi
Phi (letter)
Phi , pronounced or sometimes in English, and in modern Greek, is the 21st letter of the Greek alphabet. In modern Greek, it represents , a voiceless labiodental fricative. In Ancient Greek it represented , an aspirated voiceless bilabial plosive...
(
). The cototient of n is defined as 
, in other words the number of positive integers less than or equal to n that are not coprime to n.The totient function is important mainly because it gives the size of the multiplicative group of integers modulo n
Multiplicative group of integers modulo n
In modular arithmetic the set of congruence classes relatively prime to the modulus n form a group under multiplication called the multiplicative group of integers modulo n. It is also called the group of primitive residue classes modulo n. In the theory of rings, a branch of abstract algebra, it...
. More precisely,
is the order of the groupMultiplicative group of integers modulo n
In modular arithmetic the set of congruence classes relatively prime to the modulus n form a group under multiplication called the multiplicative group of integers modulo n. It is also called the group of primitive residue classes modulo n. In the theory of rings, a branch of abstract algebra, it...
of unit
Unit (ring theory)
In mathematics, an invertible element or a unit in a ring R refers to any element u that has an inverse element in the multiplicative monoid of R, i.e. such element v that...
s of the ring
. This fact, together with Lagrange's theoremLagrange's theorem (group theory)
Lagrange's theorem, in the mathematics of group theory, states that for any finite group G, the order of every subgroup H of G divides the order of G. The theorem is named after Joseph Lagrange....
on the possible sizes of subgroups of a group, provides a proof for Euler's theorem that
for all a coprime to n. The totient function also plays a key role in the definition of the RSA encryption system.Computing Euler's function
The totient
is a multiplicative functionMultiplicative function
In number theory, a multiplicative function is an arithmetic function f of the positive integer n with the property that f = 1 and whenevera and b are coprime, then...
; if m and n are coprime then
. (Sketch of proof: let A, B, C be the sets of residue classes modulo-and-coprime-to m, n, mn respectively; then there is a bijectionBijection
A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
between A × B and C, by the Chinese remainder theorem
Chinese remainder theorem
The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...
.)
If
, where 
is prime, then 
.Proof: It is easy to list all positive integers that are less than or equal to
and not relatively prime to 
. They are 
. They are all multiples of 
and we have exactly 
of them. Therefore, there are exactly 
positive integers less than or equal to 
that are relatively prime to 
.The value of
for 
can thus be computed using the fundamental theorem of arithmeticFundamental theorem of arithmetic
In number theory, the fundamental theorem of arithmetic states that any integer greater than 1 can be written as a unique product of prime numbers...
: if
where each pi is a distinct prime
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
, then
This last formula is an Euler product
Euler product
In number theory, an Euler product is an expansion of a Dirichlet series into an infinite product indexed by prime numbers. The name arose from the case of the Riemann zeta-function, where such a product representation was proved by Leonhard Euler.-Definition:...
and is often written in the equivalent form (multiplying top and bottom by
)
with the product ranging only over the distinct primes p dividing n.
Proof: Repeatedly applying the above mentioned theorems that we get
This can be rewritten as
Computing example
In words, this says that the distinct prime factors of 36 are 2 and 3; half of the thirty-six integers from 1 to 36 are divisible by 2, leaving eighteen; a third of those are divisible by 3, leaving twelve coprime to 36. And indeed there are twelve: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, and 35.
Some values of the function
The first 99 values are shown in the table and graph below:  |
+0 | +1 | +2 | +3 | +4 | +5 | +6 | +7 | +8 | +9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 0+ | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | |
| 10+ | 4 | 10 | 4 | 12 | 6 | 8 | 8 | 16 | 6 | 18 |
| 20+ | 8 | 12 | 10 | 22 | 8 | 20 | 12 | 18 | 12 | 28 |
| 30+ | 8 | 30 | 16 | 20 | 16 | 24 | 12 | 36 | 18 | 24 |
| 40+ | 16 | 40 | 12 | 42 | 20 | 24 | 22 | 46 | 16 | 42 |
| 50+ | 20 | 32 | 24 | 52 | 18 | 40 | 24 | 36 | 28 | 58 |
| 60+ | 16 | 60 | 30 | 36 | 32 | 48 | 20 | 66 | 32 | 44 |
| 70+ | 24 | 70 | 24 | 72 | 36 | 40 | 36 | 60 | 24 | 78 |
| 80+ | 32 | 54 | 40 | 82 | 24 | 64 | 42 | 56 | 40 | 88 |
| 90+ | 24 | 72 | 44 | 60 | 46 | 72 | 32 | 96 | 42 | 60 |
Note that the lower bound of y = 4n/15 ≈ .267n only occurs where n is a multiple of 30. (This is not a lower bound for the whole totient function, but only for these first few values of n. For example,
; 
; and 
.)Properties
for prime p and 
.
where 
.
where m = 2k.
where m = 2k+1.
(See lcmLeast common multipleIn arithmetic and number theory, the least common multiple of two integers a and b, usually denoted by LCM, is the smallest positive integer that is a multiple of both a and b...
).
implies 
.
is even for 
. Moreover, if n has r distinct odd prime factors, 
. has shown that:
The number
is also equal to the number of possible generators of the cyclic groupCyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...
Cn (and therefore also to the degree of the cyclotomic polynomial
Cyclotomic polynomial
In algebra, the nth cyclotomic polynomial, for any positive integer n, is the monic polynomial:\Phi_n = \prod_\omega \,where the product is over all nth primitive roots of unity ω in a field, i.e...
). Since every element of Cn generates a cyclic subgroupSubgroup
In group theory, given a group G under a binary operation *, a subset H of G is called a subgroup of G if H also forms a group under the operation *. More precisely, H is a subgroup of G if the restriction of * to H x H is a group operation on H...
and the subgroups of Cn are of the form Cd where d divides
Divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer which divides n without leaving a remainder.-Explanation:...
n (written as d | n), we get
where the sum extends over all positive divisors d of n.
We can now use the Möbius inversion formula
Möbius inversion formula
In mathematics, the classic Möbius inversion formula was introduced into number theory during the 19th century by August Ferdinand Möbius. Other Möbius inversion formulas are obtained when different local finite partially ordered sets replace the classic case of the natural numbers ordered by...
to "invert" this sum and get another formula for
:
where μ is the usual Möbius function
Möbius function
The classical Möbius function μ is an important multiplicative function in number theory and combinatorics. The German mathematician August Ferdinand Möbius introduced it in 1832...
defined on the positive integers.
According to Euler's theorem, if a is coprime
Coprime
In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
to n, that is, gcd
Greatest common divisor
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
(a, n) = 1, then
This follows from Lagrange's theorem
Lagrange's theorem (group theory)
Lagrange's theorem, in the mathematics of group theory, states that for any finite group G, the order of every subgroup H of G divides the order of G. The theorem is named after Joseph Lagrange....
and the fact that a belongs to the multiplicative group
Multiplicative group of integers modulo n
In modular arithmetic the set of congruence classes relatively prime to the modulus n form a group under multiplication called the multiplicative group of integers modulo n. It is also called the group of primitive residue classes modulo n. In the theory of rings, a branch of abstract algebra, it...
of
iffIf and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
a is coprime
Coprime
In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
to n.
Generating functions
The two generating functionGenerating function
In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general...
s presented here are both consequences of the fact that
Which, in the notation of Dirichlet convolution
Dirichlet convolution
In mathematics, the Dirichlet convolution is a binary operation defined for arithmetic functions; it is important in number theory. It was developed by Johann Peter Gustav Lejeune Dirichlet, a German mathematician.-Definition:...
of Multiplicative function
Multiplicative function
In number theory, a multiplicative function is an arithmetic function f of the positive integer n with the property that f = 1 and whenevera and b are coprime, then...
, says:
The Dirichlet series for
may be written in terms of the Riemann zeta function by taking Dirichlet series of both sides and rearranging to get:
A Lambert series generating function is
which converges for |q|<1.
This follows from
which is
Growth of the function
The growth of
as a function of n is an interesting question, since the first impression from small n that 
might be noticeably smaller than n is somewhat misleading. Asymptotically we have
for any given ε > 0 and n > N(ε). In fact if we consider
we can write that, from the formula above, as the product of factors
taken over the prime numbers p dividing n. Therefore the values of n corresponding to particularly small values of the ratio are those n that are the product of an initial segment of the sequence of all primes. From the prime number theorem
Prime number theorem
In number theory, the prime number theorem describes the asymptotic distribution of the prime numbers. The prime number theorem gives a general description of how the primes are distributed amongst the positive integers....
it can be shown that a constant ε in the formula above can therefore be replaced by
is also generally close to n in an average sense:
where the big O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
is the Landau symbol. This also says that the probability of two positive integers chosen at random from
being relatively prime approaches 
when n tends to infinity. A related result is the average order of 
, which is described by
Because
, one can also express the formula this way.
Other formulas involving Euler's function
Because modulo
, 
has order 
, but we also have 
- For any
and 
such that 
there exists an 
such that 
.
where m > 1 is a positive integer and ω(m) designates the number of distinct prime factors of m. (This formula counts the number of naturals less than or equal to n and relatively prime to m, additional material is listed among the external links.)
Inequalities
Some inequalities involving the
function are:
for n > 2, where γ is Euler's constantEuler–Mascheroni constantThe Euler–Mascheroni constant is a mathematical constant recurring in analysis and number theory, usually denoted by the lowercase Greek letter ....
,
for n > 0,
and
For prime n, clearly
.
For a composite numberComposite numberA composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
n we have
.
For any even number 2n we have
where equality holds only if n is a power of two.
For arbitrarily large n, these bounds still cannot be improved, or to be more precise:
The first bound follows by considering n as the product of the first k primes. The second follows from letting n range over the primes.
A pair of inequalities combining the
function and the 
divisor functionDivisor functionIn mathematics, and specifically in number theory, a divisor function is an arithmetical function related to the divisors of an integer. When referred to as the divisor function, it counts the number of divisors of an integer. It appears in a number of remarkable identities, including relationships...
are:
Ford's theorem
proved that for every integer k ≥ 2 there is a number m for which the equation φ(x) = m has exactly k solutions; this result had previously been conjectured by Wacław Sierpiński. However, no such m is known for k = 1, and according to Carmichael's totient function conjectureCarmichael's totient function conjectureIn mathematics, Carmichael's totient function conjecture concerns the multiplicity of values of Euler's totient function φ, which counts the number of integers less than and coprime to n...
it is believed that in this case no such m exists.
See also
- Carmichael function
- Generalizations of Fermat's little theorem
- Multiplicative group of integers modulo nMultiplicative group of integers modulo nIn modular arithmetic the set of congruence classes relatively prime to the modulus n form a group under multiplication called the multiplicative group of integers modulo n. It is also called the group of primitive residue classes modulo n. In the theory of rings, a branch of abstract algebra, it...
External links
- Kirby Urner, Computing totient function in Python and scheme, (2003)
- Euler's totient function calculator in JavaScript - up to 20 digits
- Miyata, Daisuke & Yamashita, Michinori, Derived logarithmic function of Euler's function
- Bordellès, Olivier, Numbers prime to q in
] - Plytage, Loomis, Polhill Summing Up The Euler Phi Function