Generalization of a Result of Sylvester Related to the Frobenius Coin Problem

Damanvir Singh Binner Department of Mathematics Simon Fraser University Burnaby, BC V5A 1S6 Canada

                    dbinner@sfu.ca

Abstract

In a recent paper, the present author generalized a fundamental result of Gauss related to quadratic reciprocity, and also showed that the above result of Gauss is equivalent to a special case of a well-known result of Sylvester related to the Frobenius coin problem. In this note, we use this equivalence to show that the above generalization of the result of Gauss naturally leads to an interesting generalization of the result of Sylvester. To be precise, for given positive coprime integers a and b, and for a family of values of k in the interval 0 ≤ k < (a − 1)(b − 1), we find the number of nonnegative integers ≤ k that can be expressed in the form ax + by for nonnegative integers x and y. We also give an elementary proof of Eisenstein’s lemma for Jacobi symbols using floor function sums. Our proof provides a natural straightforward generalization of the Gauss-Eisenstein proof of the law of quadratic reciprocity for Jacobi symbols.

1 Introduction

Throughout this note, ⌊x⌋ denotes the greatest integer less than or equal to x. Recall the following well-known results of Gauss and Sylvester.

Theorem 1 (Gauss (1808)). For distinct odd primes p and q,

∑_{i=1}^{\frac{p−1}{2}} ⌊\frac{iq}{p} ⌋ + ∑_{i=1}^{\frac{q−1}{2}} ⌊\frac{ip}{q}⌋ = \frac{(p − 1)(q − 1)}{4}.

Theorem 2 (Sylvester (1882)). If a and b are coprime numbers, the number of natural numbers that cannot be expressed in the form ax + by for nonnegative integers x and y is equal to \frac{(a−1)(b−1)}{2}.

Remark 3. Theorem 1 and its proof hold verbatim for any odd positive coprime integers a and b.

In this note, the following special case of Theorem 2 will be of particular interest.

Theorem 4. If p and q are distinct odd prime numbers, the number of natural numbers that cannot be expressed in the form px + qy for nonnegative integers x and y is equal to \frac{(p−1)(q−1)}{2}.

We refer to Theorem 2 as Sylvester’s theorem and to Theorem 4 as the Special Case of Sylvester’s theorem.

Gauss [9] proved Theorem 1 in 1808, and this completed his third proof of the law of quadratic reciprocity. Eisenstein [8] gave a geometric proof of Theorem 1 in 1844. We refer the reader to Baumgart [2, pp. 15–20] for more information about these classical proofs. Sylvester [15] proved Theorem 2 in 1882. In 1883, he posed it as a recreational problem and Curran [16] published a short proof based on generating functions. Several more contemporary proofs of Sylvester’s theorem are known [1, Section 5.1].

The present author [3, Lemma 7] generalized Theorem 1 as follows.

Theorem 5. Let a, b, d, and K be positive integers such that b < a, d < a, gcd(a, b) = 1, and K = ⌊\frac{bd}{a}⌋. Then

∑_{i=1}^{d} ⌊\frac{ib}{a}⌋ + ∑_{i=1}^{K} ⌊\frac{ia}{b}⌋ = dK.

The present author [3, Section 3] proved that the Special Case of Sylvester’s theorem is equivalent to the reciprocity relation of Gauss in Theorem 1. As described below, the importance of this equivalence is demonstrated by the fact that we are able to generalize Sylvester’s theorem using our generalization of the Gauss’ result (Theorem 5). Prior to that, we choose an appropriate special case of Theorem 5 that is equivalent to Sylvester’s theorem. It turns out that the following special case of Theorem 5 is precisely what we require.

Theorem 6. Let a and b be positive coprime integers. Then

