Counting Solutions of Quadratic Congruences in Several Variables Revisited

László Tóth Department of Mathematics University of Pécs Ifjúság útja 6 7624 Pécs Hungary and Institute of Mathematics Department of Integrative Biology Universität für Bodenkultur Gregor Mendel-Straße 33 1180 Vienna Austria

                ltoth@gamma.ttk.pte.hu

Abstract

Let N_{k}(n, r, a) denote the number of incongruent solutions of the quadratic congruence a_{1}x_{1}^{2} + ⋯ + a_{k}x_{k}^{2} ≡ n (mod r), where a = (a_{1}, …, a_{k}) ∈ ℤ^{k}, n ∈ ℤ, r ∈ ℕ. We give short direct proofs for certain less known compact formulas on N_{k}(n, r, a), valid for r odd, which go back to the work of Minkowski, Bachmann and Cohen. We also deduce some other related identities and asymptotic formulas which do not seem to appear in the literature.

1 Introduction

Let k and n be positive integers and let r_{k}(n) denote the number of representations of n as a sum of k squares. More exactly, r_{k}(n) is the number of solutions (x_{1}, …, x_{k}) ∈ ℤ^{k} of the equation

x_{1}^{2} + ⋯ + x_{k}^{2} = n.  (1)

The problem of finding exact formulas or good estimates for r_{k}(n) and to study other related properties is one of the most fascinating problems in number theory. Such results were obtained by several authors, including Euler, Gauss, Liouville, Jacobi, Legendre and many others. Some of these results are now well known and are included in several textbooks. See, e.g., Grosswald [13], Hardy and Wright [14, Ch. XX], Hua [15, Ch. 8], Ireland and Rosen [17, Ch. 17], Nathanson [20, Ch. 14]. See also Dickson [10, Ch. VI–IX, XI].

For example, one has the next exact formulas. Let n be of the form n = 2^{ν}m with ν ≥ 0 and m odd. Then

r_{2}(n) = 4 ∑_{d|m}(−1)^{(d−1)/2},  (2)

r_{4}(n) = 8(2 + (−1)^{n}) ∑_{d|m} d.  (3)

Exact formulas for r_{k}(n) are known also for other values of k. These identities are, in general, more complicated for k odd than in the case of k even.

Now consider the equation (1) in the ring ℤ/rℤ of residues (mod r), where r is a positive integer. Equivalently, consider the quadratic congruence

x_{1}^{2} + ⋯ + x_{k}^{2} ≡ n (mod r),  (4)

where n ∈ ℤ. Let N_{k}(n, r) denote the number of incongruent solutions (x_{1}, …, x_{k}) ∈ ℤ^{k} of (4). The function r ↦ N_{k}(n, r) is multiplicative. Therefore, it is sufficient to consider the case r = p^{s}, a prime power. Identities for N_{k}(n, p^{s}) can be derived using Gauss and Jacobi sums. For example, we refer to the explicit formulas for N_{k}(0, p^{s}) given in [4, p. 46] and for N_{k}(1, p) given in [17, Prop. 8.6.1]. See also Dickson [10, Ch. X] for historical remarks.

Much less known is that for k even and r odd, N_{k}(n, r) can be expressed in a compact form using Ramanujan’s sum. Furthermore, for k odd, r odd and gcd(n, r) = 1, N_{k}(n, r) can be given in terms of the Möbius μ function and the Jacobi symbol. All these formulas are similar to (2) and (3). Namely, one has the following identities:

0) For k ≡ 0 (mod 4), r odd, n ∈ ℤ:

N_{k}(n, r) = r^{k−1} ∑_{d|r} \frac{c_{d}(n)}{d^{k/2}}.  (5)

1) For k ≡ 1 (mod 4), r odd, n ∈ ℤ, gcd(n, r) = 1:

N_{k}(n, r) = r^{k−1} ∑_{d|r} \frac{μ^{2}(d)}{d^{(k−1)/2}} (\frac{n}{d}) .  (6)

2) For k ≡ 2 (mod 4), r odd, n ∈ ℤ:

N_{k}(n, r) = r^{k−1} ∑_{d|r}(−1)^{(d−1)/2} \frac{c_{d}(n)}{d^{k/2}}.  (7)

3) For k ≡ 3 (mod 4), r odd, n ∈ ℤ, gcd(n, r) = 1:

N_{k}(n, r) = r^{k−1} ∑_{d|r}(−1)^{(d−1)/2} \frac{μ^{2}(d)}{d^{(k−1)/2}} (\frac{n}{d}) .  (8)

These are special cases of the identities deduced by Cohen in the paper [6] and quoted later in his papers [7, 8, 9]. The proofs given in [6] are lengthy and use the author’s previous work, although in Section 7 of [6] a direct approach using finite Fourier sums is also described. According to Cohen the formulas (5)–(8) are due in an implicit form by Minkowski [18, pp. 45–58, 166–171]. Cohen [6, p. 27] says: “We mention the work of Minkowski as an important example of the use of Fourier sums in treating quadratic congruences. While Minkowski’s approach was quite general, his results were mainly of an implicit nature.” Cohen [9] refers also to the book of Bachmann [2, Part 1, Ch. 7].

Another related compact formula, which seems to not appear in the literature is the following: If k ≡ 0 (mod 4), r is odd and n ∈ ℤ, then

N_{k}(n, r) = r^{k/2−1} ∑_{d|gcd(n,r)} d J_{k/2}(r/d),  (9)

where J_{m} is the Jordan function of order m.

It is the first main goal of the present paper to present short direct proofs of the identities (5)–(9). Slightly more generally, we will consider — as Cohen did — the quadratic congruence

a_{1}x_{1}^{2} + ⋯ + a_{k}x_{k}^{2} ≡ n (mod r),  (10)

where n ∈ ℤ, a = (a_{1}, …, a_{k}) ∈ ℤ^{k} and derive formulas for the number N_{k}(n, r, a) of incongruent solutions (x_{1}, …, x_{k}) ∈ ℤ^{k} of (10), assuming that r is odd. For the proofs we only need to express N_{k}(n, r, a) by a trigonometric sum and to use the evaluation of the Gauss quadratic sum. No properties concerning finite Fourier expansions or other algebraic arguments are needed. The proof is quite simple if k is even and somewhat more involved if k is odd. We also evaluate N_{k}(n, 2^{ν}) (ν ∈ ℕ) for certain values of k and n and consider some special cases of (10).

Our second main goal is to establish asymptotic formulas — not given in the literature, as far as we know — for the sums ∑_{r≤x} N_{k}(n, r), taken over all integers r with 1 ≤ r ≤ x, in the cases (k, n) = (1, 0), (1, 1), (2, 0), (2, 1), (3, 0), (3, 1), (4, 0), (4, 1). Similar formulas can be deduced also for other special choices of k and n. Note that the mean values of the functions r ↦ N_{k}(n, r)/n^{k−1} were investigated by Cohen [7], but only over the odd values of r.

We remark that a character free method to determine the number of solutions of the equation x^{2} + my^{2} = k in the finite field 𝔽_{p} (p prime) was presented in a recent paper by Girstmair [12].

