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
whenever a and b are coprime.
An arithmetic function f(n) is said to be completely multiplicative (or totally multiplicative) if f(1) = 1 and f(ab) = f(a)f(b) holds for all positive integers a and b, even when they are not coprime.
Some multiplicative functions are defined to make formulas easier to write:
1(n): the constant function, defined by 1(n) = 1 (completely multiplicative)
Id(n): identity function, defined by Id(n) = n (completely multiplicative)
Idk(n): the power functions, defined by Idk(n) = nk for any complex number k (completely multiplicative). As special cases we have
Id0(n) = 1(n) and
Id1(n) = Id(n).
ε(n): the function defined by ε(n) = 1 if n = 1 and 0 otherwise, sometimes called multiplication unit for Dirichlet convolution or simply the unit function (completely multiplicative). Sometimes written as u(n), but not to be confused with μ(n) .
1C(n), the indicator function of the set C ⊂ Z, for certain sets C. The indicator function 1C(n) is multiplicative precisely when the set C has the following property for any coprime numbers a and b: the product ab is in C if and only if the numbers a and b are both themselves in C. This is the case if C is the set of squares, cubes, or k-th powers, or if C is the set of square-free numbers.
Other examples of multiplicative functions include many functions of importance in number theory, such as:
gcd(n,k): the greatest common divisor of n and k, as a function of n, where k is a fixed integer.
Euler's totient function , counting the positive integers coprime to (but not bigger than) n
μ(n): the Möbius function, the parity (−1 for odd, +1 for even) of the number of prime factors of square-free numbers; 0 if n is not square-free
σk(n): the divisor function, which is the sum of the k-th powers of all the positive divisors of n (where k may be any complex number). Special cases we have
σ0(n) = d(n) the number of positive divisors of n,
σ1(n) = σ(n), the sum of all the positive divisors of n.
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
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 ≤ k ≤ 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. For example, the totatives of n = 9 are the six numbers 1, 2, 4, 5, 7 and 8.
The Möbius function μ(n) is a multiplicative function in number theory introduced by the German mathematician August Ferdinand Möbius (also transliterated Moebius) in 1832. It is ubiquitous in elementary and analytic number theory and most often appears as part of its namesake the Möbius inversion formula. Following work of Gian-Carlo Rota in the 1960s, generalizations of the Möbius function were introduced into combinatorics, and are similarly denoted μ(x). For any positive integer n, define μ(n) as the sum of the primitive nth roots of unity.
In number theory, an arithmetic, arithmetical, or number-theoretic function is for most authors any function f(n) whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their definition the requirement that an arithmetical function "expresses some arithmetical property of n". An example of an arithmetic function is the divisor function whose value at a positive integer n is equal to the number of divisors of n.
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
This course covers methods for the analysis and control of systems with multiple inputs and outputs, which are ubiquitous in modern technology and industry. Special emphasis will be given to discrete-
We study three convolutions of polynomials in the context of free probability theory. We prove that these convolutions can be written as the expected characteristic polynomials of sums and products of unitarily invariant random matrices. The symmetric addi ...
SPRINGER HEIDELBERG2022
We prove that for any triangle-free intersection graph of n axis-parallel line segments in the plane, the independence number alpha of this graph is at least alpha n/4+ohm(root n). We complement this with a construction of a graph in this class satisfying ...
In this paper we consider two aspects of the inverse problem of how to construct merge trees realizing a given barcode. Much of our investigation exploits a recently discovered connection between the symmetric group and barcodes in general position, based ...