\begin{matrix}⌊ & \frac{a}{2} & ⌋ \\ ∑ \\ i=1 \end{matrix} ⌊\frac{ib}{a}⌋ + \begin{matrix}⌊ & \frac{b}{2} & ⌋ \\ ∑ \\ i=1 \end{matrix} ⌊\frac{ia}{b}⌋ = ⌊\frac{a}{2}⌋⌊\frac{b}{2}⌋.

Theorem 6 was known before (see [12, Section 3.2, Exercise 23]). However, we provide a proof of Theorem 6 using Theorem 5 in Section 2, where we also show that it is equivalent to Theorem 2. Note that Theorem 5 is a generalization of Theorem 6. Thus, it is natural to

Theorem 4 (Special Case of Sylvester’s theorem) ⟺^{A} Theorem 1 (Gauss (1808))

⋂  ⋂
Theorem 2 (Sylvester’s theorem (1882))  ⟺^{B}  Theorem 6
⋂  ⋂
Theorem 8 (Binner (2021))  ⟺^{C} Theorem 5 (Binner (2020))

Figure 1: By Theorem X ⊂ Theorem Y, we mean that Theorem X is a special case of Theorem Y, and by Theorem X ⇔ Theorem Y, we mean that Theorems X and Y are equivalent. The present author [3, Section 2.3] proved Equivalence A in 2020. We prove Equivalences B and C in Sections 2 and 3, respectively.

wonder whether the equivalence leads to a generalization of Theorem 2, that is equivalent to Theorem 5. This is in fact true and leads to an interesting result (Theorem 8). We make this sequence of equivalence of results more clear in Figure 1 below.

Sylvester’s theorem shows that exactly one-half of the integers in the interval [0, ab − a − b) can be expressed in the form ax + by. It is natural to ask a more general question.

Question 7. For given positive coprime integers a and b, and given k such that 0 ≤ k < (a − 1)(b − 1), find the number of nonnegative integers ≤ k that can be expressed in the form ax + by for nonnegative integers x and y.

We denote this number by N_{0}(a, b; k). For k < 0, we define N_{0}(a, b; k) = 0. By Sylvester’s theorem, we have N_{0}(a, b; ab − a − b) = \frac{(a−1)(b−1)}{2}. In this note, we answer Question 7 for a specific family of values of k by proving Theorem 8.

Theorem 8. Let a and b be positive coprime integers with b < a. Further, let 0 < α < a be such that α ≡ a (mod 2), and β = 2 ⌊\frac{b(α+a)}{2a}⌋ − b. Then

N_{0} (a, b; \frac{bα + aβ}{2} ) = \frac{(α + 1)(β + 1)}{2}.

Setting α = a − 2 in the above theorem gives Theorem 2. Note that

β ≥ 2 ⌊\frac{b}{2}⌋ − b ≥ −1.

Thus, for \frac{bα+aβ}{2} < 0, it must be true that β = −1, and then by Theorem 8, N_{0} (a, b; \frac{bα+aβ}{2} ) = 0, which is consistent with our definition of N_{0}(a, b; k) for negative values of k.

We demonstrate Theorem 8 for an example. Suppose that a = 29 and b = 23. Then Sylvester’s theorem shows that N_{0}(29, 23; 615) = 308. However, Theorem 8 gives us N_{0}(29, 23; k) for a lot of values of k, as described in Table 1.

\begin{matrix}α & k & N_{0}(29, 23; k) \\ 1 & −1 & 0 \\ 3 & 49 & 4 \\ 5 & 101 & 12 \\ 7 & 153 & 24 \\ 9 & 205 & 40 \\ 11 & 228 & 48 \\ 13 & 280 & 70 \\ 15 & 332 & 96 \\ 17 & 384 & 126 \\ 19 & 436 & 160 \\ 21 & 459 & 176 \\ 23 & 511 & 216 \\ 25 & 563 & 260 \\ 27 & 615 & 308 \end{matrix}

Table 1: The values of N_{0}(29, 23; k) versus k, as α varies from 1 to 27 such that α is odd.

