The Number of Solutions to ax + by + cz = n and its Relation to Quadratic Residues

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

                        dbinner@sfu.ca

Abstract

We develop a formula for the number of non-negative integer solutions (x, y, z) of the equation ax + by + cz = n, where a, b, c, and n are given positive integers. The formula leads us to a surprising connection between the number of non-negative integer solutions of the equation ax + by + cz = n and quadratic residues. As a consequence of our work, we are able to prove the equivalence between two fundamental results by Gauss and Sylvester in the nineteenth century that are generally viewed as independent.

1 Introduction

Tripathi [7] used generating functions to obtain a formula for the number of non-negative integer solutions (x, y) of the equation ax + by = n, where a, b, and n are given positive integers. We generalize this procedure for three variables. Throughout this paper, by solutions of an equation, we mean non-negative integer solutions only. We let ⌊x⌋ denote the greatest integer less than or equal to x.

The purpose of this paper is to calculate the number of solutions N(a, b, c; n) of the equation ax + by + cz = n in non-negative integer triples (x, y, z), where a, b, c, and n are given positive integers. Note that if gcd(a, b, c) does not divide n, then the equation cannot have any solutions; if it does divide n, then we can divide both sides of the equation by this common factor. Thus, without loss of generality, we can assume that gcd(a, b, c) = 1.

We show that there is also no loss of generality in making the assumption that a, b, and c are pairwise coprime. This allows us to use generating functions to find an explicit formula for the number of solutions. Further, we establish the equivalence between 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 p and q are distinct odd prime numbers, the number of natural numbers that cannot be expressed in the form px + qy for non-negative integers x and y is equal to \frac{(p−1)(q−1)}{2}.

Gauss [3] proved Theorem 1 in 1808, which completed his third proof of the law of quadratic reciprocity. Eisenstein [2] gave a geometric proof of Theorem 1 in 1844. We refer the reader to Baumgart [1, pp. 15–20] for more information about these classical proofs. Sylvester [5] proved a more general version of Theorem 2 in 1882. In the general case, p and q need only be coprime natural numbers instead of being distinct odd primes. In 1883, Sylvester posed the general version of Theorem 2 as a recreational problem for which Curran [6] published a short proof based on generating functions.

We conclude the paper with some further applications of our formula and techniques, including a complete list of non-negative integer solutions of the equation ax + by = n.

2 The main theorem

2.1 Reduction to an equation with pairwise coprime coefficients

Let a, b, c, and n be positive integers and, as justified above, we assume that gcd(a, b, c) = 1. We define the following symbols:

• Let g_{1}, g_{2}, and g_{3} denote gcd(b, c), gcd(c, a), and gcd(a, b), respectively. Note that gcd(g_{1}, g_{2}) = gcd(g_{2}, g_{3}) = gcd(g_{3}, g_{1}) = 1.

• Let a_{1}, b_{2}, and c_{3} denote the modular inverses of a with respect to the modulus g_{1}, b with respect to the modulus g_{2}, and c with respect to the modulus g_{3}, respectively.

• Let n_{1}, n_{2}, and n_{3} denote the remainders upon dividing na_{1} by g_{1}, nb_{2} by g_{2}, and nc_{3} by g_{3}, respectively.

• Let A = \frac{a}{g_{2}g_{3}} , B = \frac{b}{g_{3}g_{1}} , and C = \frac{c}{g_{1}g_{2}} .

• Let N = \frac{n−an_{1}−bn_{2}−cn_{3}}{g_{1}g_{2}g_{3}} . Note that N is an integer.

Lemma 3. With the notation above, the number of solutions of the equation ax+by+cz = n in non-negative integer triples (x, y, z) is equal to the number of solutions of the equation Ax + By + Cz = N in non-negative integer triples (x, y, z).

Proof. Let S and T denote the solution sets of ax + by + cz = n and Ax + By + Cz = N, respectively. Then, the function ϕ : S → T such that

(x, y, z) ↦ (\frac{x − n_{1}}{g_{1}} , \frac{y − n_{2}}{g_{2}} , \frac{z − n_{3}}{g_{3}} )

provides the required bijection.

Since A, B, and C are pairwise coprime positive integers, Lemma 3 shows that there is no loss of generality in making the assumption that a, b, and c are pairwise coprime.

Remark 4. We briefly describe the motivation behind this bijection. Reducing the equation ax + by + cz = n modulo g_{1}, g_{2}, and g_{3}, gives the congruences x ≡ n_{1} (mod g_{1}), y ≡ n_{2} (mod g_{2}), and z ≡ n_{3} (mod g_{3}), respectively. Thus, we have the expressions x = n_{1} + g_{1}u, y = n_{2}+g_{2}v, and z = n_{3}+g_{3}w, for some non-negative integers u, v, and w. Substituting these expressions back in the given equation ax+by +cz = n, yields the equation Au+Bv +Cw = N, which has pairwise coprime coefficients.

2.2 Statement of theorem and proof

As justified above, we may assume that gcd(a, b) = gcd(b, c) = gcd(c, a) = 1. We introduce a few more symbols.

• Define b′_{1} such that b′_{1} ≡ −nb^{−1} (mod a) with 1 ≤ b′_{1} ≤ a. Moreover, define c′_{1} such that c′_{1} ≡ bc^{−1} (mod a) with 1 ≤ c′_{1} ≤ a.

