We are working to restore the Unionpedia app on the Google Play Store
OutgoingIncoming
🌟We've simplified our design for better navigation!
Instagram Facebook X LinkedIn

Euler's totient function

Index Euler's totient function

In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to. [1]

Table of Contents

  1. 80 relations: An Introduction to the Theory of Numbers, Andrzej Schinzel, Annals of Mathematics, Arnold Walfisz, Big O notation, Bijection, Carl Friedrich Gauss, Carmichael function, Carmichael's totient function conjecture, Chinese remainder theorem, Concrete Mathematics, Coprime integers, Cyclic group, D. C. Heath and Company, D. H. Lehmer, Dedekind psi function, Dense set, Deutscher Verlag der Wissenschaften, Dirichlet series, Dirichlet's theorem on arithmetic progressions, Discrete Fourier transform, Disquisitiones Arithmeticae, Divisor function, Dover Publications, Duffin–Schaeffer theorem, Euler's constant, Euler's totient function, Ferdinand Rudio, Fermat number, Fermat's little theorem, Fundamental theorem of arithmetic, Greatest common divisor, Highly composite number, Inclusion–exclusion principle, Integer factorization, Inverse function, Ivan Vinogradov, James Joseph Sylvester, Jean-Louis Nicolas, Jordan's totient function, Journal of Number Theory, Lagrange's theorem (group theory), Lambert series, Least common multiple, Leonhard Euler, Limit inferior and limit superior, Möbius function, Möbius inversion formula, MIT Press, Multiplicative function, ... Expand index (30 more) »

  2. Leonhard Euler
  3. Multiplicative functions

An Introduction to the Theory of Numbers

An Introduction to the Theory of Numbers is a classic textbook in the field of number theory, by G. H. Hardy and E. M. Wright. Euler's totient function and an Introduction to the Theory of Numbers are number theory.

See Euler's totient function and An Introduction to the Theory of Numbers

Andrzej Schinzel

Andrzej Bobola Maria Schinzel (5 April 1937 – 21 August 2021) was a Polish mathematician studying mainly number theory.

See Euler's totient function and Andrzej Schinzel

Annals of Mathematics

The Annals of Mathematics is a mathematical journal published every two months by Princeton University and the Institute for Advanced Study.

See Euler's totient function and Annals of Mathematics

Arnold Walfisz

Arnold Walfisz (2 July 1892 – 29 May 1962) was a Jewish-Polish mathematician working in analytic number theory.

See Euler's totient function and Arnold Walfisz

Big O notation

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

See Euler's totient function and Big O notation

Bijection

A bijection, bijective function, or one-to-one correspondence between two mathematical sets is a function such that each element of the first set (the domain) is mapped to exactly one element of the second set (the codomain).

See Euler's totient function and Bijection

Carl Friedrich Gauss

Johann Carl Friedrich Gauss (Gauß; Carolus Fridericus Gauss; 30 April 177723 February 1855) was a German mathematician, astronomer, geodesist, and physicist who contributed to many fields in mathematics and science.

See Euler's totient function and Carl Friedrich Gauss

Carmichael function

In number theory, a branch of mathematics, the Carmichael function of a positive integer is the smallest member of the set of positive integers having the property that holds for every integer coprime to. Euler's totient function and Carmichael function are modular arithmetic.

See Euler's totient function and Carmichael function

Carmichael's totient function conjecture

In mathematics, Carmichael's totient function conjecture concerns the multiplicity of values of Euler's totient function φ(n), which counts the number of integers less than and coprime to n. It states that, for every n there is at least one other integer m ≠ n such that φ(m). Euler's totient function and Carmichael's totient function conjecture are multiplicative functions.

See Euler's totient function and Carmichael's totient function conjecture

Chinese remainder theorem

In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime (no two divisors share a common factor other than 1). Euler's totient function and Chinese remainder theorem are modular arithmetic.

See Euler's totient function and Chinese remainder theorem

Concrete Mathematics