In Section 3, we prove Theorem 8 and also show that it is equivalent to Theorem 5 (Equivalence C in Figure 1). For other values of k not covered by Theorem 8, we describe an easy method to calculate N_{0}(a, b; k) in Section 4.

We conclude our discussion of Question 7 by mentioning that for given coprime natural numbers a and b, the study of properties of numbers that cannot be expressed in the form ax + by (also called nonrepresentable numbers), where x and y are nonnegative integers, continues to be an active area of research. Let NR(a, b) denote the set of nonnegative integers n that cannot be expressed in the form ax + by. Then by Sylvester’s theorem, | NR(a, b)| = \frac{(a−1)(b−1)}{2}. Brown and Shiue [4] discovered the sum S(a, b) of nonrepresentable numbers. They proved that

S(a, b) := ∑_{n∈NR(a,b)} n = \frac{1}{12}(a − 1)(b − 1)(2ab − a − b − 1).

Rødseth considered a generalization of this sum

S_{m}(a, b) = ∑_{n∈NR(a,b)} n^{m}.

These sums S_{m}(a, b) are commonly known as the Sylvester sums. Rødseth [13] discovered a formula for these sums in terms of Bernoulli numbers and found that

S_{2}(a, b) = ∑_{n∈NR(a,b)} n^{2} = \frac{1}{12}(a − 1)(b − 1)ab(ab − a − b).

Recently, Komatsu and Zhang [10] considered the weighted Sylvester sums

S_{m}^{(λ)} = ∑_{n∈NR(a,b)} λ^{n−1}n^{m}.

They gave explicit expressions for these sums in terms of the Apostol-Bernoulli numbers.

However, in Question 7, we consider the number of nonrepresentable numbers below a given number k, instead of considering all the nonrepresentable numbers.

In Section 5, we describe an application of floor function summation results to Jacobi symbols. Our approach leads to a natural straightforward generalization of the Gauss-Eisenstein proof of the law of quadratic reciprocity for Jacobi symbols. We recall some main steps in the Gauss-Eisenstein proof of the law of quadratic reciprocity for Legendre symbols. More details about these results can be found in [12, Chapter 3].

Definition 9. Let a and m be integers such that gcd(a, m) = 1. Then a is called a quadratic residue modulo m if the congruence x^{2} ≡ a (mod m). has a solution. If the congruence has no solution, then a is called a quadratic nonresidue modulo m.

Definition 10. Let p denote an odd prime. The Legendre symbol (\frac{a}{p}) is defined to be 1 if a is a quadratic residue modulo p, −1 if a is a quadratic nonresidue modulo p, and 0 if p divides a.

Theorem 11 (Gauss’ lemma for Legendre symbols). Suppose p is an odd prime and gcd(a, p) = 1. Consider the integers a, 2a, 3a, …, (\frac{p−1}{2}) a and their least positive residues modulo p. If

n denotes the number of these residues that exceed \frac{p}{2}, then the Legendre symbol (\frac{a}{p}) satisfies

(\frac{a}{p}) = (−1)^{n}.

Theorem 12 (Eisenstein’s lemma for Legendre symbols). If p is an odd prime and a is any odd number not divisible by p, then (\frac{a}{p}) = (−1)^{t} where

t = ∑_{i=1}^{\frac{p−1}{2}} ⌊\frac{ia}{p}⌋ .

Theorems 1 and 12 immediately lead to the law of quadratic reciprocity, which is as follows:

Theorem 13 (Law of quadratic reciprocity for Legendre symbols). For distinct odd primes p and q, we have

(\frac{p}{q}) (\frac{q}{p}) = (−1)^{\frac{(p−1)(q−1)}{4}} .

The theory of quadratic residues can be extended further by generalizing Legendre symbols to Jacobi symbols.

Definition 14. Let b be an odd number and b = p_{1}^{r_{1}}p_{2}^{r_{2}} ⋯ p_{k}^{r_{k}} be its prime factorization. Then the Jacobi symbol (\frac{a}{b}) is defined as

