Ramanujan's sum
In number theory, Ramanujan's sum, usually denoted "c"("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. Notation. For integers "a" and "b", formula_2 is read ""a" divides "b"" and means that there  is an integer "c" such that formula_3 Similarly, formula_4 is read ""a" does not divide "b"". The summation symbol means that "d" goes through all the positive divisors of "m", e.g. formula_7 is the greatest common divisor, formula_8 is Euler's totient function, formula_9 is the Möbius function, and formula_10 is the Riemann zeta function. Formulas for "c"("n"). Trigonometry. These formulas come from the definition, Euler's formula formula_11 and elementary trigonometric identities. and so on (, , , .., ...). "c"("n") is always an integer. Kluyver. Let formula_13 Then is a root of the equation . Each of its powers, is also a root. Therefore , since there are "q" of them, they are all of the roots. The numbers formula_15 where 1 ≤ "n" ≤ "q" are called the "q"-th roots of unity. is called a primitive "q"-th root of unity because the smallest value of "n" that makes formula_16 is "q". The other primitive "q"-th roots of unity are the numbers formula_17 where ("a", "q") = 1. Therefore, there are φ("q") primitive "q"-th roots of unity. Thus, the Ramanujan sum "c"("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 are  precisely the primitive roots for all the divisors of "q". Example. Let "q" = 12. Then 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 "x" − 1 = ("x" − 1)("x" + "x" + ... + "x" + 1) that and this leads to the formula published by Kluyver in 1906. This shows that "c"("n") is always an integer. Compare it with the formula von Sterneck. It is easily shown from the definition that "c"("n") is multiplicative when considered as a function of "q  for a fixed value of n": i.e. From the definition (or Kluyver's formula) it is straightforward to prove that, if "p" is a prime number, and if "p" is a prime power where "k" > 1, This result and the multiplicative property can be used to prove This is called von Sterneck's arithmetic function. The equivalence of it and Ramanujan's sum is due to Hölder. Other properties of "c"("n"). For all positive integers "q", For a fixed value of "q" the absolute value of the sequence formula_39 is bounded by φ("q"), and for a fixed value of  n the absolute value of the sequence formula_40 is bounded by "n". If "q" > 1 Let "m", "m" > 0, "m" = lcm("m", "m"). Then Ramanujan's sums satisfy an orthogonality property: Let "n", "k" > 0. Then known as the Brauer - Rademacher identity. If "n" > 0 and "a" is any integer, we also have due to Cohen. Ramanujan expansions. If "f"("n") is an arithmetic function (i.e. a complex-valued function of the integers or natural numbers), then a convergent infinite series of the form: or of the form: where the , is called a Ramanujan expansion of "f"("n ). Ramanujan found expansions of some of the well-known functions of number theory. All of these results are proved in an elementary" manner (i.e. only using formal manipulations of series and the simplest results about convergence). The expansion of the zero function depends on a result from the analytic theory of prime numbers, namely that the series converges to 0, and the results for "r"("n") and "r"′("n") depend on theorems in an earlier paper. All the formulas in this section are from Ramanujan's 1918 paper. Generating functions. The generating functions of the Ramanujan sums are Dirichlet series: is a  generating function for the sequence "c"(1), "c"(2), ... where "q" is kept constant, and is a generating function for the sequence "c"("n"), "c"("n"), ... where "n" is kept constant. There is also the double Dirichlet series σ("n"). σ("n") is the divisor function (i.e. the sum of the "k"-th powers of the divisors of "n", including 1 and "n"). σ("n"), the number of divisors of "n", is usually written "d"("n") and σ("n"), the sum of the divisors of "n", is usually written σ("n"). If "s" > 0, Setting "s" = 1 gives If the Riemann hypothesis is true, and formula_53 Section::::"d"("n"). "d"("n") =  σ("n") is the number of divisors of "n", including 1 and "n" itself. where γ = 0.5772... is the Euler–Mascheroni constant. Section::::"φ"("n"). Euler's totient function φ("n") is the number of positive integers less than "n" and coprime to "n". Ramanujan defines a generalization of it, if is the prime factorization of "n", and "s" is a complex number, let so that "φ"("n") = "φ"("n") is Euler's function. He proves that and uses this to show that Letting "s" = 1, Note that the constant is the inverse of the one in the formula for σ("n"). Λ("n"). Von  Mangoldt's function unless "n" = "p" is a power of a prime number, in which case it is the natural logarithm log "p". Zero. For all "n" > 0, This is equivalent to the prime number theorem. Section::::"r"("n") (sums of squares). "r"("n") is the number of way of representing "n" as the sum of 2"s" squares, counting different orders and signs as different (e.g., "r"(13) = 8, as 13 = (±2) + (±3) = (±3) + (±2).) Ramanujan defines a function δ("n") and references a paper in which he proved that "r"("n") = δ("n") for "s" = 1, 2 , 3, and 4. For "s" > 4 he shows that δ("n") is a good approximation to "r"("n"). "s" = 1 has a special formula: In the following formulas the signs repeat with a period of 4. and therefore, formula_65 (sums of triangles). formula_65 is the number of ways "n" can be represented as the sum of 2"s" triangular numbers (i.e. the numbers 1, 3 = 1 + 2, 6 = 1 + 2 + 3, 10 = 1 + 2 + 3 + 4, 15, ...; the "n"-th triangular number is given by the formula "n"("n" + 1)/2.) The analysis here  is similar to that for squares. Ramanujan refers to the same paper as he did for the squares, where he showed that there is a function formula_67 such that formula_68 for "s" = 1, 2, 3, and 4, and that for "s" > 4, formula_67 is a good approximation to formula_70 Again, "s" = 1 requires a special formula: If "s" is a multiple of 4, Therefore, Sums. Let Then for ,