Number theoretic functions

Math Topics A - Z listing


Number theoretic functions Topics

Sort by:

Bertelsen's number

Bertelsen's number is an erroneous name erroneously given to the erroneous value of , where is the prime counting function. This value is 56 lower than the correct value of . Ore (1988, p. 69) states that the erroneous value 478 originated in Bertelsen's application of Meissel's method in 1893 (MathPages; Prime Curios!). However, the incorrect value actually first appears in Meissel (1885) rather than Bertelsen in 1893, as correctly noted by Lagarias et al. 1985. (Note that MathPages incorrectly states that Lagarias et al. attribute the result to Bertelsen.)Unfortunately, the incorrect value has continued to be propagated in modern works such as Hardy and Wright (1979, p. 9), Davis and Hersch (1981, p. 175; but actually given correctly in the table on p. 213), Sondheimer (1981), Kramer (1983), Ore (1988, p. 77), and Cormen et al. (1990)...

Totient summatory function

The summatory function of the totient function is defined by(1)(2)(3)(4)(Hardy and Wright 1979, p. 268), plotted as the red curve above. The first values of are 1, 2, 4, 6, 10, 12, 18, 22, 28, ... (OEIS A002088). has the asymptotic series(5)(6)where is the Riemann zeta function (Perrot 1881; Nagell 1951, p. 131; Hardy and Wright 1979, p. 268; blue curve above). An improved asymptotic estimate due to Walfisz (1963) is given by(7)Consider the summatory function of ,(8)plotted as the red curve above. For , 2, ..., the first few terms are 1, 2, 5/2, 3, 13/4, 15/4, 47/12, 25/6, ... (OEIS A028415 and A048049). The sum diverges as , but Landau (1900) showed that the asymptotic behavior is given by(9)where is the Euler-Mascheroni constant,(10)(11)(12)(13)(14)(15)(OEIS A082695), is the Möbius function, is the Riemann zeta function, and is the th prime (Landau 1900; Halberstam and Richert 1974, pp. 110-111; DeKoninck..


A totative is a positive integer less than or equal to a number which is also relatively prime to , where 1 is counted as being relatively prime to all numbers. The number of totatives of is the value of the totient function .The term was popularized by Sylvester (1879; Dickson 2005, p. 124), who spelled it "totitive."


The cototient of a positive number is defined as , where is the totient function. It is therefore the number of positive integers that have at least one prime factor in common with .The first few cototients for , 2, ... are 0, 1, 1, 2, 1, 4, 1, 4, 3, 6, 1, 8, 1, 8, 7, ... (OEIS A051953).

Legendre symbol

The Legendre symbol is a number theoretic function which is defined to be equal to depending on whether is a quadratic residue modulo . The definition is sometimes generalized to have value 0 if ,(1)If is an odd prime, then the Jacobi symbol reduces to the Legendre symbol. The Legendre symbol is implemented in the Wolfram Language via the Jacobi symbol, JacobiSymbol[a, p].The Legendre symbol obeys the identity(2)Particular identities include(3)(4)(5)(6)(Nagell 1951, p. 144), as well as the general(7)when and are both odd primes.In general,(8)if is an odd prime.

Least common multiple

The least common multiple of two numbers and , variously denoted (this work; Zwillinger 1996, p. 91; Råde and Westergren 2004, p. 54), (Gellert et al. 1989, p. 25; Graham et al. 1990, p. 103; Bressoud and Wagon 2000, p. 7; D'Angelo and West 2000, p. 135; Yan 2002, p. 31; Bronshtein et al. 2007, pp. 324-325; Wolfram Language), l.c.m. (Andrews 1994, p. 22; Guy 2004, pp. 312-313), or , is the smallest positive number for which there exist positive integers and such that(1)The least common multiple of more than two numbers is similarly defined.The least common multiple of , , ... is implemented in the Wolfram Language as LCM[a, b, ...].The least common multiple of two numbers and can be obtained by finding the prime factorization of each(2)(3)where the s are all prime factors of and , and if does not occur in one factorization, then the corresponding exponent is taken as 0. The least..

Summatory function

For a discrete function , the summatory function is defined bywhere is the domain of the function.

Odd part

The odd part of a positive integer is defined bywhere is the exponent of the exact power of 2 dividing . is therefore the product of odd factors of . The values for , 2, ..., are 1, 1, 3, 1, 5, 3, 7, 1, 9, 5, 11, ... (OEIS A000265).


For a real number , the mantissa is defined as the positive fractional part , where denotes the floor function.For example, for , the mantissa is 0.14159.

Iverson bracket

Let be a mathematical statement, then the Iverson bracket is defined by(1)and corresponds to the so-called characteristic function. This notation conflicts with the brackets sometimes used to denote the floor function. (However, because of the elegant symmetry of the floor function and ceiling function symbols and , the use of to denote the floor function should be deprecated.)The Iverson bracket is implemented as a built-in function in the WolframLanguage as Boole[S].

Lamé's theorem

For , let and be integers with such that the Euclidean algorithm applied to and requires exactly division steps and such that is as small as possible satisfying these conditions. Then and , where is a Fibonacci number (Knuth 1998, p. 343).Furthermore, the number of steps in the Euclidean algorithm never exceeds 5 times the number of digits in the smaller number. In fact, the bound 5 can be further reduced to , where is the golden ratio.

Greatest common divisor theorem

There are two different statements, each separately known as the greatest common divisor theorem.1. Given positive integers and , it is possible to choose integers and such that , where is the greatest common divisor of and (Eynden 2001). 2. If and are relatively prime positive integers, then there exist positive integers and such that (Johnson 1965).

Extended greatest common divisor

The extended greatest common divisor of two integers and can be defined as the greatest common divisor of and which also satisfies the constraint for and given integers. It is used in solving linear Diophantine equations, and is implemented in the Wolfram Language as ExtendedGCD[m, n].

Bézout's identity

If and are integers not both equal to 0, then there exist integers and such thatwhere is the greatest common divisor of and .

Mangoldt function

The Mangoldt function is the function defined by(1)sometimes also called the lambda function. has the explicit representation(2)where denotes the least common multiple. The first few values of for , 2, ..., plotted above, are 1, 2, 3, 2, 5, 1, 7, 2, ... (OEIS A014963).The Mangoldt function is implemented in the WolframLanguage as MangoldtLambda[n].It satisfies the divisor sums(3)(4)(5)(6)where is the Möbius function (Hardy and Wright 1979, p. 254).The Mangoldt function is related to the Riemann zeta function by(7)where (Hardy 1999, p. 28; Krantz 1999, p. 161; Edwards 2001, p. 50).The summatory Mangoldt function, illustratedabove, is defined by(8)where is the Mangoldt function, and is also known as the second Chebyshev function (Edwards 2001, p. 51). is given by the so-called explicit formula(9)for and not a prime or prime power (Edwards 2001, pp. 49, 51, and 53), and the sum is over all nontrivial..

Class equation

Let be an order of an imaginary quadratic field. The class equation of is the equation , where is the extension field minimal polynomial of over , with the -invariant of . (If has generator , then . The degree of is equal to the class number of the field of fractions of .The polynomial is also called the class equation of (e.g., Cox 1997, p. 293).It is also true thatwhere the product is over representatives of each ideal class of .If has discriminant , then the notation is used. If is not divisible by 3, the constant term of is a perfect cube. The table below lists the first few class equations as well as the corresponding values of , with being generators of ideals in each ideal class of . In each case, the constant term is written out as a cube times a cubefree part.0..

Selberg's formula

Let be a positive number, and define(1)(2)where the sum extends over the divisors of , and is the Möbius function. Then(3)(Nagell 1951, p. 286).For , 2, ..., is given by 0, 1, 3, 7, 11, 15, 20, 25, ... (OEIS A109507), where is the nearest integer function

Liouville function

The function(1)where is the number of not necessarily distinct prime factors of , with . The values of for , 2, ... are 1, , , 1, , 1, , , 1, 1, , , ... (OEIS A008836). The values of such that are 2, 3, 5, 7, 8, 11, 12, 13, 17, 18, 19, 20, 23, ... (OEIS A026424), while then values such that are 1, 4, 6, 9, 10, 14, 15, 16, 21, 22, 24, ... (OEIS A028260).The Liouville function is implemented in the WolframLanguage as LiouvilleLambda[n].The Liouville function is connected with the Riemannzeta function by the equation(2)(Lehman 1960). It has the Lambert series(3)(4)where is a Jacobi theta function.Consider the summatory function(5)the values of which for , 2, ... are 1, 0, , 0, , 0, , , , 0, , , , , , 0, , , , , ... (OEIS A002819).Lehman (1960) gives the formulas(6)and(7)where , , and are variables ranging over the positive integers, is the Möbius function, is Mertens function, and , , and are positive real numbers with .The conjecture that satisfies for is called the..

Left factorial

The term "left factorial" is sometimes used to refer to the subfactorial , the first few values for , 2, ... are 1, 3, 9, 33, 153, 873, 5913, ... (OEIS A007489).Unfortunately, the same term and notation are also applied to the factorialsum(1)(2)(3)(4)where is a gamma function, is the exponential integral, and is the En-function.For , 1, ..., the first few values are given by 0, 1, 2, 4, 10, 34, 154, 874, ... (OEIS A003422). The left factorial is always even for . is prime for , 4, 5, 8, 9, 10, 11, 30, 76, 163, 271, 273, 354, 721, 1796, 3733, 4769, 9316, 12221, ... (OEIS A100614), the last of which was found by E. W. Weisstein (Oct. 19, 2006).

Carmichael's theorem

If and are relatively prime so that the greatest common divisor , thenwhere is the Carmichael function.

Multiplicative number theoretic function

A multiplicative number theoretic function is a number theoretic function that has the property(1)for all pairs of relatively prime positive integers and .If(2)is the prime factorization of a number , then(3)Multiplicative number theoretic functions satisfy the amazing identity(4)(5)where the product is over the primes.

Carmichael function

There are two definitions of the Carmichael function. One is the reduced totient function (also called the least universal exponent function), defined as the smallest integer such that for all relatively prime to . The multiplicative order of (mod ) is at most (Ribenboim 1989). The first few values of this function, implemented as CarmichaelLambda[n], are 1, 1, 2, 2, 4, 2, 6, 2, 6, 4, 10, ... (OEIS A002322).It is given by the formula(1)where are primaries.It can be defined recursively as(2)Some special values include(3)and(4)where is a primorial (S. M. Ruiz, pers. comm., Jul. 5, 2009).The second Carmichael's function is given by the least common multiple (LCM) of all the factors of the totient function , except that if , then is a factor instead of . The values of for the first few are 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 2, 12, ... (OEIS A011773).This function has the special value(5)for an odd prime and ...

Möbius function

The Möbius function is a number theoretic function defined by(1)so indicates that is squarefree (Havil 2003, p. 208). The first few values of are therefore 1, , , 0, , 1, , 0, 0, 1, , 0, ... (OEIS A008683). Similarly, the first few values of for , 2, ... are 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, ... (OEIS A008966).The function was introduced by Möbius (1832), and the notation was first used by Mertens (1874). However, Gauss considered the Möbius function more than 30 years before Möbius, writing "The sum of all primitive roots [of a prime number ] is either (when is divisible by a square), or (mod ) (when is the product of unequal prime numbers; if the number of these is even the sign is positive but if the number is odd, the sign is negative)" (Gauss 1801, Pegg 2003).The Möbius function is implemented in the WolframLanguage as MoebiusMu[n].The summatory function of the Möbius function(2)is called the Mertens function.The..

Dedekind sum

Given relatively prime integers and (i.e., ), the Dedekind sum is defined by(1)where(2)with the floor function. is an odd function since and is periodic with period 1. The Dedekind sum is meaningful even if , so the relatively prime restriction is sometimes dropped (Apostol 1997, p. 72). The symbol is sometimes used instead of (Beck 2000).The Dedekind sum can also be expressed in the form(3)If , let , , ..., denote the remainders in the Euclidean algorithm given by(4)(5)(6)for and . Then(7)(Apostol 1997, pp. 72-73).In general, there is no simple formula for closed-form evaluation of , but some special cases are(8)(9)(Apostol 1997, p. 62). Apostol (1997, p. 73) gives the additional special cases(10)(11)(12)(13)for and , where and . Finally,(14)for and , where or .Dedekind sums obey 2-term(15)(Dedekind 1953; Rademacher and Grosswald 1972; Pommersheim 1993; Apostol 1997, pp. 62-64) and 3-term(16)(Rademacher..

Bombieri's theorem

Define(1)where(2)(Davenport 1980, p. 121), is the Mangoldt function, and is the totient function. Now define(3)where the sum is over relatively prime to , , and(4)Bombieri's theorem then says that for fixed ,(5)provided that .

Mertens function

The Mertens function is the summary function(1)where is the Möbius function (Mertens 1897; Havil 2003, p. 208). The first few values are 1, 0, , , , , , , , , , , ... (OEIS A002321). is also given by the determinant of the Redheffer matrix.Values of for , 1, 2, ... are given by 1, , 1, 2, , , 212, 1037, 1928, , ... (OEIS A084237; Deléglise and Rivat 1996).The following table summarizes the first few values of at which for various OEIS such that 13, 19, 20, 30, 33, 43, 44, 45, 47, 48, 49, 50, ...5, 7, 8, 9, 11, 12, 14, 17, 18, 21, 23, 24, 25, 29, ...3, 4, 6, 10, 15, 16, 22, 26, 27, 28, 35, 36, 38, ...0A0284422, 39, 40, 58, 65, 93, 101, 145, 149, 150, ...1A1186841, 94, 97, 98, 99, 100, 146, 147, 148, 161, ...295, 96, 217, 229, 335, 336, 339, 340, 345, 347, 348, ...3218, 223, 224, 225, 227, 228, 341, 342, 343, 344, 346, ...An analytic formula for is not known, although Titchmarsh (1960) showed that if the Riemann hypothesis holds and if there are no multiple Riemann..

Dedekind function

The Dedekind -function is defined by the divisor product(1)where the product is over the distinct prime factors of , with the special case . The first few values are(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)giving 1, 3, 4, 6, 6, 12, 8, 12, 12, 18, ... (OEIS A001615).Sums for include(12)(13)where is the Möbius function.The Dirichlet generating functionis given by(14)(15)where is the Riemann zeta function.

Restricted divisor function

The sum of the aliquot divisors of , given bywhere is the divisor function. The first few values are 0, 1, 1, 3, 1, 6, 1, 7, 4, 8, 1, 16, ... (OEIS A001065).

Refactorable number

A number is said to be refactorable, sometimes also called a tau number (Kennedy and Cooper 1990), if it is divisible by the number of its divisors , where is the divisor function.The first few refactorable numbers are 1, 2, 8, 9, 12, 18, 24, 36, 40, 56, 60, ...(OEIS A033950).The first new such that and are both refactorable numbers are 1, 8, 1520, 50624, 62000, 103040, ... (OEIS A114617).Zelinsky (2002) proved that there are no refactorable numbers and such that and also Colton's conjecture that no three consecutive integers can all be refactorable.

Pair sum

Given an amicable pair , the quantity(1)(2)(3)is called the pair sum, where is the divisor function and is the restricted divisor function.

Odd divisor function

The odd divisor function(1)is the sum of th powers of the odd divisors of a number . It is the analog of the divisor function for odd divisors only.For the case ,(2)(3)(4)where is defined to be 0 if is odd. The generating function is given by(5)(6)(7)where is a Jacobi elliptic function.Rather surprisingly, gives the number of factors of the polynomial .The following table gives the first few .OEIS0A0012271, 1, 2, 1, 2, 2, 2, 1, 3, 2, ...1A0005931, 1, 4, 1, 6, 4, 8, 1, 13, 6, ...2A0509991, 1, 10, 1, 26, 10, 50, 1, 91, 26, ...3A0510001, 1, 28, 1, 126, 28, 344, 1, 757, 126, ...4A0510011, 1, 82, 1, 626, 82, 2402, 1, 6643, 626, ...5A0510021, 1, 244, 1, 3126, 244, 16808, 1, 59293, 3126, ...This function arises in Ramanujan's Eisenstein series and in a recurrence relation for the partition function P...

Gronwall's theorem

Let be the divisor function. Thenwhere is the Euler-Mascheroni constant. Ramanujan independently discovered a less precise version of this theorem (Berndt 1985).

Even divisor function

The sum of powers of even divisors of a number. It is the analog of the divisor function for even divisors only and is written . It is given simply in terms of the usual divisor function by(1)

Divisor product

By analogy with the divisor function , let(1)denote the product of the divisors of (including itself). For , 2, ..., the first few values are 1, 2, 3, 8, 5, 36, 7, 64, 27, 100, 11, 1728, 13, 196, ... (OEIS A007955).The divisor product satisfies the identity(2)The following table gives values of for which is a th power. Lionnet (1879) considered the case .OEIS2A0489431, 6, 8, 10, 14, 15, 16, 21, 22, 24, 26, ...3A0489441, 4, 8, 9, 12, 18, 20, 25, 27, 28, 32, ...4A0489451, 24, 30, 40, 42, 54, 56, 66, 70, 78, ...5A0489461, 16, 32, 48, 80, 81, 112, 144, 162, ...Write the prime factorization of a number ,(3)Then the power of occurring in is(4)(Kaplansky 1999). This allows rules for determining when is a power of to be determined, as considered by Halcke (1719) and Lionnet (1879). Let , , and be distinct primes, then the following table gives the conditions and first few for which is a given power of (Ireland and Rosen 1990, Kaplansky 1999, Dickson 2005). The case of third..

Divisor function

The divisor function for an integer is defined as the sum of the th powers of the (positive integer) divisors of ,(1)It is implemented in the Wolfram Language as DivisorSigma[k, n].The notations (Hardy and Wright 1979, p. 239), (Ore 1988, p. 86), and (Burton 1989, p. 128) are sometimes used for , which gives the number of divisors of . Rather surprisingly, the number of factors of the polynomial are also given by . The values of can be found as the inverse Möbius transform of 1, 1, 1, ... (Sloane and Plouffe 1995, p. 22). Heath-Brown (1984) proved that infinitely often. The numbers having the incrementally largest number of divisors are called highly composite numbers. The function satisfies the identities(2)(3)where the are distinct primes and is the prime factorization of a number .The divisor function is odd iff is a square number.The function that gives the sum of the divisors of is commonly written without the..

Dirichlet divisor problem

Let the divisor function be the number of divisors of (including itself). For a prime , . In general,where is the Euler-Mascheroni constant. Dirichlet originally gave (Hardy and Wright 1979, p. 264; Hardy 1999, pp. 67-68), and Hardy and Landau showed in 1916 that (Hardy 1999, p. 81). The following table summarizes incremental progress on the upper limit (updating Hardy 1999, p. 81).approx.citation1/20.50000Dirichlet1/30.33333Voronoi (1903), Sierpiński (1906), van der Corput (1923)37/1120.33036Littlewood and Walfisz (1925)33/1000.33000van der Corput (1922)27/820.32927van der Corput (1928)15/460.3260912/370.32432Chen (1963), Kolesnik (1969)35/1080.32407Kolesnik (1982)139/4290.32401Kolesnik17/530.32075Vinogradov (1935)7/220.31818Iwaniec and Mozzochi (1988)23/730.31507Huxley (1993)131/4160.31490Huxley (2003)..

Number theoretic character

A number theoretic character, also called a Dirichlet character (because Dirichlet first introduced them in his famous proof that every arithmetic progression with relatively prime initial term and common difference contains infinitely many primes), modulo is a complex function for positive integer such that(1)(2)(3)for all , and(4)if . can only assume values which are roots of unity, where is the totient function.Number theoretic characters are implemented in the Wolfram Language as DirichletCharacter[k, j, n], where is the modulus and is the index.

Multiplicative character

A continuous homomorphism of a group into the nonzero complex numbers. A multiplicative character gives a group representation on the one-dimensional space of complex numbers, where the group representation action by is multiplication by . A multiplicative character is unitary if it has absolute value 1 everywhere.

Hasse's resolution modulus theorem

The Jacobi symbol as a number theoretic character can be extended to the Kronecker symbol so that whenever . When is relatively prime to , then , and for nonzero values iff . In addition, is the minimum value for which the latter congruence property holds in any extension symbol for .

Dirichlet kernel

The Dirichlet kernel is obtained by integrating the number theoretic character over the ball ,

Totient valence function

is the number of integers for which the totient function , also called the multiplicity of (Guy 1994). Erdős (1958) proved that if a multiplicity occurs once, it occurs infinitely often.The values of for , 2, ... are 2, 3, 0, 4, 0, 4, 0, 5, 0, 2, 0, 6, ... (OEIS A014197), and the nonzero values are 2, 3, 4, 4, 5, 2, 6, 6, 4, 5, 2, 10, 2, 2, 7, 8, 9, ... (OEIS A058277), which occur for , 2, 4, 6, 8, 10, 12, 16, 18, 20, ... (OEIS A002202). The table below lists values for . such that 121, 2233, 4, 6445, 8, 10, 12647, 9, 14, 188515, 16, 20, 24, 3010211, 2212613, 21, 26, 28, 36, 4216617, 32, 34, 40, 48, 6018419, 27, 38, 5420525, 33, 44, 50, 6622223, 46241035, 39, 45, 52, 56, 70, 72, 78, 84, 9028229, 5830231, 6232751, 64, 68, 80, 96, 102, 12036837, 57, 63, 74, 76, 108, 114, 12640941, 55, 75, 82, 88, 100, 110, 132, 15042443, 49, 86, 9844369, 92, 13846247, 94481165, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210The smallest such that has exactly 2, 3, 4, ... solutions are given by 1,..

Totient function

The totient function , also called Euler's totient function, is defined as the number of positive integers that are relatively prime to (i.e., do not contain any factor in common with) , where 1 is counted as being relatively prime to all numbers. Since a number less than or equal to and relatively prime to a given number is called a totative, the totient function can be simply defined as the number of totatives of . For example, there are eight totatives of 24 (1, 5, 7, 11, 13, 17, 19, and 23), so .The totient function is implemented in the WolframLanguage as EulerPhi[n].The number is called the cototient of and gives the number of positive integers that have at least one prime factor in common with . is always even for . By convention, , although the Wolfram Language defines EulerPhi[0] equal to 0 for consistency with its FactorInteger[0] command. The first few values of for , 2, ... are 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, ... (OEIS A000010). The totient function is..

Madelung constants

The quantities obtained from cubic, hexagonal, etc., lattice sums, evaluated at , are called Madelung constants.For cubic lattice sums(1)the Madelung constants expressible in closed form for even indices , a few examples of which are summarized in the following table, where is the Dirichlet beta function and is the Dirichlet eta function.OEISconstant2A0860544A016639To obtain the closed form for , break up the double sum into pieces that do not include ,(2)(3)(4)where the negative sums have been reindexed to run over positive quantities. But , so all the above terms can be combined into(5)The second of these sums can be done analytically as(6)which in the case reduces to(7)The first sum is more difficult, but in the case can be written(8)Combining these then gives the original sum as(9) is given by Benson's formula (Borwein and Bailey 2003, p. 24)(10)(11)(12)(OEIS A085469), where the prime indicates thatsummation over (0, 0, 0)..

Carmichael's totient function conjecture

It is thought that the totient valence function , i.e., if there is an such that , then there are at least two solutions . This assertion is called Carmichael's totient function conjecture and is equivalent to the statement that there exists an such that (Ribenboim 1996, pp. 39-40).Dickson (2005, p. 137) states that the conjecture was proved by Carmichael (1907), who also developed a method of finding the solution (Carmichael 1909). The result also appears as in exercise in Carmichael (1914). However, Carmichael (1922) subsequently discovered an error in the proof, and the conjecture currently remains open. Any counterexample to the conjecture must have more than digits (Schlafly and Wagon 1994; conservatively given as in Conway and Guy 1996, p. 155). This result was extended by Ford (1999), who showed that any counterexample must have more than digits.Ford (1998ab) showed that if there is a counterexample to Carmichael's..

Benson's formula

An equation for a lattice sum (Borwein and Bailey 2003, p. 26)(1)(2)Here, the prime denotes that summation over (0, 0, 0) is excluded. The sum is numerically equal to (OEIS A085469), a value known as "the" Madelung constant.No closed form for is known (Bailey et al. 2006).

Tau conjecture

The tau conjecture, also known as Ramanujan's hypothesis after its proposer, states thatwhere is the tau function. This was proven by Deligne (1974) in the course of proving the more general Petersson conjecture. Deligne was awarded the Fields medal for his proof.

Star of david theorem

As originally stated by Gould (1972),(1)where GCD is the greatest common divisor and is a binomial coefficient. This was subsequently extended by D. Singmaster to(2)(Sato 1975), and generalized by Sato (1975) to(3)An even larger generalization was obtained by Hitotumatu and Sato (1975), who defined(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)with(16)and showed that each of the twelve binomial coefficients , , , , , , , , , , , and has equal greatest common divisor.A second star of David theorem states that if two triangles are drawn centered on a given element of Pascal's triangle as illustrated above, then the products of the three numbers in the associated points of each of the two stars are the same (Butterworth 2002). This follows from the fact that(17)(18)(19)The second star of David theorem holds true not only for the usual binomial coefficients, but also for q-binomial coefficients, where the common product is given by(20)In..

Euler function

The term "Euler function" may be used to refer to any of several functions in number theory and the theory of special functions, including 1. the totient function , defined as the number of positive integers that are relatively prime to , where 1 is counted as being relatively prime to all numbers; 2. the function(1)(2)(3)where and are q-Pochhammer symbols; 3. the Euler L-function , which is a special case of the Artin L-function for the polynomial and is defined by(4)where(5)(6)with a Legendre symbol.

Tau function

A function related to the divisor function , also sometimes called Ramanujan's tau function. It is defined via the Fourier series of the modular discriminant for , where is the upper half-plane, by(1)(Apostol 1997, p. 20). The tau function is also given by the Cauchyproduct(2)(3)where is the divisor function (Apostol 1997, pp. 24 and 140), , and .The tau function has generating function(4)(5)(6)(7)(8)where is a q-Pochhammer symbol. The first few values are 1, , 252, , 4830, ... (OEIS A000594). The tau function is given by the Wolfram Language function RamanujanTau[n].The series(9)is known as the tau Dirichlet series.Lehmer (1947) conjectured that for all , an assertion sometimes known as Lehmer's conjecture. Lehmer verified the conjecture for (Apostol 1997, p. 22). The following table summarizes progress on finding successively larger values of for which this condition holds.reference3316799Lehmer (1947)214928639999Lehmer..


A number is called a barrier of a number-theoretic function if, for all , . Neither the totient function nor the divisor function has a barrier.Let be an open set and , then a function is called a barrier for at a point if 1. is continuous, 2. is subharmonic on , 3. , 4. (Krantz 1999, pp. 100-101).

Kronecker symbol

The Kronecker symbol is an extension of the Jacobi symbol to all integers. It is variously written as or (Cohn 1980; Weiss 1998, p. 236) or (Dickson 2005). The Kronecker symbol can be computed using the normal rules for the Jacobi symbol(1)(2)(3)plus additional rules for ,(4)and . The definition for is variously written as(5)or(6)(Cohn 1980). Cohn's form "undefines" for singly even numbers and , probably because no other values are needed in applications of the symbol involving the binary quadratic form discriminants of quadratic fields, where and always satisfies .The Kronecker symbol is implemented in the Wolfram Language as KroneckerSymbol[n, m].The Kronecker symbol is a real number theoretic character modulo , and is, in fact, essentially the only type of real primitive character (Ayoub 1963).The illustration above and table below summarize for , 2, ... and small .OEISperiodA109017241, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1,..

Tau dirichlet series

Ramanujan's Dirichlet L-series is defined as(1)where is the tau function. Note that the notation is sometimes used instead of (Hardy 1999, p. 164). has properties analogous to the Riemann zeta function, and is implemented as RamanujanTauL[s].Ramanujan conjectured that all nontrivial zeros of lie on the line . satisfies the functional equation(2)(Hardy 1999, p. 173) and has the Euler product representation(3)for (since ) (Apostol 1997, p. 137; Hardy 1999, p. 164). can be split up into(4)where(5)(6)The functions , and are returned by the Wolfram Language commands RamanujanTauTheta[t] and RamanujanTauZ[t], respectively.Ramanujan's tau -function is a real function for real and is analogous to the Riemann-Siegel function . The number of zeros in the critical strip from to is given by(7)where is the Ramanujan theta function. Ramanujan conjectured that the nontrivial zeros of the function are all real.Ramanujan's..

Singular series

where is a Gaussian sum, and is the gamma function.

Schaar's identity

A generalization of the Gaussian sum. For and of opposite parity (i.e., one is even and the other is odd), Schaar's identity statesSchaar's identity can also be written so as to be valid for , with even.

Ramanujan's sum

The sum(1)where runs through the residues relatively prime to , which is important in the representation of numbers by the sums of squares. If (i.e., and ' are relatively prime), then(2)For argument 1,(3)where is the Möbius function. For general ,(4)where is the totient function.

Lattice sum

Cubic lattice sums include the following:(1)(2)(3)where the prime indicates that the origin , , etc. is excluded from the sum (Borwein and Borwein 1986, p. 288).These have closed forms for even ,(4)(5)(6)(7)for , where is the Dirichlet beta function, is the Dirichlet eta function, and is the Riemann zeta function (Zucker 1974, Borwein and Borwein 1987, pp. 288-301). The lattice sums evaluated at are called the Madelung constants. An additional form for is given by(8)for , where is the sum of squares function, i.e., the number of representations of by two squares (Borwein and Borwein 1986, p. 291). Borwein and Borwein (1986) prove that converges (the closed form for above does not apply for ), but its value has not been computed. A number of other related double series can be evaluated analytically.For hexagonal sums, Borwein and Borwein (1987, p. 292) give(9)where . This Madelung constant is expressible in closed..

Kloosterman's sum

Kloosterman's sum is defined by(1)where runs through a complete set of residues relatively prime to and is defined by(2)The notation is also used, at least for prime .If (if and are relatively prime), then(3)Kloosterman's sum essentially solves the problem introduced by Ramanujan of representing sufficiently large numbers by quadratic forms . Weil improved on Kloosterman's estimate for Ramanujan's problem with the best possible estimate(4)(Duke 1997).

Gaussian sum

A Gaussian sum is a sum of the form(1)where and are relatively prime integers. The symbol is sometimes used instead of . Although the restriction to relatively prime integers is often useful, it is not necessary, and Gaussian sums can be written so as to be valid for all integer (Borwein and Borwein 1987, pp. 83 and 86).If , then(2)(Nagell 1951, p. 178). Gauss showed that(3)for odd . Written explicitly(4)(Nagell 1951, p. 177).For and of opposite parity (i.e., one is even and the other is odd), Schaar's identity states(5)Such sums are important in the theory of quadraticresidues.

Dirichlet series

A serieswhere and are complex and is a monotonic increasing sequence of real numbers. The numbers are called the exponents, and are called the coefficients. When , then , the series is a normal Dirichlet L-series. The Dirichlet series is a special case of the Laplace-Stieltjes transform.


The pseudosquare modulo the odd prime is the least nonsquare positive integer that is congruent to 1 (mod 8) and for which the Legendre symbol for all odd primes . They were first considered by Kraitchik (1924, pp. 41-46), who computed all up to , and were named by Lehmer (1954). Hall (1933) showed that the values of are unbounded as .Pseudosquares arise in primality proving. Lukes et al. (1996) computed pseudosquares up to . The first few pseudosquares are 73, 241, 1009, 2641, 8089, ... (OEIS A002189). Note that the pseudosquares need not be unique so, for example, , , , and so on.

Form genus

Consider the forms for which the generic characters are equal to some preassigned array of signs or ,subject to . There are possible arrays, where is the number of distinct prime divisors of a field discriminant , and the set of forms corresponding to each array is called a genus of forms. The forms for which all are called the principal genus of forms, and each genus is also a collection of proper equivalence classes (Cohn 1980, pp. 223-224).

Mertens conjecture

Given the Mertens function defined by(1)where is the Möbius function, Stieltjes claimed in an 1885 letter to Hermite that stays within two fixed bounds, which he suggested could probably be taken to be (Havil 2003, p. 208). In the same year, Stieltjes (1885) claimed that he had a proof of the general result. However, it seems likely that Stieltjes was mistaken in this claim (Derbyshire 2004, pp. 160-161). Mertens (1897) subsequently published a paper opining based on a calculation of that Stieltjes' claim(2)for was "very probable."The Mertens conjecture has important implications, since the truth of any equalityof the form(3)for any fixed (the form of the Mertens conjecture with ) would imply the Riemann hypothesis. In fact, the statement(4)for any is equivalent to the Riemann hypothesis (Derbyshire 2004, p. 251).Mertens (1897) verified the conjecture for , and this was subsequently extended to by..

Tau function prime

is prime for , 458329, 942841, 966289, 1510441, ... (OEIS A135430). These values are also known as Lehmer-Ramanujan numbers or LR numbers since the first of them was found by Lehmer (1965). The corresponding primes have explicit values given by , , ... (OEIS A265913).It is known that if is prime, then must be an odd square.Large values of for which is a (probable) prime are summarized in the table below (Lifchitz and Lifchitz).decimal digitsdiscoverer180524N. Lygeros and O. Rozier (May 2015)258571N. Lygeros and O. Rozier (May 2015)282048N. Lygeros and O. Rozier (May 2015)498503N. Lygeros and O. Rozier (May 2015)555339N. Lygeros and O. Rozier (Sep. 2015)

Fractional part

The function giving the fractional (noninteger) part of a real number . The symbol is sometimes used instead of (Graham et al. 1994, p. 70; Havil 2003, p. 109), but this notation is not used in this work due to possible confusion with the set containing the element .Unfortunately, there is no universal agreement on the meaning of for and there are two common definitions. Let be the floor function, then the Wolfram Language command FractionalPart[x] is defined as(1)(left figure). This definition has the benefit that , where is the integer part of . Although Spanier and Oldham (1987) use the same definition as the Wolfram Language, they mention the formula only very briefly and then say it will not be used further. Graham et al. (1994, p. 70), and perhaps most other mathematicians, use the different definition(2)(right figure). Min Max Re Im The fractional part function can also be extended to the complexplane as(3)as illustrated..

Euler's totient theorem

A generalization of Fermat's little theorem. Euler published a proof of the following more general theorem in 1736. Let denote the totient function. Thenfor all relatively prime to .

Greatest common divisor

The greatest common divisor, sometimes also called the highest common divisor (Hardy and Wright 1979, p. 20), of two positive integers and is the largest divisor common to and . For example, , , and . The greatest common divisor can also be defined for three or more positive integers as the largest divisor shared by all of them. Two or more positive integers that have greatest common divisor 1 are said to be relatively prime to one another, often simply just referred to as being "relatively prime."Various notational conventions are summarized in the following table.notationsourcethis work, Zwillinger (1996, p. 91), Råde and Westergren (2004, p. 54)Gellert et al. (1989, p. 25), D'Angelo and West (1990, p. 13), Graham et al. (1990, p. 103), Bressoud and Wagon (2000, p. 7), Yan (2002, p. 30), Bronshtein et al. (2007, pp. 323-324), Wolfram Languageg.c.d.Andrews 1994,..

Class number formula

A class number formula is a finite series giving exactly the class number of a ring. For a ring of quadratic integers, the class number is denoted , where is the discriminant. A class number formula is known for the full ring of cyclotomic integers, as well as for any subring of the cyclotomic integers. This formula includes the quadratic case as well as many cubic and higher-order rings.

Even part

The even part of a positive integer is defined bywhere is the exponent of the exact power of 2 dividing . The values for , 2, ..., are 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, ... (OEIS A006519). The even part function can be implemented in the Wolfram Language as EvenPart[0]:=1 EvenPart[n_Integer]:=2^IntegerExponent[n,2]

Euclidean algorithm

The Euclidean algorithm, also called Euclid's algorithm, is an algorithm for finding the greatest common divisor of two numbers and . The algorithm can also be defined for more general rings than just the integers . There are even principal rings which are not Euclidean but where the equivalent of the Euclidean algorithm can be defined. The algorithm for rational numbers was given in Book VII of Euclid's Elements. The algorithm for reals appeared in Book X, making it the earliest example of an integer relation algorithm (Ferguson et al. 1999).The Euclidean algorithm is an example of a P-problem whose time complexity is bounded by a quadratic function of the length of the input values (Bach and Shallit 1996).Let , then find a number which divides both and (so that and ), then also divides since(1)Similarly, find a number which divides and (so that and ), then divides since(2)Therefore, every common divisor of and is a common divisor of and , so the procedure..

Sum of squares function

The number of representations of by squares, allowing zeros and distinguishing signs and order, is denoted . The special case corresponding to two squares is often denoted simply (e.g., Hardy and Wright 1979, p. 241; Shanks 1993, p. 162).For example, consider the number of ways of representing 5 as the sum of two squares:(1)(2)(3)(4)(5)(6)(7)(8)so . Similarly,(9)(10)(11)(12)(13)(14)so .The Wolfram Language function SquaresR[k, n] gives . In contrast, the function PowersRepresentations[n, k, 2] gives a list of unordered unsigned representations of as a list of squares, e.g., giving the as the only "unique" representation of 5.The function is intimately connected with the Leibniz series and with Gauss's circle problem (Hilbert and Cohn-Vossen 1999, pp. 27-39). It is also given by the inverse Möbius transform of the sequence and (Sloane and Plouffe 1995, p. 22). The average order of is , but..

Möbius inversion formula

The transform inverting the sequence(1)into(2)where the sums are over all possible integers that divide and is the Möbius function.The logarithm of the cyclotomicpolynomial(3)is closely related to the Möbius inversion formula.

Jacobi symbol

The Jacobi symbol, written or is defined for positive odd as(1)where(2)is the prime factorization of and is the Legendre symbol. (The Legendre symbol is equal to depending on whether is a quadratic residue modulo .) Therefore, when is a prime, the Jacobi symbol reduces to the Legendre symbol. Analogously to the Legendre symbol, the Jacobi symbol is commonly generalized to have value(3)giving(4)as a special case. Note that the Jacobi symbol is not defined for or even. The Jacobi symbol is implemented in the Wolfram Language as JacobiSymbol[n, m].Use of the Jacobi symbol provides the generalization of the quadraticreciprocity theorem(5)for and relatively prime odd integers with (Nagell 1951, pp. 147-148). Written another way,(6)or(7)The Jacobi symbol satisfies the same rules as the Legendresymbol(8)(9)(10)(11)(12)(13)Bach and Shallit (1996) show how to compute the Jacobi symbol in terms of the simple continued fraction of..

Integer part

The function gives the integer part of . In many computer languages, the function is denoted int(x). It is related to the floor and ceiling functions and by(1)The integer part function satisfies(2)and is implemented in the Wolfram Language as IntegerPart[x]. This definition is chosen so that , where is the fractional part. Although Spanier and Oldham (1987) use the same definition as in the Wolfram Language, they mention the formula only very briefly and then say it will not be used further. Graham et al. (1994), and perhaps most other mathematicians, use the term "integer" part interchangeably with the floor function . Min Max Re Im The integer part function can also be extended to the complexplane, as illustrated above.Since usage concerning fractional part/value and integer part/value can be confusing, the following table gives a summary of names and notations used. Here, S&O indicates Spanier and Oldham (1987).notationnameS&OGraham..

Subscribe to our updates
79 345 subscribers already with us
Math Subcategories
Check the price
for your project