(\frac{a}{b}) := (\frac{a}{p_{1}} )^{r_{1}} (\frac{a}{p_{2}} )^{r_{2}} ⋯ (\frac{a}{p_{k}} )^{r_{k}} ,

where (\frac{a}{p_{i}} ) is the Legendre symbol.

Schering [14] generalized Gauss’ lemma to the Jacobi symbol. However a direct proof of the Gauss-Schering lemma [14, 6, 11] seems to be quite technical. Zolotarev [18] observed that Legendre and Jacobi symbols are connected to signatures of naturally associated permutations. Using this approach, there are some other proofs [7, 5] showing that Gauss’ lemma can be generalized to the Jacobi symbol. These methods give direct proofs of the law of quadratic reciprocity for Jacobi symbols at the cost of introducing some auxiliary concepts of an abstract algebraic nature. In the present note, we provide an elementary proof using floor function sums, showing that Eisenstein’s lemma also holds for Jacobi symbols.

Theorem 15 (Eisenstein’s lemma for Jacobi symbols). For odd positive coprime integers a and b, the Jacobi symbol (\frac{a}{b}) is given as

(\frac{a}{b}) = (−1)∑_{i=1}^{\frac{b−1}{2}}^{⌊^{\frac{ia}{b}}⌋}.

To prove Theorem 15 using Eisenstein’s lemma for Legendre symbols (Theorem 12), it suffices to prove the following result.

Lemma 16. For odd positive integers a, b and c such that b and c are coprime with a,

∑_{i=1}^{\frac{bc−1}{2}} ⌊\frac{ia}{bc}⌋ ≡ ∑_{i=1}^{\frac{b−1}{2}} ⌊\frac{ia}{b}⌋ + ∑_{i=1}^{\frac{c−1}{2}} ⌊\frac{ia}{c}⌋ (mod 2).

Using Theorem 1 and Remark 3 (or Theorem 6 instead), we can easily express all of the sums above in terms of summations of fractions having denominator a and summation index \frac{a−1}{2}. From there, Lemma 16 reduces to proving the following result.

Lemma 17. For odd positive integers a, b and c such that b and c are coprime with a,

∑_{i=1}^{\frac{a−1}{2}} ⌊\frac{ibc}{a}⌋ ≡ ∑_{i=1}^{\frac{a−1}{2}} ⌊\frac{ib}{a}⌋ + ∑_{i=1}^{\frac{a−1}{2}} ⌊\frac{ic}{a}⌋ (mod 2).

We prove Lemma 17 in Section 5. The law of quadratic reciprocity for Jacobi symbols (Theorem 18 below) is then immediately obtained using Eisenstein’s lemma for Jacobi symbols (Theorem 15), and Theorem 1 and Remark 3 (or Theorem 6 instead).

Theorem 18 (Law of quadratic reciprocity for Jacobi symbols). If a and b are positive odd coprime integers, then

(\frac{a}{b})(\frac{b}{a}) = (−1)^{\frac{(a−1)(b−1)}{4}} .

Remark 19. Using the standard techniques in the proof of Theorem 12 [12, Theorem 3.3], it is straightforward to deduce Gauss’ lemma for Jacobi symbols from Eisenstein’s lemma for Jacobi symbols.

2 Equivalence between Theorems 2 and 6

In this section, we prove Theorem 6 and show that it is equivalent to Theorem 2 (Equivalence B in Figure 1).

Proof of Theorem 6. Without loss of generality, suppose that b < a. By setting the index of summation equal to ⌊\frac{a}{2}⌋ in Theorem 5, we get

\begin{matrix}⌊ & \frac{a}{2} & ⌋ \\ ∑ \\ i=1 \end{matrix} ⌊\frac{ib}{a}⌋ + ∑_{i=1}^{K} ⌊\frac{ia}{b}⌋ = K⌊\frac{a}{2}⌋,  (1)

