The discrete Fourier transform of the greatest common divisor id = "m k=1 gcd(k, m)αka m , with αm a primitive m-th root of unity, is a multiplicative function that generalizes both the gcd-sum function and Euler’s totient function. On the one hand it is the Dirichlet convolution of the identity with Ramanujan’s sum, id![a] = id ? c?(a), and on the other hand it can be written as a generalized convolution product, id![a] = id ?a Φ. We show that id counts the number of elements in the set of ordered pairs (i, j) such that i · j ≡ a mod m. Furthermore we generalize a dozen known identities for the totient function, to identities which involve the discrete Fourier transform of the greatest common divisor, including its partial sums, and its Lambert series.
展开▼