• Define c′_{2} such that c′_{2} ≡ −nc^{−1} (mod b) with 1 ≤ c′_{2} ≤ b. Moreover, define a′_{2} such that a′_{2} ≡ ca^{−1} (mod b) with 1 ≤ a′_{2} ≤ b.

• Define a′_{3} such that a′_{3} ≡ −na^{−1} (mod c) with 1 ≤ a′_{3} ≤ c. Moreover, define b′_{3} such that b′_{3} ≡ ab^{−1} (mod c) with 1 ≤ b′_{3} ≤ c.

• Define N_{1} = n(n + a + b + c) + cbb′_{1}(a + 1 − c′_{1}(b′_{1} − 1)) + acc′_{2}(b + 1 − a′_{2}(c′_{2} − 1)) +baa′_{3}(c + 1 − b′_{3}(a′_{3} − 1)).

Theorem 5. Let a, b, c, and n be given positive integers such that gcd(a, b) = gcd(b, c) = gcd(c, a) = 1. With the notation above, the number of non-negative integer solutions of the equation ax + by + cz = n is given by

N(a, b, c; n) = \frac{N_{1}}{2abc} + ∑_{i=1}^{b′_{1}−1} ⌊\frac{ic′_{1}}{a} ⌋ + ∑_{i=1}^{c′_{2}−1} ⌊\frac{ia′_{2}}{b} ⌋ + ∑_{i=1}^{a′_{3}−1} ⌊\frac{ib′_{3}}{c} ⌋ − 2.

Proof. By elementary combinatorics, we know that the number of non-negative integer solutions of ax + by + cz = n is equal to the coefficient of x^{n} in

\frac{1}{(1 − x^{a})(1 − x^{b})(1 − x^{c})}.

Let ζ_{m} denote e^{\frac{2πi}{m}}. We know that

(1 − x^{a})(1 − x^{b})(1 − x^{c}) = (1 − x)^{3} ∏_{k=1}^{a−1}(1 − ζ_{a}^{−k}x) ∏_{k=1}^{b−1}(1 − ζ_{b}^{−k}x) ∏_{k=1}^{c−1}(1 − ζ_{c}^{−k}x).

Since a, b, and c are pairwise coprime, 1 − ζ_{a}^{−k}x, 1 − ζ_{b}^{−k}x, and 1 − ζ_{c}^{−k}x are distinct for all values of k. Thus, we obtain the partial fraction decomposition

\begin{aligned}\frac{1}{(1 − x^{a})(1 − x^{b})(1 − x^{c})} & = \frac{d_{1}}{1 − x} + \frac{d_{2}}{(1 − x)^{2}} + \frac{d_{3}}{(1 − x)^{3}} \\ & + ∑_{k=1}^{a−1} \frac{A_{k}}{1 − ζ_{a}^{−k}x} + ∑_{k=1}^{b−1} \frac{B_{k}}{1 − ζ_{b}^{−k}x} + ∑_{k=1}^{c−1} \frac{C_{k}}{1 − ζ_{c}^{−k}x}. \end{aligned}  (1)

On comparing the coefficients of x^{n} on both sides of (1), we find

N(a, b, c; n) = d_{1}+(n+1)d_{2}+ \frac{(n + 2)(n + 1)}{2}d_{3}+∑_{k=1}^{a−1} A_{k}ζ_{a}^{−nk} +∑_{k=1}^{b−1} B_{k}ζ_{b}^{−nk} +∑_{k=1}^{c−1} C_{k}ζ_{c}^{−nk}. (2)

If we substitute x = 0 in (1), we get

1 = d_{1} + d_{2} + d_{3} + ∑_{k=1}^{a−1} A_{k} + ∑_{k=1}^{b−1} B_{k} + ∑_{k=1}^{c−1} C_{k}.  (3)

Upon subtracting (3) from (2), we get

\begin{aligned}N(a, b, c; n) − 1 & = nd_{2} + \frac{n(n + 3)}{2}d_{3} − ∑_{k=1}^{a−1} A_{k}(1 − ζ_{a}^{−nk}) \\ & − ∑_{k=1}^{b−1} B_{k}(1 − ζ_{b}^{−nk}) − ∑_{k=1}^{c−1} C_{k}(1 − ζ_{c}^{−nk}). \end{aligned}  (4)

The usual procedure for finding coefficients of a partial fraction expansion gives the following equations.

d_{3} = \frac{1}{abc},
d_{2} = \frac{a + b + c − 3}{2abc},
A_{k} = \frac{1}{a(1 − ζ_{a}^{bk})(1 − ζ_{a}^{ck})},
B_{k} = \frac{1}{b(1 − ζ_{b}^{ck})(1 − ζ_{b}^{ak})},
C_{k} = \frac{1}{c(1 − ζ_{c}^{ak})(1 − ζ_{c}^{bk})}.

Substituting these back into (4), we have

N(a, b, c; n) = \frac{n(n + a + b + c)}{2abc} + 1 − (\frac{S_{1}}{a} + \frac{S_{2}}{b} + \frac{S_{3}}{c} ) ,  (5)

where

S_{1} = ∑_{k=1}^{a−1} \frac{1 − ζ_{a}^{−nk}}{(1 − ζ_{a}^{bk})(1 − ζ_{a}^{ck})},

S_{2} = ∑_{k=1}^{b−1} \frac{1 − ζ_{b}^{−nk}}{(1 − ζ_{b}^{ck})(1 − ζ_{b}^{ak})},

and