where

K = ⌊\frac{⌊\frac{a}{2}⌋ b}{a}⌋ .

We split the calculation into three cases based on the parity of a and b.

Case 1: Suppose a is even. Then K = ⌊\frac{b}{2}⌋, and we are done.

Case 2: Suppose a and b are both odd. Then

K = ⌊\frac{(a − 1)b}{2a}⌋ = ⌊\frac{b − 1}{2} + \frac{a − b}{2a}⌋ = \frac{b − 1}{2} = ⌊\frac{b}{2}⌋.

Case 3: Suppose a is odd and b is even. Then

K = ⌊\frac{(a − 1)b}{2a}⌋ = ⌊\frac{b}{2} − \frac{b}{2a}⌋ = \frac{b}{2} − 1 = ⌊\frac{b}{2}⌋ − 1,

and thus (1) becomes

\begin{matrix}⌊ & \frac{a}{2} & ⌋ \\ ∑ \\ i=1 \end{matrix} ⌊\frac{ib}{a}⌋ + ∑_{i=1}^{⌊\frac{b}{2}⌋−1} ⌊\frac{ia}{b}⌋ = (⌊\frac{b}{2}⌋ − 1) ⌊\frac{a}{2}⌋.  (2)

From (2), the theorem easily follows in this case.

We establish the equivalence between Theorems 2 and 6 (Equivalence B in Figure 1). Since the proofs of Lemmas 20, 21, and 22 below are easy generalizations of our proofs in [3, Lemmas 10, 12, 13] respectively, we skip the details here. For the remainder of this section, suppose a and b are positive coprime integers.

Lemma 20. The number of nonnegative integer solutions (x, y, z) of the equation ax + by + z = b⌊\frac{a}{2}⌋ is given by

⌊\frac{a}{2}⌋ + 1 + \begin{matrix}⌊ & \frac{a}{2} & ⌋ \\ ∑ \\ i=1 \end{matrix} ⌊\frac{ib}{a}⌋.

Lemma 21. The number of nonnegative integer solutions (x, y, z) of the equation

ax + by + z = a⌊\frac{b}{2}⌋ + b⌊\frac{a}{2}⌋

is equal to

a⌊\frac{b}{2}⌋ + b⌊\frac{a}{2}⌋ + 1 − N_{0},

where N_{0} is the number of natural numbers which cannot be expressed as ax + by for any nonnegative integers x and y.

Lemma 22. The number of nonnegative integer solutions (x, y, z) of the equation

ax + by + z = a⌊\frac{b}{2}⌋ + b⌊\frac{a}{2}⌋

is equal to

2 (\begin{matrix}⌊ & \frac{a}{2} & ⌋ \\ ∑ \\ i=1 \end{matrix} ⌊\frac{ib}{a}⌋ + \begin{matrix}⌊ & \frac{b}{2} & ⌋ \\ ∑ \\ i=1 \end{matrix} ⌊\frac{ia}{b}⌋) + ⌊\frac{a}{2}⌋ + ⌊\frac{b}{2}⌋ + 1.

We are now ready to show the equivalence between Theorems 2 and 6 (Equivalence B in Figure 1). Upon comparing the number of nonnegative integer solutions of the equation ax + by + z = a⌊\frac{b}{2}⌋ + b⌊\frac{a}{2}⌋ obtained in Lemmas 21 and 22, and then using Lemma 20, we find

N_{0} + 2 (\begin{matrix}⌊ & \frac{a}{2} & ⌋ \\ ∑ \\ i=1 \end{matrix} ⌊\frac{ib}{a}⌋ + \begin{matrix}⌊ & \frac{b}{2} & ⌋ \\ ∑ \\ i=1 \end{matrix} ⌊\frac{ia}{b}⌋) = (a − 1)⌊\frac{b}{2}⌋ + (b − 1)⌊\frac{a}{2}⌋.  (3)

