FACTOID # 7: The top five best educated states are all in the Northeast.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Euler's totient function
The first thousand values of φ(n)
The first thousand values of φ(n)

In number theory, the totient φ(n) of a positive integer n is defined to be the number of positive integers less than or equal to n and coprime to n. For example, φ(8) = 4 since the four numbers 1, 3, 5 and 7 are coprime to 8. The function φ so defined is the totient function. The totient is usually called the Euler totient or Euler's totient, after the Swiss mathematician Leonhard Euler, who studied it. The totient function is also called Euler's phi function or simply the phi function, since the letter Phi (φ) is so commonly used for it. The cototient of n is defined as nφ(n). Image File history File links EulerPhi. ... Image File history File links EulerPhi. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is... Coprime - Wikipedia /**/ @import /skins-1. ... In mathematics, a function is a relation, such that each element of a set (the domain) is associated with a unique element of another (possibly the same) set (the codomain, not to be confused with the range). ... Leonhard Euler by Emanuel Handmann. ... Phi (upper case Φ, lower case φ or ) is the 21st letter of the Greek alphabet. ...


The totient function is important mainly because it gives the size of the multiplicative group of integers modulo n. More precisely, φ(n) is the order of the group of units of the ring mathbb{Z}/nmathbb{Z}. This fact, together with Lagrange's theorem, provides a proof for Euler's theorem. In mathematics, a group is a set, together with a binary operation, such as multiplication or addition, satisfying certain axioms, detailed below. ... Modular arithmetic (sometimes called modulo arithmetic) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... In mathematics, a unit in a ring R is an element u such that there is v in R with uv = vu = 1R. That is, u is an invertible element of the multiplicative monoid of R. The units of R form a group U(R) under multiplication, the group of... In ring theory, a branch of abstract algebra, a ring is an algebraic structure in which addition and multiplication are defined and have similar properties to those familiar from the integers. ... Lagranges theorem, in the mathematics of group theory, states that if G is a finite group and H is a subgroup of G, then the order (that is, the number of elements) of H divides the order of G. It is named after Joseph Lagrange. ... In number theory, Eulers theorem (also known as the Fermat-Euler theorem or Eulers totient theorem) states that if n is a positive integer and a is coprime to n, then aφ(n) ≡ 1 (mod n) where φ(n) is Eulers totient function and mod denotes the congruence...

Contents


Computing Euler's function

It follows from the definition that φ(1) = 1, and φ(n) is (p − 1)pk−1 when n is the kth power of a prime number p. Moreover, φ is a multiplicative function; if m and n are coprime then φ(mn) = φ(m)φ(n). (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 bijection between AxB and C, via the Chinese remainder theorem.) The value of φ(n) can thus be computed using the fundamental theorem of arithmetic: if In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ... In number theory, a multiplicative function is an arithmetic function f(n) of the positive integer n with the property that f(1) = 1 and whenever a and b are coprime, then f(ab) = f(a) f(b). ... A bijective function. ... link titleThe Chinese remainder theorem (CRT) is the name for several related results in abstract algebra and number theory. ... In mathematics, and in particular number theory, the fundamental theorem of arithmetic or unique factorization theorem is the statement that every positive integer greater than 1 is either a prime number or can be written as a product of prime numbers. ...

n = p1k1 ... prkr

where the pj are distinct primes, then In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ...

varphi(n)=(p_{1}-1)p_{1}^{k_{1}-1} cdots (p_{r}-1)p_{r}^{k_{r}-1}

This last formula is a Euler product and is often written as In mathematics, an Euler product is an infinite product expansion, indexed by prime numbers p, of a Dirichlet series. ...

varphi(n)=nprod_{p|n}left(1-frac{1}{p}right)

with the product ranging only over the distinct primes pr.


Computing example

Some values of the function