S_{3} = ∑_{k=1}^{c−1} \frac{1 − ζ_{c}^{−nk}}{(1 − ζ_{c}^{ak})(1 − ζ_{c}^{bk})}.

Next, we find S_{1}, S_{2}, and S_{3}. By definition of b′_{1}, we have bb′_{1} ≡ −n (mod a), so ζ_{a}^{−nk} = ζ_{a}^{bb′_{1}k}, and thus,

\begin{aligned}S_{1} & = ∑_{k=1}^{a−1} \frac{1 − ζ_{a}^{bb′_{1}k}}{(1 − ζ_{a}^{bk})(1 − ζ_{a}^{ck})} \\ & = ∑_{k=1}^{a−1} ∑_{j=0}^{b′_{1}−1} \frac{ζ_{a}^{jbk}}{1 − ζ_{a}^{ck}} \\ & = ∑_{k=1}^{a−1} ∑_{j=0}^{b′_{1}−1} \frac{1}{1 − ζ_{a}^{ck}} − ∑_{k=1}^{a−1} ∑_{j=0}^{b′_{1}−1} \frac{1 − ζ_{a}^{jbk}}{1 − ζ_{a}^{ck}} . \end{aligned}  (6)

It is well-known that

∑_{k=1}^{a−1} \frac{1}{1 − ζ_{a}^{ck}} = \frac{a − 1}{2},

and thus, changing the order of summations yields

∑_{k=1}^{a−1} ∑_{j=0}^{b′_{1}−1} \frac{1}{1 − ζ_{a}^{ck}} = b′_{1} (\frac{a − 1}{2}) .  (7)

By definition of c′_{1}, we have cc′_{1} ≡ b (mod a), so ζ_{a}^{jbk} = ζ_{a}^{jcc′_{1}k}, and thus,

\begin{aligned}∑_{k=1}^{a−1} ∑_{j=0}^{b′_{1}−1} \frac{1 − ζ_{a}^{jbk}}{1 − ζ_{a}^{ck}} & = ∑_{k=1}^{a−1} ∑_{j=1}^{b′_{1}−1} \frac{1 − ζ_{a}^{jbk}}{1 − ζ_{a}^{ck}} \\ & = ∑_{k=1}^{a−1} ∑_{j=1}^{b′_{1}−1} \frac{1 − ζ_{a}^{jcc′_{1}k}}{1 − ζ_{a}^{ck}} \\ & = ∑_{k=1}^{a−1} ∑_{j=1}^{b′_{1}−1} ∑_{l=0}^{jc′_{1}−1} ζ_{a}^{lck}. \end{aligned}  (8)

From (6), (7), and (8), we get that

S_{1} = b′_{1} (\frac{a − 1}{2}) − ∑_{k=1}^{a−1} ∑_{j=1}^{b′_{1}−1} ∑_{l=0}^{jc′_{1}−1} ζ_{a}^{lck}.  (9)

Now,

\begin{aligned}∑_{k=1}^{a−1} ∑_{j=1}^{b′_{1}−1} ∑_{l=0}^{jc′_{1}−1} ζ_{a}^{lck} & = ∑_{j=1}^{b′_{1}−1} ∑_{l=0}^{jc′_{1}−1} ∑_{k=1}^{a−1} ζ_{a}^{lck} \\ & = ∑_{j=1}^{b′_{1}−1} ∑_{l=0}^{jc′_{1}−1} ∑_{k=0}^{a−1} ζ_{a}^{lck} − \frac{c′_{1}b′_{1}(b′_{1} − 1)}{2}. \end{aligned}  (10)

We know that ∑_{k=0}^{a−1} ζ_{a}^{lck} ≠ 0 only if a divides l, and in that case, the sum is a. Note that, here we have again used the fact that gcd(a, c) = 1. Therefore,

∑_{l=0}^{jc′_{1}−1} ∑_{k=0}^{a−1} ζ_{a}^{lck} = a (⌊\frac{jc′_{1} − 1}{a}⌋ + 1) .

Since gcd(a, c′_{1}) = 1, and j ≤ b′_{1} − 1 ≤ a − 1, we have

⌊\frac{jc′_{1} − 1}{a}⌋ = ⌊\frac{jc′_{1}}{a} ⌋ .

Hence,

∑_{j=1}^{b′_{1}−1} ∑_{l=0}^{jc′_{1}−1} ∑_{k=0}^{a−1} ζ_{a}^{lck} = a ∑_{j=1}^{b′_{1}−1} (⌊\frac{jc′_{1}}{a} ⌋ + 1) .  (11)

From (9), (10), and (11), we have

\frac{S_{1}}{a} = b′_{1} (\frac{a − 1}{2a}) + \frac{c′_{1}b1^{′}(b′_{1} − 1)}{2a} − ∑_{j=1}^{b′_{1}−1} ⌊\frac{jc′_{1}}{a} ⌋ − (b′_{1} − 1).

We combine the first and last terms to get

\frac{S_{1}}{a} = \frac{c′_{1}b1^{′}(b′_{1} − 1)}{2a} − ∑_{j=1}^{b′_{1}−1} ⌊\frac{jc′_{1}}{a} ⌋ + 1 − b′_{1} (\frac{a + 1}{2a}) .  (12)

Symmetrically, we also have

\frac{S_{2}}{b} = \frac{a′_{2}c′_{2}(c′_{2} − 1)}{2b} − ∑_{j=1}^{c′_{2}−1} ⌊\frac{ja′_{2}}{b} ⌋ + 1 − c′_{2} (\frac{b + 1}{2b}) ,  (13)

