Jordan's totient function

Last updated March 30, 2024

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

Definition

For each positive integer $k$ , Jordan's totient function $J_{k}$ is multiplicative and may be evaluated as

J_{k}(n)=n^{k}\prod _{p|n}\left(1-{\frac {1}{p^{k}}}\right)\,

, where

p

ranges through the prime divisors of

n

.

Properties

$\sum _{d|n}J_{k}(d)=n^{k}.\,$

which may be written in the language of Dirichlet convolutions as^[1]

J_{k}(n)\star 1=n^{k}\,

and via Möbius inversion as

J_{k}(n)=\mu (n)\star n^{k}

.

Since the Dirichlet generating function of

\mu

is

1/\zeta (s)

and the Dirichlet generating function of

n^{k}

is

\zeta (s-k)

, the series for

J_{k}

becomes

\sum _{n\geq 1}{\frac {J_{k}(n)}{n^{s}}}={\frac {\zeta (s-k)}{\zeta (s)}}

.

An average order of $J_{k}(n)$ is

J_{k}(n)\sim {\frac {n^{k}}{\zeta (k+1)}}

.

The Dedekind psi function is

\psi (n)={\frac {J_{2}(n)}{J_{1}(n)}}

,

and by inspection of the definition (recognizing that each factor in the product over the primes is a cyclotomic polynomial of

p^{-k}

), the arithmetic functions defined by

{\frac {J_{k}(n)}{J_{1}(n)}}

or

{\frac {J_{2k}(n)}{J_{k}(n)}}

can also be shown to be integer-valued multiplicative functions.

$\sum _{\delta \mid n}\delta ^{s}J_{r}(\delta )J_{s}\left({\frac {n}{\delta }}\right)=J_{r+s}(n)$ .^[2]

Order of matrix groups

The general linear group of matrices of order $m$ over $\mathbf {Z} /n$ has order^[3]

|\operatorname {GL} (m,\mathbf {Z} /n)|=n^{\frac {m(m-1)}{2}}\prod _{k=1}^{m}J_{k}(n).

The special linear group of matrices of order $m$ over $\mathbf {Z} /n$ has order

|\operatorname {SL} (m,\mathbf {Z} /n)|=n^{\frac {m(m-1)}{2}}\prod _{k=2}^{m}J_{k}(n).

The symplectic group of matrices of order $m$ over $\mathbf {Z} /n$ has order

|\operatorname {Sp} (2m,\mathbf {Z} /n)|=n^{m^{2}}\prod _{k=1}^{m}J_{2k}(n).

The first two formulas were discovered by Jordan.

Examples

Explicit lists in the OEIS are J₂ in OEIS: A007434 , J₃ in OEIS: A059376 , J₄ in OEIS: A059377 , J₅ in OEIS: A059378 , J₆ up to J₁₀ in OEIS: A069091 up to OEIS: A069095 .
Multiplicative functions defined by ratios are J₂(n)/J₁(n) in OEIS: A001615 , J₃(n)/J₁(n) in OEIS: A160889 , J₄(n)/J₁(n) in OEIS: A160891 , J₅(n)/J₁(n) in OEIS: A160893 , J₆(n)/J₁(n) in OEIS: A160895 , J₇(n)/J₁(n) in OEIS: A160897 , J₈(n)/J₁(n) in OEIS: A160908 , J₉(n)/J₁(n) in OEIS: A160953 , J₁₀(n)/J₁(n) in OEIS: A160957 , J₁₁(n)/J₁(n) in OEIS: A160960 .
Examples of the ratios J_2k(n)/J_k(n) are J₄(n)/J₂(n) in OEIS: A065958 , J₆(n)/J₃(n) in OEIS: A065959 , and J₈(n)/J₄(n) in OEIS: A065960 .

Notes

↑ Sándor & Crstici (2004) p.106
↑ Holden et al in external links. The formula is Gegenbauer's.
↑ All of these formulas are from Andrica and Piticari in #External links.

Related Research Articles

In mathematics, the Bernoulli numbers $B n$ are a sequence of rational numbers which occur frequently in analysis. The Bernoulli numbers appear in the Taylor series expansions of the tangent and hyperbolic tangent functions, in Faulhaber's formula for the sum of m-th powers of the first n positive integers, in the Euler–Maclaurin formula, and in expressions for certain values of the Riemann zeta function.

In mathematics, the gamma function is one commonly used extension of the factorial function to complex numbers. The gamma function is defined for all complex numbers except the non-positive integers. For every positive integer $n$ ,

In number theory, a multiplicative function is an arithmetic function f(n) of a positive integer n with the property that f(1) = 1 and

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