varphi(n) +0 +1 +2 +3 +4 +5 +6 +7 +8 +9 +10 +11
0+   1 1 2 2 4 2 6 4 6 4 10
12+ 4 12 6 8 8 16 6 18 8 12 10 22
24+ 8 20 12 18 12 28 8 30 16 20 16 24
36+ 12 36 18 24 16 40 12 42 20 24 22 46
48+ 16 42 20 32 24 52 18 40 24 36 28 58
60+ 16 60 30 36 32 48 20 66 32 44 24 70
72+ 24 72 36 40 36 60 24 78 32 54 40 82

ććć==Properties== The number φ(n) is also equal to the number of possible 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 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 a (called a generator of the group) such that, when written multiplicatively, every element of the group is a power of a (or na... In mathematics, the n-th roots of unity or de Moivre numbers, named after Abraham de Moivre (1667 - 1754), are complex numbers located on the unit circle. ... In group theory, given a group G under a binary operation *, we say that some subset H of G is 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 is a group... In mathematics, a divisor of an integer n, also called a factor of n, is an integer which evenly divides n without leaving a remainder. ...

sum_{dmid n}varphi(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): The classic Möbius inversion formula was introduced into number theory during the 19th century by August Ferdinand Möbius. ...

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

where μ is the usual Möbius function defined on the positive integers. The classical Möbius function is an important multiplicative function in number theory and combinatorics. ... Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is...


According to Euler's theorem, if a is coprime to n, that is, gcd(a,n) = 1, then In number theory, Eulers theorem (also known as the Fermat-Euler theorem or Eulers totient theorem) states that if n is a positive integer and a is coprime to n, then aφ(n) ≡ 1 (mod n) where φ(n) is Eulers totient function and mod denotes the congruence... Coprime - Wikipedia /**/ @import /skins-1. ... In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf) of two integers which are both not zero is the largest integer that divides both numbers. ...

a^{varphi(n)} equiv 1mod n.

This follows from Lagrange's theorem and the fact that a belongs to the multiplicative group of mathbb{Z}/nmathbb{Z} if and only if a is coprime to n. Lagranges theorem, in the mathematics of group theory, states that if G is a finite group and H is a subgroup of G, then the order (that is, the number of elements) of H divides the order of G. It is named after Joseph Lagrange. ... In mathematics, the multiplicative group of integers modulo n is the group defined by multiplication of the units (that is, the numbers relatively prime to ) in the ring for a given integer . ... It has been suggested that this article or section be merged with Logical biconditional. ... Coprime - Wikipedia /**/ @import /skins-1. ...


Generating functions

A Dirichlet series involving φ(n) is In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers. ... In mathematics, a Dirichlet series, one of a number of concepts named in honor of Johann Peter Gustav Lejeune Dirichlet, is a series of the form The most famous of Dirichlet series is which is the Riemann zeta function. ...

sum_{n=1}^{infty} frac{varphi(n)}{n^s}=frac{zeta(s-1)}{zeta(s)}.

A Lambert series generating function is A Lambert series, named after Johann Heinrich Lambert, is a series taking the form It can be resummed by expanding the denominator: where the coefficients of the new series are given by the Dirichlet convolution of with the constant function Since this last sum is a typical number-theortic sum...

sum_{n=1}^{infty} frac{varphi(n) q^n}{1-q^n}= frac{q}{(1-q)^2}

which converges for |q|<1.


Growth of the function

The growth of φ(n) as a function of n is an interesting question, since the first impression from small n that φ(n) might be noticeably smaller than n is somewhat misleading. Asymptotically we have

n1−ε < φ(n) < n

for any given ε > 0 and n > N(ε). In fact if we consider

φ(n)/n

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

1 −p−1

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 it can be shown that a constant ε in the formula above can therefore be replaced by In number theory, the prime number theorem (PNT) describes the approximate, asymptotic distribution of the prime numbers. ...

C log log n/log n.

φ is also generally close to n in an average sense:

frac{1}{n^2} sum_{k=1}^n varphi(k)= frac{3}{pi^2} + mathcal{O}left(frac{log n }{n}right)

where the big O is the Landau symbol. This also says that the probability of two positive integers chosen at random from [1,n] x [1,n] being relatively prime is 6 / π2. A proof of this formula may be found here. It has been suggested that Landau notation be merged into this article or section. ... In complexity theory, computer science, and mathematics the Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ... This page provides proofs for identities involving the totient function and the Möbius function . ...


Other formulas involving Euler's function

;varphi(n^m) = n^{m-1}varphi(n) for mge 1
sum_{d mid n} frac{mu^2(d)}{varphi(d)} = frac{n}{varphi(n)}
sum_{1le kle n atop (k,n)=1} = frac{1}{2}nvarphi(n) for ;n>1
sum_{k=1}^nvarphi(k) = frac{1}{2}left(1+ sum_{k=1}^n mu(k)leftlfloorfrac{n}{k}rightrfloor^2right)
sum_{k=1}^nfrac{varphi(k)}{k} = sum_{k=1}^nfrac{mu(k)}{k}leftlfloorfrac{n}{k}rightrfloor
sum_{k=1}^nfrac{k}{varphi(k)} = mathcal{O}(n)
sum_{k=1}^nfrac{1}{varphi(k)} = mathcal{O}(log(n))

Proofs of some of these identities may be found here. This page provides proofs for identities involving the totient function and the Möbius function . ...


Inequalities

Some inequalities involving the φ function are: The feasible regions of linear programming are defined by a set of inequalities. ...

varphi(n) > frac {n} {e^gamma; log log n + frac {3} {log log n}} for n > 2, where γ is Euler's constant,
varphi(n) ge sqrt{frac {n} {2} } for n > 0,

and The Euler-Mascheroni constant is a mathematical constant, used mainly in number theory, and is defined as the limiting difference between the harmonic series and the natural logarithm: Its approximate value is γ ≈ 0. ...

varphi(n) ge sqrt{n} for n > 6.

For prime n, clearly φ(n) = n-1. For composite n we have A composite number is a positive integer which has a positive divisor other than one or itself. ...

varphi(n) le n-sqrt{n} (for composite n).

For all n > 1:


0<frac{varphi (n)}{n}<1


For randomly large n, these bounds still cannot be improved, or to be more precise :


lim inf and lim sup


A pair of inequalities combining the φ function and the σ divisor function are: In mathematics, and specifically in number theory, a divisor function is an arithmetical function related to the divisors of an integer. ...

frac {6 n^2} {pi^2} < varphi(n) sigma(n) < n^2 for n > 1.

See also

A nontotient is a positive integer n which is not in the range of Eulers totient function φ, that is, for which φ(x) = n has no solution. ... A noncototient is a positive integer n that can not be expressed as the difference between a positive integer m and the number of coprime integers below it. ... A highly totient number k is an integer that has more solutions to the equation φ(x) = k, where φ is Eulers totient function, than any integer below it. ... In mathematics, a sparsely totient number is a certain kind of natural number. ... In number theory, a branch of mathematics, a highly cototient number k is an integer that has more solutions to the equation x - φ(x) = k, where φ is Eulers totient function, than any integer below it, with the exception of 1. ... In mathematics, and specifically in number theory, a divisor function is an arithmetical function related to the divisors of an integer. ...

References

  • Milton Abramowitz and Irene A. Stegun, Handbook of Mathematical Functions, (1964) Dover Publications, New York. ISBN 486-61272-4 . See paragraph 24.3.2.
  • Eric Bach and Jeffrey Shallit, Algorithmic Number Theory, volume 1, 1996, MIT Press. ISBN 0-262-02405-5, see page 234 in section 8.8.
  • Kirby Urner, Computing totient function in Python and scheme, (2003)

  Results from FactBites:
 
file_nav_name Encyclopedia Index (8557 words)
A hash function or hash algorithm is a function for examining the input data and producing an output of a fixed length,...
A function prototype in C or C++ is a declaration of a function that omits the function body but does specify the func...
In complex analysis, a meromorphic function on an open subset D of the complex plane is a function that is holomor...
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m