Concrete Mathematics: A Foundation for Computer Science, by Ronald Graham, Donald Knuth, and Oren Patashnik, first published in 1989, is a textbook that is widely used in computer-science departments as a substantive but light-hearted treatment of the analysis of algorithms.

See Euler's totient function and Concrete Mathematics

Coprime integers

In number theory, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Euler's totient function and coprime integers are number theory.

See Euler's totient function and Coprime integers

Cyclic group

In abstract algebra, a cyclic group or monogenous group is a group, denoted Cn (also frequently \Zn or Zn, not to be confused with the commutative ring of p-adic numbers), that is generated by a single element.

See Euler's totient function and Cyclic group

D. C. Heath and Company

D.

See Euler's totient function and D. C. Heath and Company

D. H. Lehmer

Derrick Henry "Dick" Lehmer (February 23, 1905 – May 22, 1991), almost always cited as D.H. Lehmer, was an American mathematician significant to the development of computational number theory.

See Euler's totient function and D. H. Lehmer

Dedekind psi function

In number theory, the Dedekind psi function is the multiplicative function on the positive integers defined by where the product is taken over all primes p dividing n. (By convention, \psi(1), which is the empty product, has value 1.) The function was introduced by Richard Dedekind in connection with modular functions. Euler's totient function and Dedekind psi function are multiplicative functions.

See Euler's totient function and Dedekind psi function

Dense set

In topology and related areas of mathematics, a subset A of a topological space X is said to be dense in X if every point of X either belongs to A or else is arbitrarily "close" to a member of A — for instance, the rational numbers are a dense subset of the real numbers because every real number either is a rational number or has a rational number arbitrarily close to it (see Diophantine approximation).

See Euler's totient function and Dense set

Deutscher Verlag der Wissenschaften

Deutscher Verlag der Wissenschaften (DVW) (English: German Publisher of Sciences) was a scientific publishing house in the former German Democratic Republic (GDR/DDR).

See Euler's totient function and Deutscher Verlag der Wissenschaften

Dirichlet series

In mathematics, a Dirichlet series is any series of the form \sum_^\infty \frac, where s is complex, and a_n is a complex sequence.

See Euler's totient function and Dirichlet series

Dirichlet's theorem on arithmetic progressions

In number theory, Dirichlet's theorem, also called the Dirichlet prime number theorem, states that for any two positive coprime integers a and d, there are infinitely many primes of the form a + nd, where n is also a positive integer.

See Euler's totient function and Dirichlet's theorem on arithmetic progressions

Discrete Fourier transform

In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency.

See Euler's totient function and Discrete Fourier transform

Disquisitiones Arithmeticae

Disquisitiones Arithmeticae (Latin for Arithmetical Investigations) is a textbook on number theory written in Latin by Carl Friedrich Gauss in 1798, when Gauss was 21, and published in 1801, when he was 24. Euler's totient function and Disquisitiones Arithmeticae are number theory.

See Euler's totient function and Disquisitiones Arithmeticae

Divisor function

In mathematics, and specifically in number theory, a divisor function is an arithmetic function related to the divisors of an integer. Euler's totient function and divisor function are multiplicative functions and number theory.

See Euler's totient function and Divisor function

Dover Publications

Dover Publications, also known as Dover Books, is an American book publisher founded in 1941 by Hayward and Blanche Cirker.

See Euler's totient function and Dover Publications

Duffin–Schaeffer theorem

The Koukoulopoulos–Maynard theorem, also known as the Duffin-Schaeffer conjecture, is a theorem in mathematics, specifically, the Diophantine approximation proposed as a conjecture by R. J. Duffin and A. C. Schaeffer in 1941 and proven in 2019 by Dimitris Koukoulopoulos and James Maynard.

See Euler's totient function and Duffin–Schaeffer theorem

Euler's constant

Euler's constant (sometimes called the Euler–Mascheroni constant) is a mathematical constant, usually denoted by the lowercase Greek letter gamma, defined as the limiting difference between the harmonic series and the natural logarithm, denoted here by: \begin \gamma &. Euler's totient function and Euler's constant are Leonhard Euler.