and

\frac{S_{3}}{c} = \frac{b′_{3}a′_{3}(a′_{3} − 1)}{2c} − ∑_{j=1}^{a′_{3}−1} ⌊\frac{jb′_{3}}{c} ⌋ + 1 − a′_{3} (\frac{c + 1}{2c}) .  (14)

The result now follows from (5), (12), (13), and (14).

Remark 6. Komatsu [4] obtained equations similar to (5) in the pairwise coprime case. He expressed these sums as summations of some very complicated expressions involving trigonometric functions, which can be solved for small values of a, b, and c. However, the summations become intractable as a, b or c become larger. In Theorem 5, we have expressed the number of solutions in terms of summations of floor functions that are easy to work with, particularly with the help of Lemma 7 below.

2.3 An algorithm to find N(a, b, c; n)

In this section, we describe an efficient way to find the sums in Theorem 5. Let us recall Theorem 1, which states that 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}.

It turns out that we can generalize Theorem 1 as follows:

Lemma 7. Let a, b, c, and K be positive integers such that b < a, c < a, gcd(a, c) = 1, and K = ⌊\frac{bc}{a}⌋. Then,

∑_{i=1}^{b} ⌊\frac{ic}{a}⌋ + ∑_{i=1}^{K} ⌊\frac{ia}{c}⌋ = bK.

Proof. We have

∑_{i=1}^{b} ⌊\frac{ic}{a}⌋ = ∑_{t=1}^{K} tn_{t},

where n_{t} is the number of i such that 1 ≤ i ≤ b and ⌊\frac{ic}{a}⌋ = t. Clearly, if t < K, then

n_{t} = ⌊\frac{(t + 1)a}{c}⌋ − ⌊\frac{ta}{c}⌋;

if t = K, then

n_{t} = b − ⌊\frac{Ka}{c}⌋ .

Therefore,

∑_{i=1}^{b} ⌊\frac{ic}{a}⌋ = ∑_{t=1}^{K−1} (⌊\frac{(t + 1)a}{c}⌋ − ⌊\frac{ta}{c}⌋) t + (b − ⌊\frac{Ka}{c}⌋) K.

We rearrange the terms and solve the summation using telescoping sums to obtain

∑_{i=1}^{b} ⌊\frac{ic}{a}⌋ = ∑_{t=1}^{K−1} (⌊\frac{(t + 1)a}{c}⌋ (t + 1) − ⌊\frac{ta}{c}⌋ t) − ∑_{t=1}^{K−1} ⌊\frac{(t + 1)a}{c}⌋ + bK − K ⌊\frac{Ka}{c}⌋ .

By cancelling terms and solving, we get the required result.

Lemma 7 is helpful to calculate summations of the form ∑_{i=1}^{b} ⌊\frac{ic}{a}⌋ because a summation can be reduced to another of the same form but with a smaller upper limit and a lesser denominator. In Section 2.5, we will see that after two applications of this lemma, the upper limit of summation and the denominator both get reduced to less than half of their original values while the numerator still remains less than the denominator. Remark 8. Observe that if we take a = p, b = \frac{p−1}{2}, and c = q in Lemma 7, then we get Theorem 1. Similar to Eisenstein’s proof of Theorem 1 [1, pp. 19–20], we can also give a geometric proof of Lemma 7 by counting the number of points under the straight line y = \frac{c}{a}x.

Our algorithm for finding the number of non-negative integer solutions N(a, b, c; n) of the equation ax + by + cz = n is as follows:

1. Reduce the given equation to an equation with gcd(a, b, c) = 1 as described in Section 1. Then, reduce it to an equation with pairwise coprime coefficients as described in Section 2.1.

2. Apply the formula in Theorem 5 to express the number of solutions in terms of the three summations involving floor functions.

3. Suppose the first summation has the form ∑_{i=1}^{b_{1}} ⌊\frac{ic_{1}}{a_{1}} ⌋ for some positive integers a_{1},b_{1}, and c_{1} such that b_{1} < a_{1}, c_{1} < a_{1}. Then, apply Lemma 7 to express the summation in terms of the summation ∑_{i=1}^{K_{1}} ⌊\frac{ia_{1}}{c_{1}} ⌋, where K_{1} = ⌊\frac{b_{1}c_{1}}{a_{1}} ⌋.

4. To calculate the sum ∑_{i=1}^{K_{1}} ⌊\frac{ia_{1}}{c_{1}} ⌋, we cannot apply Lemma 7 since a_{1} > c_{1}. However, by the division algorithm, we have a_{1} = c_{1}q + r for some quotient q and remainder r. Then,

∑_{i=1}^{K_{1}} ⌊\frac{ia_{1}}{c_{1}} ⌋ = \frac{qK_{1}(K_{1} + 1)}{2} + ∑_{i=1}^{K_{1}} ⌊\frac{ir}{c_{1}} ⌋ .

Since r < c_{1}, we can use Lemma 7 again to find this sum.

5. Keep repeating Steps 3 and 4 until the first summation in Step 2 is fully solved. Then, follow the same procedure to find the other two summations and hence the number of solutions.

2.4 An example

Let us apply this algorithm to an example. Consider the equation

4452x + 8030y + 9945z = 3857942.