2 Notation

Throughout the paper we use the following notation: ℕ := {1, 2, …}, ℕ_{0} := {0, 1, 2, …}; e(x) = exp(2πix); (\frac{ℓ}{r}) is the Jacobi symbol (ℓ, r ∈ ℕ, r odd), with the conventions (\frac{ℓ}{1}) = 1 (ℓ ∈ ℕ), (\frac{ℓ}{r}) = 0 if gcd(ℓ, r) > 1; c_{r}(n) denotes Ramanujan’s sum (see, e.g., [1, Ch. 8], [14, Ch. XVI]) defined as the sum of n-th powers of the primitive r-th roots of unity, i.e.,

c_{r}(n) = ∑_{\begin{matrix}j=1 \\ gcd(j,r)=1 \end{matrix}}^{r} e(jn/r) (r, n ∈ ℕ),  (11)

where c_{r}(0) = φ(r) is Euler’s function and c_{r}(1) = μ(r) is the Möbius function; S(ℓ, r) is the quadratic Gauss sum defined by

S(ℓ, r) = ∑_{j=1}^{r} e(ℓj^{2}/r) (ℓ, r ∈ ℕ, gcd(ℓ, r) = 1).  (12)

Furthermore, ∗ is the Dirichlet convolution of arithmetical functions; 1, id and id_{k} are the functions given by 1(n) = 1, id(n) = n, id_{k}(n) = n^{k} (n ∈ ℕ); τ(n) is the number of divisors of n; J_{k} = μ∗id_{k} is the Jordan function of order k, J_{k}(n) = n^{k} ∏_{p|n}(1−1/p^{k}) (n ∈ ℕ), where J_{1} = φ. Also, ψ_{k} = μ^{2} ∗ id_{k} is the generalized Dedekind function, ψ_{k}(n) = n^{k} ∏_{p|n}(1 + 1/p^{k}) (n ∈ ℕ); ζ is the Riemann zeta function; γ stands for the Euler constant; χ = χ_{4} is the nonprincipal character (mod 4) and G = L(2, χ) ≐ 0.915956 is the Catalan constant given by

G = ∑_{n=0}^{∞} \frac{(−1)^{n}}{(2n + 1)^{2}} = ∏_{p≡1 (mod 4)} (1 − \frac{1}{p^{2}} )^{−1} ∏_{p≡−1 (mod 4)} (1 + \frac{1}{p^{2}} )^{−1} .  (13)

3 General results

We evaluate N_{k}(n, r, a) using the quadratic Gauss sum S(ℓ, r) defined by (12).

Proposition 1. For every k, r ∈ ℕ, n ∈ ℤ, a = (a_{1}, …, a_{k}) ∈ ℤ^{k} we have

N_{k}(n, r, a) = r^{k−1} ∑_{d|r} \frac{1}{d^{k}} ∑_{\begin{matrix}ℓ=1 \\ (ℓ,d)=1 \end{matrix}}^{d} e(−ℓn/d)S(ℓa_{1}, d) ⋯ S(ℓa_{k}, d).

Proof. As is well known (see e.g., [19, Th. 1.31]), the number of solutions of a congruence can be expressed using the familiar identity

∑_{j=1}^{r} e(jt/r) = \begin{cases}r, & if r | t; \\ 0, & if r ∤ t. \end{cases}  (14)

valid for every r ∈ ℕ, t ∈ ℤ. In our case we obtain

N_{k}(n, r, a) = \frac{1}{r} ∑_{x_{1}=1}^{r} ⋯ ∑_{x_{k}=1}^{r} ∑_{j=1}^{r} e((a_{1}x_{1}^{2} + ⋯ + a_{k}x_{k}^{2} − n)j/r),

that is,

N_{k}(n, r, a) = \frac{1}{r} ∑_{j=1}^{r} e(−jn/r) ∑_{x_{1}=1}^{r} e(ja_{1}x_{1}^{2}/r) ⋯ ∑_{x_{k}=1}^{r} e(ja_{k}x_{k}^{2}/r).  (15)

By grouping the terms of (15) according to the values (j, r) = d with j = dℓ, (ℓ, r/d) = 1, we obtain

N_{k}(n, r, a) = \frac{1}{r} ∑_{d|r} ∑_{\begin{matrix}ℓ=1 \\ (ℓ,r/d)=1 \end{matrix}}^{r/d} e(−ℓn/(r/d)) ∑_{x_{1}=1}^{r} e(ℓa_{1}x_{1}^{2}/(r/d)) ⋯ ∑_{x_{k}=1}^{r} e(ℓa_{k}x_{k}^{2}/(r/d)), (16)

where, as it is easy to see, for every j ∈ {1, …, k},

∑_{x_{j}=1}^{r} e(ℓa_{j}x_{j}^{2}/(r/d)) = dS(ℓa_{j}, r/d).  (17)

By inserting (17) into (16) and by putting d instead of r/d, we are ready.

Proposition 2. Assume that k, r ∈ ℕ, r is odd, n ∈ ℤ and a = (a_{1}, …, a_{k}) ∈ ℤ^{k} is such that gcd(a_{1} ⋯ a_{k}, r) = 1. Then

N_{k}(n, r, a) = r^{k−1} ∑_{d|r} \frac{i^{k(d−1)^{2}/4}}{d^{k/2}} (\frac{a_{1} ⋯ a_{k}}{d} ) ∑_{\begin{matrix}ℓ=1 \\ (ℓ,d)=1 \end{matrix}}^{d} (\frac{ℓ}{d})^{k} e(−ℓn/d).  (18)

Proof. We use that for every r odd and ℓ ∈ ℕ such that gcd(ℓ, r) = 1,

S(ℓ, r) = \begin{cases}(\frac{ℓ}{r}) \sqrt{r}, & if r ≡ 1 (mod 4); \\ i (\frac{ℓ}{r}) \sqrt{r}, & if r ≡ −1 (mod 4), \end{cases}  (19)

cf., e.g., [4, Th. 1.5.2], [15, Th. 7.5.6]. Now the result follows immediately from Proposition 1.

Proposition 3. Assume that k ∈ ℕ, r = 2^{ν} (ν ∈ ℕ), n ∈ ℤ and a = (a_{1}, …, a_{k}) ∈ ℤ^{k} is such that a_{1}, …, a_{k} are odd. Then

N_{k}(n, 2^{ν}, a) = 2^{ν(k−1)} (1 + ∑_{t=1}^{⌊ν/2⌋} \frac{1}{2^{kt}} ∑_{\begin{matrix}ℓ=1 \\ ℓ odd \end{matrix}}^{2^{2t}} e(−ℓn/2^{2t})(1 + i^{ℓa_{1}}) ⋯ (1 + i^{ℓa_{k}})

+ ∑_{t=1}^{⌊(ν−1)/2⌋} \frac{1}{2^{kt}} ∑_{\begin{matrix}ℓ=1 \\ ℓ odd \end{matrix}}^{2^{2t+1}} e(−ℓn/2^{2t+1} + ℓ(a_{1} + ⋯ + a_{k})/8)) .

