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) = 1 means that a only takes on values coprime to q. Srinivasa Ramanujan mentioned the sums in a 1918 paper. In addition to the expansions discussed in this article, Ramanujan's sums are used in the proof of Vinogradov's theorem that every sufficiently large odd number is the sum of three primes. For integers a and b, is read "a divides b" and means that there is an integer c such that Similarly, is read "a does not divide b". The summation symbol means that d goes through all the positive divisors of m, e.g. is the greatest common divisor, is Euler's totient function, is the Möbius function, and is the Riemann zeta function. These formulas come from the definition, Euler's formula and elementary trigonometric identities. and so on (, , , ,.., ,...). cq(n) is always an integer. Let Then ζq is a root of the equation xq − 1 = 0. Each of its powers, is also a root. Therefore, since there are q of them, they are all of the roots. The numbers where 1 ≤ n ≤ q are called the q-th roots of unity. ζq is called a primitive q-th root of unity because the smallest value of n that makes is q. The other primitive q-th roots of unity are the numbers where (a, q) = 1. Therefore, there are φ(q) primitive q-th roots of unity. Thus, the Ramanujan sum cq(n) is the sum of the n-th powers of the primitive q-th roots of unity. It is a fact that the powers of ζq are precisely the primitive roots for all the divisors of q. Example. Let q = 12. Then and are the primitive twelfth roots of unity, and are the primitive sixth roots of unity, and are the primitive fourth roots of unity, and are the primitive third roots of unity, is the primitive second root of unity, and is the primitive first root of unity. Therefore, if is the sum of the n-th powers of all the roots, primitive and imprimitive, and by Möbius inversion, It follows from the identity xq − 1 = (x − 1)(xq−1 + xq−2 + ...