For brevity, let N denote the number of non-negative integer solutions N(4452, 8030, 9945; 3857942) of this equation. Firstly, we reduce this equation to an equation with pairwise coefficients. Note that gcd(4452, 8030) = 2, gcd(4452, 9945) = 3, and gcd(8030, 9945) = 5. By Lemma 3, N is equal to the number of non-negative integer solutions of the equation

742x + 803y + 663z = 128598.

Next, we apply Theorem 5 to get

N = ∑_{i=1}^{129} ⌊\frac{281i}{742}⌋ + ∑_{i=1}^{539} ⌊\frac{621i}{803}⌋ + ∑_{i=1}^{335} ⌊\frac{602i}{663}⌋ − 166300.  (15)

In order to solve the first sum, we apply Lemma 7 to get

∑_{i=1}^{129} ⌊\frac{281i}{742}⌋ = 6192 − ∑_{i=1}^{48} ⌊\frac{742i}{281}⌋ .  (16)

Then, by the division algorithm,

\begin{aligned}∑_{i=1}^{48} ⌊\frac{742i}{281}⌋ & = ∑_{i=1}^{48} (2i + ⌊\frac{180i}{281}⌋) \\ & = 2352 + ∑_{i=1}^{48} ⌊\frac{180i}{281}⌋ . \end{aligned}  (17)

Repeated applications of Lemma 7, followed by the division algorithm, give the following equations.

\begin{aligned}∑_{i=1}^{48} ⌊\frac{180i}{281}⌋ & = 1440 − ∑_{i=1}^{30} ⌊\frac{281i}{180}⌋ \\ & = 975 − ∑_{i=1}^{30} ⌊\frac{101i}{180}⌋ , \end{aligned}  (18)

\begin{aligned}∑_{i=1}^{30} ⌊\frac{101i}{180}⌋ & = 480 − ∑_{i=1}^{16} ⌊\frac{180i}{101}⌋ \\ & = 344 − ∑_{i=1}^{16} ⌊\frac{79i}{101}⌋ , \end{aligned}  (19)

\begin{aligned}∑_{i=1}^{16} ⌊\frac{79i}{101}⌋ & = 192 − ∑_{i=1}^{12} ⌊\frac{101i}{79}⌋ \\ & = 114 − ∑_{i=1}^{12} ⌊\frac{22i}{79}⌋ , \end{aligned}  (20)

\begin{aligned}∑_{i=1}^{12} ⌊\frac{22i}{79}⌋ & = 36 − ∑_{i=1}^{3} ⌊\frac{79i}{22}⌋ \\ & = 18 − ∑_{i=1}^{3} ⌊\frac{13i}{22}⌋ , \end{aligned}  (21)

and

\begin{aligned}∑_{i=1}^{3} ⌊\frac{13i}{22}⌋ & = 3 − ∑_{i=1}^{1} ⌊\frac{22i}{13}⌋ \\ & = 2. \end{aligned}  (22)

From (16) to (22), we get

∑_{i=1}^{129} ⌊\frac{281i}{742}⌋ = 3111.

Repeating the same procedure with the other two summations leads to

∑_{i=1}^{539} ⌊\frac{621i}{803}⌋ = 112277,

and

∑_{i=1}^{335} ⌊\frac{602i}{663}⌋ = 50934.

Substituting these values back in (15), we find that N = 22, i.e., there are 22 solutions of the equation 4452x + 8030y + 9945z = 3857942 in non-negative integer triples (x, y, z).

2.5 Efficiency of the algorithm

We want to find an upper bound for the number of steps required to calculate the number of non-negative integer solutions of the equation ax + by + cz = n. By a step, we mean a basic arithmetic operation on O(log r) bits where r = max(a, b, c). Suppose we want to find the sum ∑_{i=1}^{b} ⌊\frac{ic_{1}}{a_{1}} ⌋ for some positive integers a_{1}, b, and c_{1} such that b < a_{1}, c_{1} < a_{1}, and gcd(c_{1}, a_{1}) = 1.

According to Step 3 of the algorithm, we need to apply Lemma 7 to get ∑_{i=1}^{b} ⌊\frac{ic_{1}}{a_{1}} ⌋ in terms of the sum ∑_{i=1}^{K_{1}} ⌊\frac{ia_{1}}{c_{1}} ⌋ for some K_{1} < c_{1}. Then, as Step 4 in the algorithm describes, we need to apply the division algorithm to obtain a_{1} = c_{1}q_{1} + a_{2}, where a_{2} < c_{1}. Since gcd(c_{1}, a_{1}) = 1, we have gcd(a_{2}, c_{1}) = 1. Thus, the sum ∑_{i=1}^{K_{1}} ⌊\frac{ia_{1}}{c_{1}} ⌋ can be obtained in terms of the sum ∑_{i=1}^{K_{1}} ⌊\frac{ia_{2}}{c_{1}} ⌋. Note that since c_{1} < a_{1}, we have q ≥ 1, and thus,

a_{1} ≥ c_{1} + a_{2} > 2a_{2},

or equivalently a_{2} < \frac{a_{1}}{2} .