Proof. Using Proposition 1 and putting d = 2^{s},

N_{k}(n, 2^{ν}, a) = 2^{ν(k−1)} ∑_{s=0}^{ν} \frac{1}{2^{ks}} ∑_{\begin{matrix}ℓ=1 \\ ℓ odd \end{matrix}}^{2^{s}} e(−ℓn/2^{s})S(ℓa_{1}, 2^{s}) ⋯ S(ℓa_{k}, 2^{s}).

We apply that for every ℓ odd,

S(ℓ, 2^{ν}) = \begin{cases}0, & if ν = 1; \\ (1 + i^{ℓ})2^{ν/2}, & if ν is even; \\ 2^{(ν+1)/2}e(ℓ/8), & if ν > 1 is odd, \end{cases}

cf., e.g., [4, Th. 1.5.1, 1.5.3], [15, Th. 7.5.7]. Separating the terms corresponding to s = 2t even and s = 2t + 1 odd, respectively we obtain the given formula.

4 The case k even, r odd

Suppose that k is even and r is odd. In this case we deduce for N_{k}(n, r, a) formulas in terms of the Ramanujan sums.

Proposition 4. ([6, Th. 11 and Eq. (5.2)]) Assume that k = 2m (m ∈ ℕ), r ∈ ℕ is odd, n ∈ ℤ, a = (a_{1}, …, a_{k}) ∈ ℤ^{k}, gcd(a_{1} ⋯ a_{k}, r) = 1. Then

N_{2m}(n, r, a) = r^{2m−1} ∑_{d|r} \frac{c_{d}(n)}{d^{m}} (\frac{(−1)^{m}a_{1} ⋯ a_{2m}}{d} ) .

Proof. This is a direct consequence of Proposition 2. For k even the inner sum of (18) is exactly c_{d}(n), by its definition (11), and applying that (\frac{−1}{d}) = (−1)^{(d−1)/2} the proof is complete.

In the special case k = 2, a_{1} = 1, a_{2} = −D, r odd, gcd(D, r) = gcd(n, r) = 1 Proposition 4 was deduced by Rabin and Shallit [21, Lemma 3.2].

Corollary 5. If k = 4m (m ∈ ℕ), r ∈ ℕ is odd, n ∈ ℤ and a_{1} ⋯ a_{k} = 1 (in particular a_{1} = ⋯ = a_{k} = 1), then

N_{4m}(n, r, a) = r^{4m−1} ∑_{d|r} \frac{c_{d}(n)}{d^{2m}}.

Corollary 6. If k = 4m + 2 (m ∈ ℕ_{0}), r ∈ ℕ is odd, n ∈ ℤ and a_{1} ⋯ a_{k} = 1 (in particular a_{1} = ⋯ = a_{k} = 1), then

N_{4m+2}(n, r, a) = r^{4m+1} ∑_{d|r}(−1)^{(d−1)/2} \frac{c_{d}(n)}{d^{2m+1}} .  (20)

Therefore, the identities (5) and (7) are proved. In particular, the next simple formulas are valid: for every r odd,

N_{2}(0, r) = r ∑_{d|r}(−1)^{(d−1)/2} \frac{φ(d)}{d},  (21)

N_{4}(1, r) = r^{3} ∑_{d|r} \frac{μ(d)}{d^{2}} = rJ_{2}(r).  (22)

Remark 7. In the case k even and a_{1} = ⋯ = a_{k} = 1 for the proof of Proposition 4 it is sufficient to use the formula S^{2}(ℓ, r) = (−1)^{(r−1)/2}r (r odd, gcd(ℓ, r) = 1) instead of the much deeper result (19) giving the precise value of S(ℓ, r).

In the case k = 4m and a_{1} ⋯ a_{k} = 1 the next representation holds as well (already given in (9) in the case a_{1} = ⋯ = a_{k} = 1).

Corollary 8. If k = 4m (m ∈ ℕ), r ∈ ℕ is odd, n ∈ ℤ and a_{1} ⋯ a_{k} = 1 (in particular a_{1} = ⋯ = a_{k} = 1), then

N_{4m}(n, r, a) = r^{2m−1} ∑_{d|gcd(n,r)} d J_{2m}(r/d).  (23)

Proof. We use Corollary 5 and apply that for every fixed n, c.(n) = μ ∗ η.(n), where η_{r}(n) = r if r | n and 0 otherwise. Therefore,

N_{4m}(n, r, a) = r^{2m−1} ∑_{d|r} c_{d}(n)(r/d)^{2m}

= r^{2m−1} (c.(n) ∗ id_{2m}) (r) = r^{2m−1} (μ ∗ id_{2m} ∗η.(n)) (r) = r^{2m−1} (J_{2m} ∗ η.(n)) (r)

= r^{2m−1} ∑_{d|gcd(n,r)} d J_{2m}(r/d).

Remark 9. The identity (23) shows that for every r odd, the function n ↦ N_{4m}(n, r) is even (mod r). We recall that an arithmetic function n ↦ f(n) is said to be even (mod r) if f(n) = f(gcd(n, r)) holds for every n ∈ ℕ. We refer to [24] for this notion. In fact, for every k even the function n ↦ N_{k}(n, r, a) is even (mod r), where r is a fixed odd number and gcd(a_{1} ⋯ a_{k}, r) = 1, since according to Proposition 4, N_{k}(n, r, a) is a linear combination of the values c_{d}(r) with d | r. See also [8].

A direct consequence of (23) is the next result:

Corollary 10. If k = 4m (m ∈ ℕ), r ∈ ℕ is odd, n ∈ ℤ such that gcd(n, r) = 1, then

N_{4m}(n, r) = r^{2m−1}J_{2m}(r) = r^{4m−1} ∏_{p|r} (1 − \frac{1}{p^{2m}} ) .

Another consequence of Proposition 4 is the following identity, of which proof is similar to the proof of Corollary 8:

Corollary 11. If k = 4m + 2 (m ∈ ℕ_{0}), r ∈ ℕ is odd, n ∈ ℤ and a_{1} ⋯ a_{k} = −1, then

N_{4m+2}(n, r, a) = r^{2m} ∑_{d|gcd(n,r)} d J_{2m+1}(r/d).

In the case r = p^{ν} (p > 2 prime) and for special choices of k and n one can deduce explicit formulas from the identities of above. For example (as is well known):

Corollary 12. For every prime p > 2 and every n ∈ ℕ,

N_{2}(n, p) = \begin{cases}2p − 1, & if p | n, p ≡ 1 (mod 4); \\ 1, & if p | n, p ≡ −1 (mod 4); \\ p − 1, & if p ∤ n, p ≡ 1 (mod 4); \\ p + 1, & if p ∤ n, p ≡ −1 (mod 4), \end{cases}

N_{2}(n, p^{2}) = \begin{cases}p(p − 1), & if p ∤ n, p ≡ 1 (mod 4); \\ 2p(p − 1), & if p | n, p^{2} ∤ n, p ≡ 1 (mod 4); \\ 3p^{2} − 2p, & if p^{2} | n, p ≡ 1, (mod 4); \\ p(p + 1), & if p ∤ n, p ≡ −1 (mod 4); \\ 0, & if p | n, p^{2} ∤ n, p ≡ −1 (mod 4); \\ p^{2}, & if p^{2} | n, p ≡ −1 (mod 4). \end{cases}