See Euler's totient function and Euler's constant

Euler's totient function

In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to. Euler's totient function and Euler's totient function are algebra, Leonhard Euler, modular arithmetic, multiplicative functions and number theory.

See Euler's totient function and Euler's totient function

Ferdinand Rudio

Ferdinand Rudio (born 2 August 1856 in Wiesbaden, died 21 June 1929 in Zurich) was a German and Swiss mathematician and historian of mathematics.

See Euler's totient function and Ferdinand Rudio

Fermat number

In mathematics, a Fermat number, named after Pierre de Fermat, the first known to have studied them, is a positive integer of the form:F_.

See Euler's totient function and Fermat number

Fermat's little theorem

In number theory, Fermat's little theorem states that if is a prime number, then for any integer, the number is an integer multiple of. Euler's totient function and Fermat's little theorem are modular arithmetic.

See Euler's totient function and Fermat's little theorem

Fundamental theorem of arithmetic

In mathematics, the fundamental theorem of arithmetic, also called the unique factorization theorem and prime factorization theorem, states that every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors.

See Euler's totient function and Fundamental theorem of arithmetic

Greatest common divisor

In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. Euler's totient function and greatest common divisor are multiplicative functions.

See Euler's totient function and Greatest common divisor

Highly composite number

A highly composite number is a positive integer that has more divisors than any smaller positive integer.

See Euler's totient function and Highly composite number

Inclusion–exclusion principle

In combinatorics, a branch of mathematics, the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as where A and B are two finite sets and |S | indicates the cardinality of a set S (which may be considered as the number of elements of the set, if the set is finite).

See Euler's totient function and Inclusion–exclusion principle

Integer factorization

In number theory, integer factorization is the decomposition of a positive integer into a product of integers.

See Euler's totient function and Integer factorization

Inverse function

In mathematics, the inverse function of a function (also called the inverse of) is a function that undoes the operation of.

See Euler's totient function and Inverse function

Ivan Vinogradov

Ivan Matveevich Vinogradov (a; 14 September 1891 – 20 March 1983) was a Soviet mathematician, who was one of the creators of modern analytic number theory, and also a dominant figure in mathematics in the USSR.

See Euler's totient function and Ivan Vinogradov

James Joseph Sylvester

James Joseph Sylvester (3 September 1814 – 15 March 1897) was an English mathematician.

See Euler's totient function and James Joseph Sylvester

Jean-Louis Nicolas

Jean-Louis Nicolas is a French number theorist.

See Euler's totient function and Jean-Louis Nicolas

Jordan's totient function

In number theory, Jordan's totient function, denoted as J_k(n), where k is a positive integer, is a function of a positive integer, n, that equals the number of k-tuples of positive integers that are less than or equal to n and that together with n form a coprime set of k+1 integers Jordan's totient function is a generalization of Euler's totient function, which is the same as J_1(n). Euler's totient function and Jordan's totient function are modular arithmetic and multiplicative functions.

See Euler's totient function and Jordan's totient function

Journal of Number Theory

The Journal of Number Theory (JNT) is a monthly peer-reviewed scientific journal covering all aspects of number theory. Euler's totient function and journal of Number Theory are number theory.

See Euler's totient function and Journal of Number Theory

Lagrange's theorem (group theory)

In the mathematical field of group theory, Lagrange's theorem is a theorem that states that for any finite group, the order (number of elements) of every subgroup of divides the order of.

See Euler's totient function and Lagrange's theorem (group theory)

Lambert series

In mathematics, a Lambert series, named for Johann Heinrich Lambert, is a series taking the form It can be resummed formally by expanding the denominator: where the coefficients of the new series are given by the Dirichlet convolution of an with the constant function 1(n).

See Euler's totient function and Lambert series

Least common multiple

In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, usually denoted by, is the smallest positive integer that is divisible by both a and b. Since division of integers by zero is undefined, this definition has meaning only if a and b are both different from zero. Euler's totient function and least common multiple are number theory.