In mathematics, a square-free integer (or squarefree integer) is an integer which is divisible by no square number other than 1. That is, its prime factorization has exactly one factor for each prime that appears in it. For example, 10 = 2 ⋅ 5 is square-free, but 18 = 2 ⋅ 3 ⋅ 3 is not, because 18 is divisible by 9 = 3². The smallest positive square-free numbers are

<span class="mw-page-title-main">Euler's totient function</span> Number of integers coprime to and not exceeding n

In number theory, Euler's totient function counts the positive integers up to a given integer $n$ that are relatively prime to $n$ . It is written using the Greek letter phi as $or, and may also be called Euler's phi function . In other words, it is the number of integers k in the range 1 \leq k \leq n for which the greatest common divisor gcd(n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n .$

<span class="mw-page-title-main">Euler's constant</span> Constant value used in mathematics

Euler's 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 $log$ :

In number theory, an Euler product is an expansion of a Dirichlet series into an infinite product indexed by prime numbers. The original such product was given for the sum of all positive integers raised to a certain power as proven by Leonhard Euler. This series and its continuation to the entire complex plane would later become known as the Riemann zeta function.

<span class="mw-page-title-main">Divisor function</span> Arithmetic function related to the divisors of an integer

In mathematics, and specifically in number theory, a divisor function is an arithmetic 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 on the Riemann zeta function and the Eisenstein series of modular forms. Divisor functions were studied by Ramanujan, who gave a number of important congruences and identities; these are treated separately in the article Ramanujan's sum.

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.

A powerful number is a positive integer m such that for every prime number p dividing m, p² also divides m. Equivalently, a powerful number is the product of a square and a cube, that is, a number m of the form m = a²b³, where a and b are positive integers. Powerful numbers are also known as squareful, square-full, or 2-full. Paul Erdős and George Szekeres studied such numbers and Solomon W. Golomb named such numbers powerful.

In mathematics, the Dedekind zeta function of an algebraic number field K, generally denoted ζ_K(s), is a generalization of the Riemann zeta function (which is obtained in the case where K is the field of rational numbers Q). It can be defined as a Dirichlet series, it has an Euler product expansion, it satisfies a functional equation, it has an analytic continuation to a meromorphic function on the complex plane C with only a simple pole at s = 1, and its values encode arithmetic data of K. The extended Riemann hypothesis states that if ζ_K(s) = 0 and 0 < Re(s) < 1, then Re(s) = 1/2.

In number theory, the Dedekind psi function is the multiplicative function on the positive integers defined by

In mathematics, the multiple zeta functions are generalizations of the Riemann zeta function, defined by

In number theory, an average order of an arithmetic function is some simpler or better-understood function which takes the same values "on average".

In number theory, a cyclotomic field is a number field obtained by adjoining a complex root of unity to $Q$ , the field of rational numbers.

In mathematics, the arithmetic zeta function is a zeta function associated with a scheme of finite type over integers. The arithmetic zeta function generalizes the Riemann zeta function and Dedekind zeta function to higher dimensions. The arithmetic zeta function is one of the most-fundamental objects of number theory.

In number theory, the prime omega functions $and count the number of prime factors of a natural number Thereby counts each distinct prime factor, whereas the related function counts the total number of prime factors of honoring their multiplicity. That is, if we have a prime factorization of of the form for distinct primes, then the respective prime omega functions are given by and . These prime factor counting functions have many important number theoretic relations.$

In number theory, the totient summatory function $is a summatory function of Euler's totient function defined by:$

In number theory, the real parts of the roots of unity are related to one-another by means of the minimal polynomial of $The roots of the minimal polynomial are twice the real part of the roots of unity, where the real part of a root of unity is just with coprime with$

References

L. E. Dickson (1971) [1919]. History of the Theory of Numbers, Vol. I . Chelsea Publishing. p. 147. ISBN 0-8284-0086-5. JFM 47.0100.04.
M. Ram Murty (2001). Problems in Analytic Number Theory. Graduate Texts in Mathematics. Vol. 206. Springer-Verlag. p. 11. ISBN 0-387-95143-1. Zbl 0971.11001.
Sándor, Jozsef; Crstici, Borislav (2004). Handbook of number theory II. Dordrecht: Kluwer Academic. pp. 32–36. ISBN 1-4020-2546-7. Zbl 1079.11001.

External links

Andrica, Dorin; Piticari, Mihai (2004). "On some extensions of Jordan's arithmetic functions". Acta Universitatis Apulensis. 7: 13–22. MR 2157944.
Holden, Matthew; Orrison, Michael; Vrable, Michael. "Yet Another Generalization of Euler's Totient Function" (PDF). Archived from the original (PDF) on 2016-03-05. Retrieved 2011-12-21.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Sándor & Crstici (2004) p.106

[2] Holden et al in external links. The formula is Gegenbauer's.

[3] All of these formulas are from Andrica and Piticari in #External links.

[1]

[2]

[3]