5 The case k odd, r odd

Now consider the case k odd, r odd. In order to apply Proposition 2 we need to evaluate the character sum

T (n, r) = ∑_{\begin{matrix}j=1 \\ gcd(j,r)=1 \end{matrix}}^{r} (\frac{j}{r}) e(jn/r).

Lemma 13. Let r, n ∈ ℕ, r odd such that gcd(n, r) = 1.

i) If r is squarefree, then

T (n, r) = \begin{cases}(\frac{n}{r}) \sqrt{r}, & if r ≡ 1 (mod 4); \\ i (\frac{n}{r}) \sqrt{r}, & if r ≡ −1 (mod 4). \end{cases}  (24)

ii) If r is not squarefree, then T (n, r) = 0.

Proof. For every r odd the Jacobi symbol j ↦ (\frac{j}{r}) is a real character (mod r) and T (n, r) = (\frac{n}{r}) T (1, r) holds if gcd(n, r) = 1. See, e.g., [15, Ch. 7].

i) If r is squarefree, then j ↦ (\frac{j}{r}) is a primitive character (mod r). Thus, T (1, r) = \sqrt{r} for (\frac{−1}{r}) = 1 and T (1, r) = i\sqrt{r} for (\frac{−1}{r}) = −1 ([15, Th. 7.5.8]), giving (24).

ii) We show that if r is not squarefree, then T (1, r) = 0. Here r can be written as r = p^{2}s, where p is a prime and by putting j = ks + q,

T (1, r) = ∑_{q=1}^{s} ∑_{k=0}^{p^{2}−1} (\frac{ks + q}{r} ) e((ks + q)/r),

where

(\frac{ks + q}{r} ) = (\frac{ks + q}{p^{2}} ) (\frac{ks + q}{s} ) = (\frac{q}{s})

and deduce

T (1, r) = ∑_{q=1}^{s} (\frac{q}{s}) e(q/(p^{2}s)) ∑_{k=0}^{p^{2}−1} e(k/p^{2}) = 0,

since the inner sum is zero using (14).

Note that properties of the sum T (n, r), including certain orthogonality results were obtained by Cohen [6] using different arguments.

Proposition 14. ([6, Cor. 2]) Assume that k = 2m + 1 (m ∈ ℕ_{0}), r ∈ ℕ is odd, n ∈ ℤ such that gcd(n, r) = 1, a = (a_{1}, …, a_{k}) ∈ ℤ^{k}, gcd(a_{1} ⋯ a_{k}, r) = 1. Then

N_{2m+1}(n, r, a) = r^{2m} ∑_{d|r} \frac{μ^{2}(d)}{d^{m}} (\frac{(−1)^{m}na_{1} ⋯ a_{2m+1}}{d} ) .

Proof. Apply Proposition 2. For k odd the inner sum of (18) is T (−n, d), where T (n, r) is given by (24). Since r is odd and gcd(n, r) = 1, if d | r, then d is also odd and gcd(d, r) = 1.

We deduce by Lemma 13 that

N_{k}(n, r, a) = r^{k−1} ∑_{d|r} \frac{i^{k(d−1)^{2}/4}}{d^{k/2}} (\frac{a_{1} ⋯ a_{k}}{d} ) T (−n, d)

= r^{k−1} ∑_{d|r ; d squarefree} \frac{i^{k(d−1)^{2}/4}}{d^{k/2}} (\frac{a_{1} ⋯ a_{k}}{d} ) i^{(d−1)^{2}/4} (\frac{−n}{d}) \sqrt{d}

= r^{k−1} ∑_{d|r} \frac{μ^{2}(d)}{d^{(k−1)/2}} i^{(k+1)(d−1)^{2}/4} (\frac{−na_{1} ⋯ a_{k}}{d} ) ,

which gives the result by evaluating the powers of i. Corollary 15. If k = 4m+1 (m ∈ ℕ_{0}), r ∈ ℕ is odd, n ∈ ℤ, gcd(n, r) = 1 and a_{1} ⋯ a_{k} = 1 (in particular if a_{1} = ⋯ = a_{k} = 1), then

N_{4m+1}(n, r, a) = r^{4m} ∑_{d|r} \frac{μ^{2}(d)}{d^{2m}} (\frac{n}{d}) .

Corollary 16. If k = 4m+3 (m ∈ ℕ_{0}), r ∈ ℕ is odd, n ∈ ℤ, gcd(n, r) = 1 and a_{1} ⋯ a_{k} = 1 (in particular if a_{1} = ⋯ = a_{k} = 1), then

N_{4m+3}(n, r, a) = r^{4m+2} ∑_{d|r} \frac{μ^{2}(d)}{d^{2m+1}} (−1)^{(d−1)/2} (\frac{n}{d}) .

This proves the identities (6) and (8). Corollary 17. If k = 4m + 3 (m ∈ ℕ_{0}), r ∈ ℕ is odd, n ∈ ℤ, gcd(n, r) = 1 and a_{1} ⋯ a_{k} = −1, then

N_{4m+3}(n, r, a) = r^{2m+1}ψ_{2m+1}(r).

To prove the next result we need the evaluation of

V (r) = T (0, r) = ∑_{\begin{matrix}j=1 \\ gcd(j,r)=1 \end{matrix}}^{r} (\frac{j}{r}) ,

not given by Lemma 13. Lemma 18. If r ∈ ℕ is odd, then

V (r) = \begin{cases}φ(r), & if r is a square; \\ 0, & otherwise. \end{cases}

Proof. If r = t^{2} is a square, then (\frac{j}{r}) = (\frac{j}{t^{2}} ) = 1 for every j with gcd(j, r) = 1 and deduce that V (r) = φ(r).

Now assume that r is not a square. Then, since r is odd, there is a prime p > 2 such that r = p^{ν}s, where ν is odd and gcd(p, s) = 1. First we show that there exists an integer j_{0} such that (j_{0}, r) = 1 and (\frac{j_{0}}{r} ) = −1. Indeed, let c be a quadratic nonresidue (mod p) and consider the simultaneous congruences x ≡ c (mod p), x ≡ 1 (mod s). By the Chinese remainder theorem there exists a solution x = j_{0} satisfying

(\frac{j_{0}}{r} ) = (\frac{j_{0}}{p} )^{ν} (\frac{j_{0}}{s} ) = (\frac{c}{p})^{ν} (\frac{1}{s}) = (−1)^{ν} = −1,

since ν is odd. Hence

V (r) = ∑_{\begin{matrix}j=1 \\ gcd(j,r)=1 \end{matrix}}^{r} (\frac{jj_{0}}{r} ) = ∑_{\begin{matrix}j=1 \\ gcd(j,r)=1 \end{matrix}}^{r} (\frac{j}{r}) (\frac{j_{0}}{r} ) = − ∑_{\begin{matrix}j=1 \\ gcd(j,r)=1 \end{matrix}}^{r} (\frac{j}{r}) = −V (r),