See Euler's totient function and Least common multiple

Leonhard Euler

Leonhard Euler (15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician, and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in many other branches of mathematics such as analytic number theory, complex analysis, and infinitesimal calculus.

See Euler's totient function and Leonhard Euler

Limit inferior and limit superior

In mathematics, the limit inferior and limit superior of a sequence can be thought of as limiting (that is, eventual and extreme) bounds on the sequence.

See Euler's totient function and Limit inferior and limit superior

Möbius function

The Möbius function is a multiplicative function in number theory introduced by the German mathematician August Ferdinand Möbius (also transliterated Moebius) in 1832. Euler's totient function and Möbius function are multiplicative functions.

See Euler's totient function and Möbius function

Möbius inversion formula

In mathematics, the classic Möbius inversion formula is a relation between pairs of arithmetic functions, each defined from the other by sums over divisors.

See Euler's totient function and Möbius inversion formula

MIT Press

The MIT Press is a university press affiliated with the Massachusetts Institute of Technology (MIT) in Cambridge, Massachusetts.

See Euler's totient function and MIT Press

Multiplicative function

In number theory, a multiplicative function is an arithmetic function f(n) of a positive integer n with the property that f(1). Euler's totient function and multiplicative function are multiplicative functions and number theory.

See Euler's totient function and Multiplicative function

Multiplicative group of integers modulo n

In modular arithmetic, the integers coprime (relatively prime) to n from the set \ of n non-negative integers form a group under multiplication modulo ''n'', called the multiplicative group of integers modulo n. Equivalently, the elements of this group can be thought of as the congruence classes, also known as residues modulo n, that are coprime to n. Euler's totient function and multiplicative group of integers modulo n are modular arithmetic.

See Euler's totient function and Multiplicative group of integers modulo n

Multiplicative inverse

In mathematics, a multiplicative inverse or reciprocal for a number x, denoted by 1/x or x−1, is a number which when multiplied by x yields the multiplicative identity, 1.

See Euler's totient function and Multiplicative inverse

Nikolay Korobov

Nikolai Mikhailovich Korobov (Коробов Николай Михайлович; November 23, 1917 – October 25, 2004) was a Soviet mathematician specializing in number theory and numerical analysis.

See Euler's totient function and Nikolay Korobov

Nontotient

In number theory, a nontotient is a positive integer n which is not a totient number: it is not in the range of Euler's totient function φ, that is, the equation φ(x).

See Euler's totient function and Nontotient

Number theory

Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions.

See Euler's totient function and Number theory

Order (group theory)

In mathematics, the order of a finite group is the number of its elements.

See Euler's totient function and Order (group theory)

Oxford University Press

Oxford University Press (OUP) is the publishing house of the University of Oxford.

See Euler's totient function and Oxford University Press

Phi

Phi (uppercase Φ, lowercase φ or ϕ; ϕεῖ pheî; Modern Greek: φι fi) is the twenty-first letter of the Greek alphabet.

See Euler's totient function and Phi

Pierre Wantzel

Pierre Laurent Wantzel (5 June 1814 in Paris – 21 May 1848 in Paris) was a French mathematician who proved that several ancient geometric problems were impossible to solve using only compass and straightedge.

See Euler's totient function and Pierre Wantzel

Prentice Hall

Prentice Hall was a major American educational publisher.

See Euler's totient function and Prentice Hall

Prime number

A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers.

See Euler's totient function and Prime number

Prime number theorem

In mathematics, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers.

See Euler's totient function and Prime number theorem

Primorial

In mathematics, and more particularly in number theory, primorial, denoted by "#", is a function from natural numbers to natural numbers similar to the factorial function, but rather than successively multiplying positive integers, the function only multiplies prime numbers.

See Euler's totient function and Primorial

Radical of an integer

In number theory, the radical of a positive integer n is defined as the product of the distinct prime numbers dividing n. Each prime factor of n occurs exactly once as a factor of this product: \displaystyle\mathrm(n). Euler's totient function and radical of an integer are multiplicative functions.

See Euler's totient function and Radical of an integer

Ramanujan's sum

In number theory, Ramanujan's sum, usually denoted cq(n), is a function of two positive integer variables q and n defined by the formula where (a, q). Euler's totient function and Ramanujan's sum are number theory.

See Euler's totient function and Ramanujan's sum

Riemann hypothesis

In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part.

See Euler's totient function and Riemann hypothesis

Riemann zeta function

The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s).