According to Step 3 of the algorithm, we again apply Lemma 7 to get the sum ∑_{i=1}^{K_{1}} ⌊\frac{ia_{2}}{c_{1}} ⌋ in terms of the sum ∑_{i=1}^{K_{2}} ⌊\frac{ic_{1}}{a_{2}} ⌋ for some K_{2} < a_{2}. Then, we again apply the division algorithm to obtain c_{1} = a_{2}q_{2} + c_{2} for some c_{2} < a_{2}; we can then express the sum ∑_{i=1}^{K_{2}} ⌊\frac{ic_{1}}{a_{2}} ⌋ in terms of the sum ∑_{i=1}^{K_{2}} ⌊\frac{ic_{2}}{a_{2}} ⌋. Since a_{2} is coprime to c_{1}, it is also coprime to c_{2}. Finally, since K_{2} < a_{2}, c_{2} < a_{2}, and gcd(c_{2}, a_{2}) = 1, we return to Step 3 of the algorithm to find the sum ∑_{i=1}^{K_{2}} ⌊\frac{ic_{2}}{a_{2}} ⌋.

Thus, with two applications of Steps 3 and 4 of the algorithm (i.e., two applications of Lemma 7, with each one followed by an application of the division algorithm), we can obtain the sum ∑_{i=1}^{b} ⌊\frac{ic_{1}}{a_{1}} ⌋ in terms of the sum ∑_{i=1}^{K_{2}} ⌊\frac{ic_{2}}{a_{2}} ⌋, where a_{2} < \frac{a_{1}}{2} . It is also easy to see that K_{2} < \frac{b}{2}. This ensures that the Steps 3, 4, and 5 of the algorithm terminate in O(log a) steps. Hence, the algorithm terminates in O(log t) steps, where t = max(a, b, c).

2.6 Relationship with quadratic residues

Let us recall Eisenstein’s lemma, which states that for given distinct odd primes p and q, the Legendre symbol (\frac{q}{p}) is given by

(\frac{q}{p}) = (−1)^{t},

where

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

Remark 9. The Legendre symbol (\frac{q}{p}) can be calculated in O(log s) steps, where s = max(p, q).

Thus, Eisenstein’s lemma relates Legendre symbols to summations that we have been dealing with while attempting to solve the equation ax + by + cz = n. This suggests the existence of an equation whose number of solutions gives the Legendre symbol (\frac{q}{p}).

Lemma 10. The number of non-negative integer solutions of the equation px+qy+z = \frac{q(p−1)}{2} is given by

N_{p,q} = \frac{p + 1}{2} + ∑_{i=1}^{\frac{p−1}{2}} ⌊\frac{iq}{p} ⌋ .

Proof. Clearly, one way of proving this is by applying Theorem 5. However, we could also prove it directly by fixing y and then calculating the number of possible values for x. For given x and y, z is automatically determined.

Corollary 11. The Legendre symbol (\frac{q}{p}) is given by

(\frac{q}{p}) = (−1)^{N_{p,q}− \frac{p+1}{2}} .

Proof. This follows directly from Eisenstein’s lemma and Lemma 10.

3 Equivalence between two well-known results

The aim of this section is to establish the equivalence between Theorems 1 and 2. Throughout this section, p and q denote distinct odd primes.

Lemma 12. The number of non-negative integer solutions of the equation

px + qy + z = \frac{p(q − 1)}{2} + \frac{q(p − 1)}{2}

is equal to

\frac{p(q − 1)}{2} + \frac{q(p − 1)}{2} + 1 − N_{0},

where N_{0} is the number of natural numbers which cannot be expressed as px + qy for some non-negative integers x and y.

Proof. We first fix z and then calculate the number of solutions of the equation

px + qy = \frac{p(q − 1)}{2} + \frac{q(p − 1)}{2} − z.

Thus, the number of solutions of the equation px + qy + z = \frac{p(q−1)}{2} + \frac{q(p−1)}{2} is equal to

∑_{n=0}^{\frac{p(q−1)}{2} + \frac{q(p−1)}{2}} S_{n},

where S_{n} is the number of solutions of the equation px + qy = n. Clearly, S_{0} = 1. We would require the following well-known results which we would also reprove in Section 4.2 using the methods developed in Section 3.

(i) Whenever 1 ≤ n ≤ (p − 1)(q − 1), S_{n} is either 0 or 1.

(ii) Whenever (p − 1)(q − 1) < n < pq, S_{n} = 1.

Thus, by (i) and the definition of N_{0},

∑_{n=1}^{(p−1)(q−1)} S_{n} = (p − 1)(q − 1) − N_{0}.

Moreover, by (ii),

∑_{n=(p−1)(q−1)+1}^{\frac{p(q−1)}{2} + \frac{q(p−1)}{2}} S_{n} = \frac{p(q − 1)}{2} + \frac{q(p − 1)}{2} − (p − 1)(q − 1).

Therefore,

∑_{n=0}^{\frac{p(q−1)}{2} + \frac{q(p−1)}{2}} S_{n} = S_{0} + ∑_{n=1}^{(p−1)(q−1)} S_{n} + ∑_{n=(p−1)(q−1)+1}^{\frac{p(q−1)}{2} + \frac{q(p−1)}{2}} S_{n}

= \frac{p(q − 1)}{2} + \frac{q(p − 1)}{2} + 1 − N_{0}.

We calculate the number of solutions of the equation px + qy + z = \frac{p(q−1)}{2} + \frac{q(p−1)}{2} in another way by considering four separate cases. Recall that N_{p,q} denotes the number of non-negative solutions of the equation px + qy + z = \frac{q(p−1)}{2}.

Lemma 13. The number of non-negative integer solutions of the equation

px + qy + z = \frac{p(q − 1)}{2} + \frac{q(p − 1)}{2}

is equal to

2(N_{p,q} + N_{q,p}) − (\frac{p + 1}{2} + \frac{q + 1}{2} + 1) .