By taking three cases based on the parity of a and b, it can be easily verified that

(a − 1)⌊\frac{b}{2}⌋ + (b − 1)⌊\frac{a}{2}⌋ = \frac{(a − 1)(b − 1)}{2} + 2⌊\frac{a}{2}⌋⌊\frac{b}{2}⌋.  (4)

From (3) and (4), we get that

N_{0} + 2 (\begin{matrix}⌊ & \frac{a}{2} & ⌋ \\ ∑ \\ i=1 \end{matrix} ⌊\frac{ib}{a}⌋ + \begin{matrix}⌊ & \frac{b}{2} & ⌋ \\ ∑ \\ i=1 \end{matrix} ⌊\frac{ia}{b}⌋) = \frac{(a − 1)(b − 1)}{2} + 2⌊\frac{a}{2}⌋⌊\frac{b}{2}⌋.

The equivalence between Theorems 2 and 6 (Equivalence B in Figure 1) now readily follows.

3 Proof of Theorem 8

In this section, we prove Theorem 8 and the Equivalence C in Figure 1. Recall that for given positive coprime integers a and b, and given k such that 0 ≤ k < (a − 1)(b − 1), the symbol N_{0}(a, b; k) denotes the number of natural numbers ≤ k that can be expressed in the form ax + by for nonnegative integers x and y.

For positive coprime integers a and b and any natural number n, let N(a, b; n) denote the number of nonnegative integer solutions of ax + by = n. An exact formula for N(a, b; n) [17] is known. Further, it is well-known that N(a, b; n + ab) = N(a, b; n) + 1 (see [17, Lemma 1]). Using this fact while generalizing the proof of Lemma 21, we easily get the following result.

Lemma 23. Let a, b, d, and K be positive integers such that b < a, \frac{a}{2} < d < a, gcd(a, b) = 1,

and K = ⌊\frac{bd}{a}⌋. The number of nonnegative integer solutions of the equation

ax + by + z = bd + aK

is equal to

bd + aK + 1 − \frac{(a − 1)(b − 1)}{2} + N_{0}(a, b; bd + aK − ab).

Generalizing the proof of Lemma 22 and then using Theorem 5, we get the following result.

Lemma 24. Let a, b, d, and K be positive integers such that b < a, d < a, gcd(a, b) = 1, and K = ⌊\frac{bd}{a}⌋. The number of nonnegative integer solutions (x, y, z) of the equation

ax + by + z = bd + aK

is equal to

2 (∑_{i=1}^{d} ⌊\frac{ib}{a}⌋ + ∑_{i=1}^{K} ⌊\frac{ia}{b}⌋) + d + K + 1.

The following lemma immediately follows from Lemmas 23 and 24.

Lemma 25. Let a, b, d, and K be positive integers such that b < a, \frac{a}{2} < d < a, gcd(a, b) = 1,

and K = ⌊\frac{bd}{a}⌋. Then

N_{0}(a, b; bd + aK − ab) = 2 (∑_{i=1}^{d} ⌊\frac{ib}{a}⌋ + ∑_{i=1}^{K} ⌊\frac{ia}{b}⌋ − dK) + \frac{(2d − a + 1)(2K − b + 1)}{2}.

Using Lemma 25, it is clear that Theorem 5 is equivalent to the following theorem.

Theorem 26. Let a, b, d, and K be positive integers such that b < a, \frac{a}{2} < d < a, gcd(a, b) =

1, and K = ⌊\frac{bd}{a}⌋. Then

N_{0}(a, b; bd + aK − ab) = \frac{(2d − a + 1)(2K − b + 1)}{2}.

Observe that Theorem 8 is just another version of Theorem 26 obtained by setting α = 2d − a and β = 2K − b in Theorem 26. This completes the proof of Theorem 8 and its equivalence with Theorem 5 (Equivalence C in Figure 1).

4 N_{0}(a, b; k) for other values of k