giving that V (r) = 0.

Proposition 19. ([6, Cor. 1]) Assume that k, r ∈ ℕ are odd, n = 0 and a = (a_{1}, …, a_{k}) ∈ ℤ^{k}, gcd(a_{1} ⋯ a_{k}, r) = 1. Then

N_{k}(0, r, a) = r^{k−1} ∑_{d^{2}|r} \frac{φ(d)}{d^{k−1}},

which does not depend on a.

Proof. From Proposition 2 we have

N_{k}(0, r, a) = r^{k−1} ∑_{d|r} \frac{i^{k(d−1)^{2}/4}}{d^{k/2}} (\frac{a_{1} ⋯ a_{k}}{d} ) V (d),

where V (d) is given by Lemma 18. We deduce

N_{k}(0, r, a) = r^{k−1} ∑_{d^{2}|r} \frac{i^{k(d^{2}−1)^{2}/4}}{d^{k}} (\frac{a_{1} ⋯ a_{k}}{d^{2}} ) φ(d^{2}) = r^{k−1} ∑_{d^{2}|r} \frac{φ(d^{2})}{d^{k}}.

Remark 20. For all the results of this section it was assumed that gcd(n, r) = 1. See [9] for certain special cases of gcd(n, r) > 1.

6 The case k even, r = 2^{ν}

In this section let a_{1} = ⋯ = a_{k} = 1.

Proposition 21. If k ∈ ℕ is even and n ∈ ℤ is odd, then N_{k}(n, 2) = 2^{k−1} and for every ν ∈ ℕ, ν ≥ 2,

N_{k}(n, 2^{ν}) = 2^{ν(k−1)} (1 − \frac{1}{2^{k/2−1}} cos (\frac{kπ}{4} + \frac{nπ}{2} )) .

Proof. We obtain from Proposition 3 by separating the terms according to ℓ = 4u + 1 and ℓ = 4u + 3, respectively,

N_{k}(n, 2^{ν}) = 2^{ν(k−1)} (1 + ∑_{t=1}^{⌊ν/2⌋} \frac{1}{2^{kt}} A_{t} + ∑_{t=1}^{⌊(ν−1)/2⌋} \frac{1}{2^{kt}} B_{t}) ,

where

A_{t} = (1 + i)^{k} ∑_{u=0}^{2^{2t−2}−1} e(−(4u + 1)n/2^{2t}) + (1 − i)^{k} ∑_{u=0}^{2^{2t−2}−1} e(−(4u + 3)n/2^{2t})

= ((1 + i)^{k}e(−n/2^{2t}) + (1 − i)^{k}e(−3n/2^{2t})) ∑_{u=0}^{2^{2t−2}−1} e(−un/2^{2t−2}),

and

B_{t} = ∑_{u=0}^{2^{2t−1}−1} (e(−(4u + 1)n/2^{2t+1} + (4u + 1)k/8) + e(−(4u + 3)n/2^{2t+1} + (4u + 3)k/8))

= (e(k/8 − n/2^{2t+1}) + e(3k/8 − 3n/2^{2t+1})) ∑_{u=0}^{2^{2t−1}−1} e(−un/2^{2t−1} + ku/2).

Since n is odd, n/2^{2t−2} ∉ ℤ for every t ≥ 2. It follows that A_{t} = 0 for every t ≥ 2. Also,

A_{1} = (1 + i)^{k}e(−n/4) + (1 − i)^{k}e(−3n/4) = −2^{k/2+1} cos(kπ/4 + nπ/2).

Similarly, since k is even and n is odd, k/2 − n/2^{2t−1} ∉ ℤ for every t ≥ 1. It follows that B_{t} = 0 for every t ≥ 1. This completes the proof.

Corollary 22. If k = 4m (m ∈ ℕ) and n ∈ ℤ is odd, then for every ν ∈ ℕ,

N_{4m}(n, 2^{ν}) = 2^{ν(4m−1)}.

Corollary 23. If k = 4m+2 (m ∈ ℕ_{0}) and n = 2t+1 ∈ ℤ is odd, then N_{4m+2}(n, 2) = 2^{4m+1} and for every ν ≥ 2,

N_{4m+2}(n, 2^{ν}) = 2^{ν(4m+1)} (1 + \frac{(−1)^{m+t}}{2^{2m}} ) .

By similar arguments one can deduce from Proposition 3:

Proposition 24. ([4, p. 46]) If k = 4m (m ∈ ℕ) and n = 0, then for every ν ∈ ℕ,

N_{4m}(0, 2^{ν}) = 2^{ν(4m−1)} (1 + \frac{(−1)^{m}(2^{(ν−1)(2m−1)} − 1)}{2^{(ν−1)(2m−1)}(2^{2m−1} − 1)}) .

Proposition 25. ([4, p. 46]) If k = 4m + 2 (m ∈ ℕ_{0}) and n = 0 for every ν ∈ ℕ,

N_{4m+2}(0, 2^{ν}) = 2^{ν(4m+1)}.

7 The case k odd, r = 2^{ν}

Now let k be odd, r = 2^{ν}, a_{1} = ⋯ = a_{k} = 1. By similar arguments as in the previous sections we have

Proposition 26. ([4, p. 46]) If k ∈ ℕ is odd and n = 0, then for every ν ∈ ℕ,

N_{k}(0, 2^{ν}) = 2^{ν(k−1)} (1 + \frac{(−1)^{(k^{2}−1)/8} · (2^{(k−2)⌊ν/2⌋} − 1)}{2^{(k−2)⌊ν/2⌋−(k−3)/2}(2^{k−2} − 1)}) .

Other cases can also be considered, for example:

Proposition 27. If k = 4m + 3 and n = 4t + 1 (m, n ∈ ℕ_{0}), then for every ν ∈ ℕ,

N_{4m+3}(n, 2^{ν}) = 2^{ν(4m+2)} (1 + \frac{(−1)^{m}}{2^{2m+1}} ) .

8 Special cases

In this section we consider some special cases and deduce asymptotic formulas for k = 1, 2, 3, 4 and a = (1, …, 1).

8.1 The congruence x^{2} ≡ 0 (mod r)

For k = 1 and n = 0 we have the congruence x^{2} ≡ 0 (mod r). Its number of solutions, N_{1}(0, r) is the sequence \underline{A000188} in [22]. It is well known and can be deduced directly that N_{1}(0, p^{ν}) = p^{⌊ν/2⌋} for every prime power p^{ν} (ν ∈ ℕ). This leads to the Dirichlet series representation

∑_{r=1}^{∞} \frac{N_{1}(0, r)}{r^{s}} = \frac{ζ(2s − 1)ζ(s)}{ζ(2s)}.  (25)

Our next result corresponds to the classical asymptotic formula of Dirichlet

∑_{n≤x} τ(n) = x log x + (2γ − 1)x + O(x^{1/2}).

Proposition 28. We have

∑_{r≤x} N_{1}(0, r) = \frac{3}{π^{2}} x log x + cx + O(x^{2/3}),  (26)

