Euler's totient function

Encyclopedia

In number theory

, the

to

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

The totient is usually called the

mathematician Leonhard Euler

, who studied it. The totient function is also called

(). The

The totient function is important mainly because it gives the size of the multiplicative group of integers modulo

. More precisely, is the order of the group

of unit

s of the ring . This fact, together with Lagrange's theorem

on the possible sizes of subgroups of a group, provides a proof for Euler's theorem that for all

; if

between

.)

If , where is prime, then .

The value of for can thus be computed using the fundamental theorem of arithmetic

: if

where each

, then

This last formula is an Euler product

and is often written in the equivalent form (multiplying top and bottom by )

with the product ranging only over the distinct primes

This can be rewritten as

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.

Note that the lower bound of

The number is also equal to the number of possible generators of the cyclic group

). Since every element of

and the subgroups of

where the sum extends over all positive divisors

We can now use the Möbius inversion formula

to "invert" this sum and get another formula for :

where

defined on the positive integers.

According to Euler's theorem, if

to

(

This follows from Lagrange's theorem

and the fact that

of iff

to

s presented here are both consequences of the fact that

Which, in the notation of Dirichlet convolution

of Multiplicative function

, 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 |

This follows from

which is

for any given ε > 0 and

we can write that, from the formula above, as the product of factors

taken over the prime numbers

it can be shown that a constant ε in the formula above can therefore be replaced by

is also generally close to

where the big O

is the Landau symbol. This also says that the probability of two positive integers chosen at random from being relatively prime approaches when

Because , one can also express the formula this way.

Because modulo , has order , but we also have

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 SwissSwitzerland

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 phiPhi (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 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 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 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....

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 theoremChinese 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 arithmetic

Fundamental 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

*p*_{i}is a distinct primePrime 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 getThis 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*= 4*n*/15 ≈ .267*n*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 group

Cyclic 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...

*C*_{n}(and therefore also to the degree of the cyclotomic polynomialCyclotomic 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

*C*_{n}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

*C*_{n}are of the form*C*_{d}where*d*dividesDivisor

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 getwhere 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 functionMö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 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*, that is, gcdGreatest 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, thenThis 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 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 iff

If 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 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*.## 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 havefor any given ε > 0 and

*n*>*N*(ε). In fact if we considerwe 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 theoremPrime 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 byBecause , 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 n

## 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