See Euler's totient function and Riemann zeta function

Ring (mathematics)

In mathematics, rings are algebraic structures that generalize fields: multiplication need not be commutative and multiplicative inverses need not exist.

See Euler's totient function and Ring (mathematics)

Root of unity

In mathematics, a root of unity, occasionally called a de Moivre number, is any complex number that yields 1 when raised to some positive integer power.

See Euler's totient function and Root of unity

RSA (cryptosystem)

RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem, one of the oldest widely used for secure data transmission.

See Euler's totient function and RSA (cryptosystem)

RSA problem

In cryptography, the RSA problem summarizes the task of performing an RSA private-key operation given only the public key.

See Euler's totient function and RSA problem

Schinzel's hypothesis H

In mathematics, Schinzel's hypothesis H is one of the most famous open problems in the topic of number theory.

See Euler's totient function and Schinzel's hypothesis H

Springer Publishing

Springer Publishing Company is an American publishing company of academic journals and books, focusing on the fields of nursing, gerontology, psychology, social work, counseling, public health, and rehabilitation (neuropsychology).

See Euler's totient function and Springer Publishing

Springer Science+Business Media

Springer Science+Business Media, commonly known as Springer, is a German multinational publishing company of books, e-books and peer-reviewed journals in science, humanities, technical and medical (STM) publishing.

See Euler's totient function and Springer Science+Business Media

Subgroup

In group theory, a branch of mathematics, given a group under a binary operation ∗, a subset of is called a subgroup of if also forms a group under the operation ∗.

See Euler's totient function and Subgroup

Totative

In number theory, a totative of a given positive integer is an integer such that. Euler's totient function and totative are modular arithmetic.

See Euler's totient function and Totative

Totient summatory function

In number theory, the totient summatory function \Phi(n) is a summatory function of Euler's totient function defined by: It is the number of coprime integer pairs.

See Euler's totient function and Totient summatory function

Unit (ring theory)

In algebra, a unit or invertible element of a ring is an invertible element for the multiplication of the ring.

See Euler's totient function and Unit (ring theory)

Upper and lower bounds

In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is every element of.

See Euler's totient function and Upper and lower bounds

Wacław Sierpiński

Wacław Franciszek Sierpiński (14 March 1882 – 21 October 1969) was a Polish mathematician.

See Euler's totient function and Wacław Sierpiński

See also

Leonhard Euler

Multiplicative functions

References

[1] https://en.wikipedia.org/wiki/Euler's_totient_function

Also known as Co-totient, Cototient, Euler Phi Function, Euler Totient function, Euler phi, Euler phi-function, Euler totient, Euler's phi, Euler's phi function, Euler's phi-function, Euler's totient, Euler-Totient Function, Eulers phi function, Oiler's totient function, Phi function, Totient, Totient function, Totient number, Totients, Φ function, Φ(n).

, Multiplicative group of integers modulo n, Multiplicative inverse, Nikolay Korobov, Nontotient, Number theory, Order (group theory), Oxford University Press, Phi, Pierre Wantzel, Prentice Hall, Prime number, Prime number theorem, Primorial, Radical of an integer, Ramanujan's sum, Riemann hypothesis, Riemann zeta function, Ring (mathematics), Root of unity, RSA (cryptosystem), RSA problem, Schinzel's hypothesis H, Springer Publishing, Springer Science+Business Media, Subgroup, Totative, Totient summatory function, Unit (ring theory), Upper and lower bounds, Wacław Sierpiński.