where c = \frac{3}{π^{2}} (3γ − 1 − \frac{2ζ′(2)}{ζ(2)}).

Proof. By the identity (25) we infer that for every r ∈ ℕ,

N_{1}(0, r) = ∑_{a^{2}b^{2}c=r} μ(a)b.

Using Dirichlet’s hyperbola method we have

E(x) := ∑_{b^{2}c≤x} b = ∑_{b≤x^{1/3}} b ∑_{c≤x/b^{2}} 1 + ∑_{c≤x^{1/3}} ∑_{b≤(x/c)^{1/2}} b − ∑_{b≤x^{1/3}} b ∑_{c≤x^{1/3}} 1,

which gives by the trivial estimate (i.e., |x − ⌊x⌋| < 1),

E(x) = \frac{1}{2}x log x + \frac{1}{2}(3γ − 1)x + O(x^{2/3}).

Now,

∑_{r≤x} N_{1}(0, r) = ∑_{a≤x^{1/2}} μ(a)E(x/a^{2})

and easy computations complete the proof.

Remark 29. The error term of (26) can be improved by the method of exponential sums (see, e.g., [5, Ch. 6]). Namely, it is O(x^{2/3−δ}) for some explicit δ with 0 < δ < 1/6.

8.2 The congruence x^{2} ≡ 1 (mod r)

It is also well known, that in the case k = 1 and n = 1 for the number of solutions of the congruence x^{2} ≡ 1 (mod r) one has N_{1}(1, p^{ν}) = 2 for every prime p > 2 and every ν ∈ ℕ, N_{1}(1, 2) = 1, N_{1}(1, 4) = 2, N_{1}(1, 2^{ν}) = 4 for every ν ≥ 3 (sequence \underline{A060594} in [22]). The Dirichlet series representation

∑_{r=1}^{∞} \frac{N_{1}(1, r)}{r^{s}} = \frac{ζ^{2}(s)}{ζ(2s)} (1 − \frac{1}{2^{s}} + \frac{2}{2^{2s}} )  (27)

shows that estimating the sum ∑_{r≤x} N_{1}(1, r) is closely related to the squarefree divisor problem. Let τ^{(2)}(n) = 2^{ω(n)} denote the number of squarefree divisors of n. Then

∑_{n=1}^{∞} \frac{τ^{(2)}(n)}{n^{s}} = \frac{ζ^{2}(s)}{ζ(2s)}.  (28)

By this analogy we deduce Proposition 30.

∑_{r≤x} N_{1}(1, r) = \frac{6}{π^{2}} x log x + c_{1}x + O(x^{1/2} exp(−c_{0}(log x)^{3/5}(log log x)^{−1/5})),

where c_{0} > 0 is a constant and c_{1} = \frac{6}{π^{2}} (2γ − 1 − \frac{log 2}{2} − \frac{2ζ′(2)}{ζ(2)}). If the Riemann hypothesis

(RH) is true, then the error term is O(x^{4/11+ε}) for every ε > 0.

Proof. By the identities (27) and (28) it follows that for every r ∈ ℕ,

N_{1}(1, r) = ∑_{ab=r} τ^{(2)}(a)h(b),

where the multiplicative function h is defined by

h(p^{ν}) = \begin{cases}−1, & if p = 2, ν = 1; \\ 2, & if p = 2, ν = 2; \\ 0, & otherwise. \end{cases}

Now the convolution method and the result

∑_{n≤x} τ^{(2)}(n) = \frac{6}{π^{2}} x (log x + 2γ − 1 − \frac{2ζ′(2)}{ζ(2)}) + O(R(x)),

where R(x) ≪ x^{1/2} exp(−c_{0}(log x)^{3/5}(log log x)^{−1/5}) (see [23]) conclude the proof. If RH is true, then the estimate R(x) ≪ x^{4/11+ε} due to Baker [3] can be used.

Remark 31. See [11] for asymptotic formulas on the number of solutions of the higher degree congruences x^{ℓ} ≡ 0 (mod n) and x^{ℓ} ≡ 1 (mod n), respectively, where ℓ ∈ ℕ. The results of our Propositions 28 and 30 are better than those of [11] applied for ℓ = 2.

8.3 The congruence x^{2} + y^{2} ≡ 0 (mod r)

This is the case k = 2, n = 0. N_{2}(0, r) is the sequence \underline{A086933} in [22] and for r odd it is given by (21). Furthermore, N_{2}(0, 2^{ν}) is given by Proposition 25. We deduce

Corollary 32. For every prime power p^{ν} (ν ∈ ℕ),

N_{2}(0, p^{ν}) = \begin{cases}p^{ν}(ν + 1 − ν/p), & if p ≡ 1 (mod 4), ν ≥ 1; \\ p^{ν}, & if p ≡ −1 (mod 4), ν is even; \\ p^{ν−1}, & if p ≡ −1 (mod 4), ν is odd; \\ 2^{ν}, & if p = 2, ν ≥ 1. \end{cases}

Corollary 33. N_{2}(0,.) = id ·(1 ∗ χ) ∗ μχ, where χ is the nonprincipal character (mod 4).

Proof. From Corollary 32 we obtain the Dirichlet series representation

∑_{r=1}^{∞} \frac{N_{2}(0, r)}{r^{s}} = ζ(s − 1) ∏_{p>2} (1 − \frac{(−1)^{(p−1)/2}}{p^{s}} ) (1 − \frac{(−1)^{(p−1)/2}}{p^{s−1}} )^{−1}

= ζ(s − 1)L(s − 1, χ)L(s, χ)^{−1},

where L(s, χ) is the Dirichlet series of χ. This gives the result.

Observe that 4(1 ∗ χ)(n) = r_{2}(n) is the number of ways n can be written as a sum of two squares, quoted in the Introduction. This shows that the sum ∑_{r≤x} N_{2}(0, r) is closely related to the Gauss circle problem. The next result corresponds to the asymptotic formula due to Huxley [16]

∑_{n≤x} r_{2}(n) = πx + O(x^{a}(log x)^{b}),  (29)

where a = 131/416 ≐ 0.314903 and b = 26947/8320.

Proposition 34. We have

∑_{r≤x} N_{2}(0, r) = \frac{π}{8G}x^{2} + O(x^{a+1}(log x)^{b}),

where G is the Catalan constant defined by (13).

Proof. Since N_{2}(0,.) = (id · r_{2}/4) ∗ (μχ), we have

∑_{r≤x} N_{2}(0, r) = \frac{1}{4} ∑_{d≤x} μ(d)χ(d) ∑_{n≤x/d} nr_{2}(n).

Now partial summation on (29) and usual estimates give the result.

8.4 The congruence x^{2} + y^{2} ≡ 1 (mod r)

This is the case k = 2, n = 1. N_{2}(1, r) is sequence \underline{A060968} in [22]. For every r odd we have by (20),

N_{2}(1, r) = r ∑_{d|r}(−1)^{(d−1)/2} \frac{μ(d)}{d},

and deduce (cf. Corollary 23).

Corollary 35. For every prime power p^{ν} (ν ∈ ℕ),