In this section, we describe an easy method to calculate N_{0}(a, b; k) for other values of k not covered by Theorem 8. It is well-known that for l < ab, the equation ax + by = l has at most one solution [17, Lemma 2 and Lemma 4]. Using this fact, it is easy to see that for k < ab, N_{0}(a, b; k) is equal to the number of nonnegative integer solutions of ax+by +z = k, which can be easily calculated using the algorithm described in [3, Section 2.3]. For example, suppose we want to calculate N_{0}(29, 23; 257). Then by [3, Theorem 5], we get that

N_{0}(29, 23; 257) = 15 + ∑_{i=1}^{8} ⌊\frac{23i}{29}⌋ + ∑_{i=1}^{18} ⌊\frac{4i}{23}⌋ .

By repeated applications of Theorem 5 and the division algorithm, as described in [3, Section 2.3], we easily get that ∑_{i=1}^{8} ⌊\frac{23i}{29}⌋ = 24 and ∑_{i=1}^{18} ⌊\frac{4i}{23}⌋ = 21, and thus N_{0}(29, 23; 257) = 60.

5 Proof of Lemma 17

Proof of Lemma 17. For brevity of notation, let r(m) denote the remainder when m is divided by a. Since a, b and c are odd, we get

∑_{i=1}^{\frac{a−1}{2}} ⌊\frac{ibc}{a}⌋ ≡ ∑_{i=1}^{\frac{a−1}{2}} a ⌊\frac{ibc}{a}⌋ (mod 2)

= ∑_{i=1}^{\frac{a−1}{2}} ibc − r(ibc)

≡ ∑_{i=1}^{\frac{a−1}{2}} i − ∑_{i=1}^{\frac{a−1}{2}} r(ibc) (mod 2).  (5)

Next, we study the latter sum. Let c_{i} denote the remainder when ic is divided by a. Note that

c_{i} = ic − a ⌊\frac{ic}{a}⌋

≡ i − ⌊\frac{ic}{a}⌋ (mod 2).

Therefore,

r(ibc) = r(bc_{i})

= bc_{i} − a ⌊\frac{bc_{i}}{a} ⌋

≡ c_{i} − ⌊\frac{bc_{i}}{a} ⌋ (mod 2)

≡ i − ⌊\frac{ic}{a}⌋ − ⌊\frac{bc_{i}}{a} ⌋ (mod 2).  (6)

Thus, from (5) and (6), we get that

∑_{i=1}^{\frac{a−1}{2}} ⌊\frac{ibc}{a}⌋ ≡ ∑_{i=1}^{\frac{a−1}{2}} ⌊\frac{ic}{a}⌋ + ∑_{i=1}^{\frac{a−1}{2}} ⌊\frac{bc_{i}}{a} ⌋ (mod 2).

Therefore, to complete the proof of the lemma, it suffices to show that

∑_{i=1}^{\frac{a−1}{2}} ⌊\frac{bc_{i}}{a} ⌋ ≡ ∑_{i=1}^{\frac{a−1}{2}} ⌊\frac{ib}{a}⌋ (mod 2).  (7)

Let d_{i} = min(c_{i}, a − c_{i}). Note that

⌊\frac{b(a − c_{i})}{a}⌋ = b − 1 − ⌊\frac{bc_{i}}{a} ⌋ ≡ ⌊\frac{bc_{i}}{a} ⌋ (mod 2).

Therefore, for each i,

⌊\frac{bd_{i}}{a} ⌋ ≡ ⌊\frac{bc_{i}}{a} ⌋ (mod 2).

Moreover, note that as i varies from 1 to \frac{a−1}{2}, so does d_{i}. Therefore,

∑_{i=1}^{\frac{a−1}{2}} ⌊\frac{bc_{i}}{a} ⌋ ≡ ∑_{i=1}^{\frac{a−1}{2}} ⌊\frac{bd_{i}}{a} ⌋ (mod 2)