Proof. Let X, Y, and Z denote \frac{q−1}{2} − x, \frac{p−1}{2} − y, and \frac{q(p−1)}{2} − z, respectively. We split our calculation into four different cases according to

1. X ≥ 0, Y ≥ 0, Z ≥ 0,

2. X ≥ 0, Y ≥ 0, Z < 0,

3. X ≥ 0, Y < 0, or

4. X < 0. We define the following sets:

• Let S_{1}, S_{2}, S_{3}, and S_{4} denote the set of non-negative integer solutions of px + qy + z = \frac{p(q−1)}{2} + \frac{q(p−1)}{2} in Cases 1, 2, 3, and 4, respectively.

• Let T_{1} denote the set of non-negative integer solutions of px + qy + z = \frac{q(p−1)}{2}.

• Let T_{2} denote the set of non-negative integer solutions of px + qy + z = \frac{p(q−1)}{2}.

• Let U denote the set of solutions in T_{2} that satisfy z = 0.

• Let V denote the set of solutions in T_{2} that satisfy y = 0.

• Let W denote the set of solutions in T_{1} that satisfy x = 0. Clearly, |T_{1}| = N_{p,q} and |T_{2}| = N_{q,p}. Moreover, it is straightforward to see that |U| = 1,

|V | = \frac{q+1}{2}, and |W | = \frac{p+1}{2}. Next, we find the cardinalities of the sets S_{1}, S_{2}, S_{3}, and S_{4} by defining the following maps from these sets to T_{1} and T_{2}.

• Define ϕ_{1} : S_{1} → T_{1} such that (x, y, z) ↦ (X, Y, Z).

• Define ϕ_{2} : S_{2} → T_{2} such that (x, y, z) ↦ (x, y, −Z).

• Define ϕ_{3} : S_{3} → T_{2} such that (x, y, z) ↦ (x, −Y, z).

• Define ϕ_{4} : S_{4} → T_{1} such that (x, y, z) ↦ (−X, y, z).

It is easy to verify that ϕ_{1}, ϕ_{2}, ϕ_{3}, and ϕ_{4} are well-defined injective maps and their images are given as follows:

• ϕ_{1}(S_{1}) = T_{1}.

• ϕ_{2}(S_{2}) = T_{2} \ U.

• ϕ_{3}(S_{3}) = T_{2} \ V.

• ϕ_{4}(S_{4}) = T_{1} \ W.

Thus, |S_{1}| = N_{p,q}, |S_{2}| = N_{q,p} − 1, |S_{3}| = N_{q,p} − \frac{q+1}{2}, and |S_{4}| = N_{p,q} − \frac{p+1}{2}. Hence, the total number of non-negative integer solutions of the equation px + qy + z = \frac{p(q−1)}{2} + \frac{q(p−1)}{2} is equal to |S_{1}| + |S_{2}| + |S_{3}| + |S_{4}| = 2(N_{p,q} + N_{q,p}) − (\frac{p+1}{2} + \frac{q+1}{2} + 1).

Upon comparing the number of non-negative integer solutions of the equation px+qy+z = \frac{p(q−1)}{2} + \frac{q(p−1)}{2} obtained in Lemmas 12 and 13, and then using Lemma 10, we find

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

This establishes the required equivalence between Theorems 1 and 2.

4 Some applications of techniques developed in this paper

4.1 Another proof of Theorem 1

In this section, we prove Theorem 1 by counting the number of solutions of an equation in two different ways. Without loss of generality, we can assume q < p. Recall that in Lemma 10, we counted the number of solutions of the equation px + qy + z = \frac{q(p−1)}{2}. Now, we count these in another way.

Lemma 14. If p and q are distinct odd primes such that q < p, then the number of nonnegative integer solutions of the equation px + qy + z = \frac{q(p−1)}{2} is given by

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

Proof. The maximum possible value for x is

⌊\frac{q(p − 1)}{2p}⌋ = ⌊\frac{(q − 1)}{2} + \frac{p − q}{2p} ⌋ = \frac{q − 1}{2}.

Now we consider two cases.

Case 1: Let x = 0. The number of solutions in Case 1 is equal to \frac{p+1}{2}.

Case 2: Let x ≥ 1. Fix x = i. Then, the number of possible values for y is equal to

1 + ⌊ \frac{\frac{q(p−1)}{2} − ip}{q}⌋ = \frac{p − 1}{2} − ⌊\frac{ip}{q}⌋ .

Hence, the total number of solutions in Case 2 is equal to

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

Adding up the number of solutions in both the cases, we get the required result.

Theorem 1 now easily follows from Lemma 10 and Lemma 14.

4.2 Solving the equation ax + by = n

It turns out that we can completely solve the equation ax + by = n by modifying the technique used in Section 2.1. Note that if gcd(a, b) does not divide n, then there is no solution; otherwise we can divide both sides of the equation by gcd(a, b). Thus, without loss of generality, we can assume that gcd(a, b) = 1.

We define the following symbols:

• Let a^{−1} and b^{−1} denote the modular inverses of a with respect to b and b with respect to a, respectively.

• Let a_{1} and b_{1} denote the remainders when na^{−1} is divided by b and nb^{−1} is divided by a, respectively.

• Let M denotes \frac{n−aa_{1}−bb_{1}}{ab}. Note that M is an integer.

We obtain a complete list of non-negative integer solutions of the equation ax + by = n.