N_{2}(1, p^{ν}) = \begin{cases}p^{ν}(1 − 1/p), & if p ≡ 1 (mod 4), ν ≥ 1; \\ p^{ν}(1 + 1/p), & if p ≡ −1 (mod 4), ν ≥ 1; \\ 2, & if p = 2, ν = 1; \\ 2^{ν+1}, & if p = 2, ν ≥ 2. \end{cases}

Proposition 36. We have

∑_{r≤x} N_{2}(1, r) = \frac{5}{8G}x^{2} + O(x log x).

Proof. One has the Dirichlet series representation

∑_{r=1}^{∞} \frac{N_{2}(1, r)}{r^{s}} = ζ(s − 1) (1 + \frac{4}{2^{2s}} ) L(s, χ)^{−1},

and the asymptotic formula is obtained by usual elementary arguments.

8.5 The congruence x^{2} + y^{2} + z^{2} ≡ 0 (mod r)

This is the case k = 3, n = 0. N_{3}(0, r) is the sequence \underline{A087687} in [22]. By Proposition 19 we have for every r ∈ ℕ odd,

N_{3}(0, r) = r^{2} ∑_{d^{2}|r} \frac{φ(d)}{d^{2}}  (30)

and using also Proposition 26 we deduce Corollary 37. For every prime power p^{ν} (ν ∈ ℕ),

N_{3}(0, p^{ν}) = \begin{cases}p^{3β−1}(p^{β+1} + p^{β} − 1), & if p > 2, ν = 2β is even; \\ p^{3β−2}(p^{β} + p^{β−1} − 1), & if p > 2, ν = 2β − 1 is odd; \\ 2^{3β}, & if p = 2, ν = 2β is even; \\ 2^{3β−1}, & if p = 2, ν = 2β − 1 is odd. \end{cases}

Proposition 38.

∑_{r≤x} N_{3}(0, r) = \frac{24ζ(3)}{π^{4}}x^{3} + O(x^{2} log x).

Proof. The Dirichlet series of the function r ↦ N_{3}(0, r) is

∑_{r=1}^{∞} \frac{N_{3}(0, r)}{r^{s}} = ζ(s − 2)G(s),

where

G(s) = \frac{ζ(2s − 3)}{ζ(2s − 2)} \frac{2^{2s} − 16}{2^{2s} − 4}  (31)

is the Dirichlet series of the multiplicative function g given by

g(p^{ν}) = \begin{cases}p^{3β−1}(p − 1), & if p > 2, ν = 2β ≥ 2; \\ −2^{3β}, & if p = 2, ν = 2β ≥ 2; \\ 0, & if p ≥ 2, ν = 2β − 1 ≥ 1. \end{cases}

Therefore, N_{3}(0,.) = id_{2} ∗g and obtain

∑_{r≤x} N_{3}(0, r) = ∑_{d≤x} g(d) (\frac{x^{3}}{3d^{3}} + O(\frac{x^{2}}{d^{2}} ))

= \frac{x^{3}}{3} G(3) + O (x^{3} ∑_{d>x} \frac{|g(d)|}{d^{3}}) + O (x^{2} ∑_{d≤x} \frac{|g(d)|}{d^{2}}) .  (32)

Here a direct computation shows that

∑_{d≤x} \frac{|g(d)|}{d^{2}} ≤ ∏_{p≤x} ∑_{ν=0}^{∞} \frac{|g(p^{ν})|}{p^{ν}} ≪ ∏_{p} (1 + \frac{1}{p}) ≪ log x  (33)

by Mertens’ theorem.

Furthermore, by (31), g(n) = ∑_{ab^{2}=n} h(a)b^{3}, where the Dirichlet series of the function h is absolutely convergent for ℜs > 3/2. Hence

∑_{n≤x} h(n) = c_{2}x^{2} + O(x^{3/2+ε})

with a certain constant c_{2}, and by partial summation we deduce that

∑_{d>x} \frac{|g(d)|}{d^{3}} ≪ \frac{1}{x}.  (34)

Now the result follows from (32), (33) and (34).

8.6 The congruence x^{2} + y^{2} + z^{2} ≡ 1 (mod r)

N_{3}(1, r) is the sequence \underline{A087784} in [22]. Using Corollary 16 and Proposition 27 we have

Corollary 39. For every prime power p^{ν} (ν ∈ ℕ),

N_{3}(1, p^{ν}) = \begin{cases}p^{2ν}(1 + 1/p), & if p ≡ 1 (mod 4), ν ≥ 1; \\ p^{2ν}(1 − 1/p), & if p ≡ −1 (mod 4), ν ≥ 1; \\ 4, & if p = 2, ν = 1; \\ 3 · 2^{2ν−1}, & if p = 2, ν ≥ 2. \end{cases}

Proposition 40. We have

∑_{r≤x} N_{3}(1, r) = \frac{36G}{π^{4}}x^{3} + O(x^{2} log x).

Proof. Now the corresponding Dirichlet series is

∑_{r=1}^{∞} \frac{N_{3}(1, r)}{r^{s}} = ζ(s − 2) (1 + \frac{8}{2^{2s}} ) ∏_{p≡1 (mod 4)} (1 + \frac{1}{p^{s−1}} ) ∏_{p≡−1 (mod 4)} (1 − \frac{1}{p^{s−1}} ) .

Hence, N_{3}(1,.) = id_{2} ∗f, where f is the multiplicative function defined for prime powers p^{ν} by

f(p^{ν}) = \begin{cases}p, & if p ≡ 1 (mod 4), ν = 1; \\ −p, & if p ≡ −1 (mod 4), ν = 1; \\ 8, & if p = 2, ν = 2; \\ 0, & otherwise, \end{cases}

and the given asymptotic formula is obtained by the convolution method.

8.7 The congruence x^{2} + y^{2} + z^{2} + t^{2} ≡ 0 (mod r)

This is the case k = 4, n = 0 (sequence \underline{A240547} in [22]). For every r odd,

N_{4}(0, r) = r^{3} ∑_{d|r} \frac{φ(d)}{d^{2}}

by Corollary 5 and using also Proposition 24 we conclude Corollary 41. For every prime power p^{ν} (ν ∈ ℕ),

N_{4}(0, p^{ν}) = \begin{cases}p^{2ν−1}(p^{ν+1} + p^{ν} − 1), & if p > 2, ν ≥ 1; \\ 2^{2ν+1}, & if p = 2, ν ≥ 1. \end{cases}

Proposition 42. We have

∑_{r≤x} N_{4}(0, r) = \frac{5π^{2}}{168ζ(3)}x^{4} + O(x^{3} log x).

Proof. The corresponding Dirichlet series is

∑_{r=1}^{∞} \frac{N_{4}(0, r)}{r^{s}} = ζ(s − 2)ζ(s − 3) (1 − \frac{4}{2^{s}} − \frac{32}{2^{2s}} ) ∏_{p>2} (1 − \frac{1}{p^{s−1}} ) .

8.8 The congruence x^{2} + y^{2} + z^{2} + t^{2} ≡ 1 (mod r)