= ∑_{i=1}^{\frac{a−1}{2}} ⌊\frac{ib}{a}⌋ (mod 2),

completing the proof of (7), and thus of Lemma 17.

6 Acknowledgments

I want to thank the anonymous referee for some excellent insights, especially regarding Jacobian quadratic reciprocity. I also wish to express my gratitude to A. Rattan at Simon Fraser University for some very helpful suggestions on the presentation of this paper. Finally, I want to thank the Mathematics Department at SFU for providing me various awards and fellowships that helped me conduct my research.

References

[1] J. L. Ramírez Alfonsín, The Diophantine Frobenius Problem, Vol. 30 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, 2005.

[2] O. Baumgart, The Quadratic Reciprocity Law: A Collection of Classical Proofs, Springer International Publishing, 2015.

[3] D. S. Binner, The number of solutions to ax + by + cz = n and its relation to quadratic residues, J. Integer Sequences 23 (2020), Article 20.6.5.

[4] T. C. Brown and P. J. Shiue, A remark related to the Frobenius problem, Fibonacci Quart. 31 (1993), 32–36.

[5] A. Brunyate and P. L. Clark, Extending the Zolotarev-Frobenius approach to quadratic reciprocity, Ramanujan J. 37 (2015), 25–50.

[6] P. Cartier, Sur une généralisation des symboles de Legendre-Jacobi, Enseign. Math. 16 (1970), 31–48.

[7] W. Duke and K. Hopkins, Quadratic reciprocity in a finite group, Amer. Math. Monthly 112 (2005), 251–256.

[8] G. Eisenstein. Geometrischer Beweis des Fundamentaltheorems für die quadratischen Reste, J. Reine Angew. Math. 28 (1844), 246–248.

[9] C. F. Gauss, Theorematis arithmetici demonstratio nova, Comment. Soc. regiae sci. Göttingen 16 (1808), 69.

[10] T. Komatsu and Y. Zhang, Weighted Sylvester sums on the Frobenius set, arxiv

    preprint, 2021. Available at https://arxiv.org/pdf/2105.08274.pdf.

[11] A. Kuroki and S. I. Katayama, A variation of Takagi’s proof for quadratic reciprocity laws of Jacobi symbols, J. Math. Tokushima Univ. 43 (2009), 9–23.

[12] I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction to the Theory of Numbers, John Wiley and Sons Inc, 2004.

[13] Ø. J. Rødseth, A note on Brown and Shiue’s paper on a remark related to the Frobenius problem, Fibonacci Quart. 32 (1994), 407–408.

[14] E. Schering, Zur Theorie der quadratischen Reste, Acta Math. 1 (1882), 153–170; Werke II, 69–86.

[15] J. J. Sylvester, On subinvariants, i.e. semi-invariants to binary quantics of an unlimited order, Amer. J. Math. 5 (1882), 79–136.

[16] J. J. Sylvester, Problem 7382, Mathematical Questions, with their Solutions, from the Educational Times 41 (1884), 21.

[17] A. Tripathi, The number of solutions to ax + by = n, Fibonacci Quart. 38 (2000), 290–293.

[18] G. Zolotarev, Nouvelle démonstration de la loi de réciprocité de Legendre. Nouvelles Annales de Mathématiques 11 (1872), 354–362.

2010 Mathematics Subject Classification: Primary 11D45; Secondary 11A15, 11A07, 11D04, 05A15.

Keywords: Frobenius coin problem, nonrespresentable number, Sylvester’s result, equivalence, reciprocity relation, floor function summation, Gauss-Schering lemma, Eisenstein’s lemma for Jacobi symbol, quadratic reciprocity for Jacobi symbol, Frobenius number.

Received July 10 2021; revised versions received July 20 2021; July 23 2021; August 6 2021; August 10 2021. Published in Journal of Integer Sequences, August 17 2021.

Return to Journal of Integer Sequences home page.