Theorem 15. Let a, b, and n be given positive integers such that gcd(a, b) = 1. With the notation above, the non-negative integer solutions of the equation ax + by = n are given as

{(bi + a_{1}, (M − i)a + b_{1}) : 0 ≤ i ≤ M}.

Proof. Let S and T denote the solution sets of ax + by = n and x + y = M, respectively. Then, the function ϕ : S → T such that

(x, y) ↦ (\frac{x − a_{1}}{b} , \frac{y − b_{1}}{a} )

is a bijection with ϕ^{−1} : T → S given by

(x, y) ↦ (bx + a_{1}, ay + b_{1}).

Clearly, T = {(i, M − i) : 0 ≤ i ≤ M}. Then, ϕ^{−1} gives the required form for S.

Remark 16. We briefly describe the motivation behind this bijection. Reducing the given equation ax + by = n modulo b and a, gives the equations x ≡ a_{1} (mod b) and y ≡ b_{1} (mod a), respectively. Thus, we have the expressions x = a_{1} + bu and y = b_{1} + av, for some non-negative integers u and v. Substituting these expressions back in the given equation ax + by = n yields the equation u + v = M.

Corollary 17. Let a, b, and n be given positive integers such that gcd(a, b) = 1. With the notation above, the number of non-negative integer solutions of the equation ax + by = n is given by

N(a, b; n) = 1 + \frac{n − aa_{1} − bb_{1}}{ab} .

This formula is equivalent to the one given in [7].

Corollary 18. The equation ax + by = n has a unique non-negative integer solution if (a − 1)(b − 1) ≤ n < ab.

Proof. If n < ab, then clearly N(a, b; n) < 2. Moreover, since a_{1} ≤ (b − 1) and b_{1} ≤ (a − 1), we have

N(a, b; n) ≥ \frac{n + a + b − ab}{ab}.

Therefore, if (a−1)(b−1) ≤ n, then N(a, b; n) > 0. Thus, whenever (a−1)(b−1) ≤ n < ab, N(a, b; n) = 1.

Recall that the Frobenius number of a set {a_{1}, a_{2}, …, a_{l}} such that gcd(a_{1}, a_{2}, …, a_{l}) = 1 is defined as the largest integer that cannot be expressed in the form

k_{1}a_{1} + k_{2}a_{2} + ⋯ + k_{l}a_{l},

where k_{1}, k_{2}, …, k_{l} are non-negative integers. Corollary 18 gives another proof of the fact that the Frobenius number of the set {a, b} such that gcd(a, b) = 1 is equal to ab − a − b.

4.3 A by-product summation result

We can modify the proof of Lemma 14 to obtain the following result: Theorem 19. Let p and q be distinct odd primes such that q > p, then

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

For example, if we take p = 23 and q = 739, then ⌊\frac{q−p}{2p}⌋ = 15, and we get

∑_{i=354}^{369} ⌊\frac{23i}{739}⌋ = 176.

4.4 An application of Theorem 1

We want to show that Theorem 1 can be used to determine the parity of number of solutions of a particular linear equation. Let p and q be distinct odd primes, and let p^{−1} denote the modular inverse of p with respect to q. Furthermore, let k denote the quantity (\frac{p−1}{2}) + p (\frac{q−1}{2}) p^{−1}. Theorem 20. The number of non-negative integer solutions of the equation

px + qy + z = k

has the same parity as

(k + 1) (\frac{k + p + q}{2} ) + (\frac{q^{2} − 1}{8}) (1 + p^{−1}) + \frac{(p − 1)(q − 1)}{4}.

Proof. By Eisenstein’s lemma, (\frac{p}{q}) = (−1)^{t_{1}} and (\frac{p^{−1}}{q} ) = (−1)^{t_{2}}, where t_{1} = ∑i=1^{\frac{q−1}{2}} ⌊\frac{ip}{q}⌋

and t_{2} = ∑i=1^{\frac{q−1}{2}} ⌊\frac{ip^{−1}}{q} ⌋. Note that

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

Therefore, ∑i=1^{\frac{q−1}{2}} ⌊\frac{ip}{q}⌋ and ∑i=1^{\frac{q−1}{2}} ⌊\frac{ip^{−1}}{q} ⌋ have the same parity. The result now follows directly from Theorems 5 and 1.

5 Acknowledgments

I am highly grateful to A. Tripathi at IIT Delhi who asked me to try to extend his work for 3 variables. Section 2.2 of this note heavily uses the techniques developed in his paper. I also want to thank my friend A. Jain for verifying the reduction process by running a computer program and also for simplifying the expression of N in Section 2.1. I am highly indebted to A. Rattan at SFU and A. Ganguli at IISER Mohali for helpful suggestions on the presentation of this paper. I also wish to express my gratitude to D. Prasad at TIFR, Mumbai for listening to my work very patiently and giving me encouraging remarks.

References

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

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

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

[4] T. Komatsu, On the number of solutions of the Diophantine equation of Frobenius— general case, Math. Commun. 8 (2003), 195–206.

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

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

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

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

Keywords: Frobenius coin problem, linear Diophantine equation, generating function, roots of unity, partial fraction, floor function, Eisenstein’s lemma, Legendre symbol, quadratic reciprocity, Frobenius number.

Received December 21 2017; revised versions received September 25 2019; May 11 2020; May 18 2020. Published in Journal of Integer Sequences, June 11 2020. Minor revision fixing typos, February 1 2021.

Return to Journal of Integer Sequences home page. 20