This is the case k = 4, n = 1. N_{4}(1, r) is sequence \underline{A208895} in [22]. By the identity (22) giving its values for r odd and by Corollary 22 we obtain

Corollary 43. For every prime power p^{ν} (ν ∈ ℕ),

N_{4}(1, p^{ν}) = \begin{cases}p^{3ν}(1 − 1/p^{2}), & if p > 2, ν ≥ 1; \\ 8^{ν}, & if p = 2, ν ≥ 1. \end{cases}

Proposition 44. We have

∑_{r≤x} N_{4}(1, r) = \frac{2}{7ζ(3)}x^{4} + O(x^{3}).

Proof. Here

∑_{r=1}^{∞} \frac{N_{4}(1, r)}{r^{s}} = ζ(s − 3) ∏_{p>2} (1 − \frac{1}{p^{s−1}} ) .

Finally, we deal with two special cases corresponding to a ≠ (1, …, 1).

8.9 The congruence x^{2} − y^{2} ≡ 1 (mod r)

Here k = 2, n = 1, a = (1, −1). N_{2}(1, r, (1, −1)) is sequence \underline{A062570} in [22]. Corollary 11 tells us that for every r ∈ ℕ odd, N_{3}(1, r, (1, −1)) = φ(r). Furthermore, from Proposition 1 one can deduce, similar to the proof of Proposition 21 that for every ν ∈ ℕ, N_{3}(1, 2^{ν}, (1, −1)) = 2^{ν}. Thus,

Corollary 45. For every r ∈ ℕ one has

N_{3}(1, r, (1, −1)) = φ(2r).

8.10 The congruence x^{2} + y^{2} ≡ z^{2} (mod r)

This Phythagorean congruence is obtained for k = 3, n = 0, a_{1} = a_{2} = 1, a_{3} = −1. N_{3}(0, r, (1, 1, −1)) is sequence \underline{A062775} in [22]. Proposition 19 shows that for every r ∈ ℕ odd, N_{3}(0, r, (1, 1, −1)) = N_{3}(0, r) given by (30). From Proposition 1 one can deduce that for every ν ∈ ℕ,

N_{3}(0, 2^{ν}, (1, 1, −1)) = 2^{2ν} (2 − \frac{1}{2^{⌊ν/2⌋}} ) .

Consequently, Corollary 46.

N_{3}(0, p^{ν}, (1, 1, −1)) = \begin{cases}p^{3β−1}(p^{β+1} + p^{β} − 1), & if p > 2, ν = 2β is even; \\ p^{3β−2}(p^{β} + p^{β−1} − 1), & if p > 2, ν = 2β − 1 is odd; \\ 2^{3β}(2^{β+1} − 1), & if p = 2, ν = 2β is even; \\ 2^{3β−1}(2^{β} − 1), & if p = 2, ν = 2β − 1 is odd. \end{cases}

9 Acknowledgments

The author gratefully acknowledges support from the Austrian Science Fund (FWF) under the project Nr. M1376-N18. The author thanks Olivier Bordellès, Steven Finch and Wenguang Zhai for their valuable comments on the asymptotic formulas included in Section 8. The author is thankful to the referee for some corrections and remarks that have improved the paper.

References

[1] T. M. Apostol, Introduction to Analytic Number Theory, Springer, 1976.

[2] P. Bachmann, Zahlentheorie, Vol. 4: Arithmetik der quadratischen Formen, Leipzig, 1898.

[3] R. C. Baker, The square-free divisor problem II, Quart. J. Math. (Oxford) (2) 47 (1996), 133–146.

[4] B. C. Berndt, R. J. Evans, and K. S. Williams, Gauss and Jacobi Sums, Canadian Mathematical Society Series of Monographs and Advanced Texts, New York, NY: John Wiley & Sons, 1998.

[5] O. Bordellès, Arithmetic Tales, Springer, 2012.

[6] E. Cohen, Rings of arithmetic functions. II: The number of solutions of quadratic congruences, Duke Math. J. 21 (1954), 9–28.

[7] E. Cohen, A generalization of Axer’s theorem and some of its applications, Math. Nachr. 27 (1963/1964), 163–177.

[8] E. Cohen, Arithmetical notes, VII: Some classes of even functions (mod r), Collect. Math. 16 (1964), 81–87.

[9] E. Cohen, Quadratic congruences with an odd number of summands, Amer. Math. Monthly 73 (1966), 138–143.

[10] L. E. Dickson, History of the Theory of Numbers, vol. II, reprinted by Chelsea, New York, 1966.

[11] S. Finch, G. Martin, and P. Sebah, Roots of unity and nullity modulo n, Proc. Amer. Math. Soc. 138 (2010), 2729–2743.

[12] K. Girstmair, The equation x^{2} + \overline{m}y^{2} = \overline{k} in ℤ/pℤ, Amer. Math. Monthly 120 (2013), 546–552.

[13] E. Grosswald, Representations of Integers as Sums of Squares, Springer, 1985.

[14] G. H, Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Sixth Edition, Edited and revised by D. R. Heath-Brown and J. H. Silverman, Oxford University Press, 2008.

[15] L. K. Hua, Introduction to Number Theory, Springer, 1982.

[16] M. N. Huxley, Exponential sums and lattice points III., Proc. London Math. Soc. 87 (2003), 591–609.

[17] K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., Graduate Texts in Mathematics 84, Springer, 1990.

[18] H. Minkowski, Gesammelte Abhandlungen, Leipzig, 1911.

[19] W. Narkiewicz, Number Theory, World Scientific, Singapore, 1983.

[20] M. B. Nathanson, Elementary Methods in Number Theory, Graduate Texts in Mathematics 195, Springer, 2000.

[21] M. O. Rabin and J. O. Shallit, Randomized algorithms in number theory, Comm. in Pure and Applied Math. 39 (supplement) (1986), S239–S256.

[22] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences. http://oeis.org [23] D. Suryanarayana and V. Siva Rama Prasad, The number of k-free divisors of an integer,

Acta Arith. 17 (1971), 345–354.

[24] L. Tóth and P. Haukkanen, The discrete Fourier transform of r-even functions, Acta Univ. Sapientiae, Math. 3 (2011), 5–25.

2010 Mathematics Subject Classification: Primary 11D79; Secondary 11A25, 11N37. Keywords: quadratic congruence in many variables, number of solutions, Jacobi symbol, Ramanujan sum, character sum, Gauss quadratic sum, asymptotic formula.

(Concerned with sequences \underline{A000089}, \underline{A000188}, \underline{A060594}, \underline{A060968}, \underline{A062570}, \underline{A062775}, \underline{A062803}, \underline{A086932}, \underline{A086933}, \underline{A087561}, \underline{A087687}, \underline{A087784}, \underline{A088964}, \underline{A088965}, \underline{A089002}, \underline{A089003}, \underline{A091143}, \underline{A096018}, \underline{A096020}, \underline{A208895}, \underline{A227553}, \underline{A229179}, \underline{A240547}.)

Received July 1 2014; revised versions received September 21 2014; November 8 2014. Published in Journal of Integer Sequences, November 9 2014.

Return to Journal of Integer Sequences home page.