On a Special Case of the Frobenius Problem

Amitabha Tripathi Department of Mathematics Indian Institute of Technology Hauz Khas New Delhi – 110016 India

               atripath@maths.iitd.ac.in

Abstract

For any set of positive and relatively prime integers A, the set of positive integers that are not representable as a nonnegative integral linear combination of elements of A is always a non-empty finite set. Thus we may define g(A), n(A), s(A) to denote the largest integer in, the number of integers in, and the sum of integers in this finite set, respectively. We determine g(A), n(A), s(A) when A = {a, b, c} with a | lcm(b, c). A particular case of this is when A = {kℓ, ℓm, mk}, with k, ℓ, m pairwise coprime. We also solve a related problem when a | lcm(b, c), thereby providing another proof of the formula for g(A).

1 Introduction

The following problem was the third of the six problems in the Twenty-Fourth International Mathematical Olympiad, held in Paris on July 6–7, 1983:

Let a, b, c be positive integers satisfying (a, b) = (b, c) = (c, a) = 1. Show that 2abc − ab − bc − ca is the largest integer not representable as

xbc + yca + zab

with nonnegative integers x, y, z.

This is a special case of the well-known linear Diophantine problem, posed by Sylvester [7], but known as the Frobenius problem, after G. Frobenius who was largely instrumental in popularizing the problem. Consider a finite set A = {a_{1}, …, a_{k}} of positive integers with gcd A := gcd(a_{1}, …, a_{k}) = 1. Let Γ(A) := {a_{1}x_{1} + ⋯ + a_{k}x_{k} : x_{i} ∈ ℤ_{≥0}}. Then Γ^{c}(A) := ℤ_{≥0} \ Γ(A) can be shown to be a finite set, and this allows us to define the Frobenius number g(A) and the Sylvester number n(A):

g(A) := max Γ^{c}(A), n(A) := |Γ^{c}(A)|.

Here, and elsewhere, |X| denotes the cardinality of the finite set X. The Frobenius problem is to determine g(A) and n(A) in the general case.

For A = {a, b}, gcd(a, b) = 1, Sylvester [7] showed

g(a, b) = ab − a − b, n(a, b) = \frac{1}{2}(a − 1)(b − 1).

Exact values for g(A) have been known only for few cases when |A| > 2 – in some cases when the elements of A satisfy a specific condition. For instance, g(kℓ, ℓm, mk) = 2kℓm − kℓ − ℓm − mk whenever gcd(k, ℓ) = gcd(ℓ, m) = gcd(m, k) = 1. On the other hand, bounds and algorithms to compute g(A), especially in the case |A| = 3, have been a major source of research. Corresponding results for n(A) have been much rarer, even in special cases; refer to [4].

Brown and Shiue [1] introduced the related problem of determining the function

s(A) := ∑_{n∈Γ^{c}(A)} n,

and found

s(a, b) = \frac{1}{12}(a − 1)(b − 1)(2ab − a − b − 1)

when gcd(a, b) = 1; also see [10].

Tripathi [8] introduced the following variation on the Frobenius problem. The set Γ(A) is closed under addition, and so n + Γ(A) ⊆ Γ(A) whenever n ∈ Γ(A). It is conceivable that n ∈ Γ^{c}(A) satisfy a slightly modified condition, replacing Γ(A) by Γ(A) \ {0}. In fact, g(A) is clearly the largest number satisfying such a condition. Thus we study the set given by

S^{⋆}(A) := {n ∈ Γ^{c}(A) : n + Γ^{⋆}(A) ⊂ Γ^{⋆}(A)},

where Γ^{⋆}(A) = Γ(A) \ {0}.

In this note, we consider the set A = {a, b, c} with gcd(a, b) = 1, where a divides lcm(b, c). Observe that the IMO problem introduced at the beginning of this article, involving triples a = kℓ, b = ℓm, c = mk with k, ℓ, m pairwise coprime, satisfies the condition a divides lcm(b, c). We determine g(A), n(A), s(A), and the set S^{⋆}(A), giving more than one proof for each of the results for g(A) and n(A). We list all results that we will base our study on in Section 2, and prove our main results, listed as Theorem 1 and Corollary 2, in Section 3. The results of Corollary 2 follow directly from those of Theorem 1, and the results for g(A), n(A) and S^{⋆}(A) are also special cases of [9, Theorem 1, 2]. The proofs of the results in Corollary 2 are omitted.

Theorem 1. Let A = {a, b, c}, where gcd(a, b, c) = 1 and a | lcm(b, c). Then

(a)

g(a, b, c) = lcm(a, b) + lcm(a, c) − (a + b + c).

(b)

n(a, b, c) = \frac{1}{2}( lcm(a, b) + lcm(a, c) − (a + b + c) + 1).

(c)

s(a, b, c) = \frac{1}{12}(a^{2} + b^{2} + c^{2} + 3abc + 3(ab + bc + ca) − 3(a + b + c)( lcm(a, b) + lcm(a, c))
+2(( lcm(a, b))^{2} + ( lcm(a, c))^{2}) − 1).

(d)

S^{⋆}({a, b, c}) = { lcm(a, b) + lcm(a, c) − (a + b + c)}.

Corollary 2. Let k, ℓ, m be pairwise coprime, positive integers. If σ_{1} = k + ℓ + m, σ_{2} = kℓ + ℓm + mk, and σ_{3} = kℓm, then

g(kℓ, ℓm, mk) = 2σ_{3} − σ_{2}, n(kℓ, ℓm, mk) = \frac{1}{2}(2σ_{3} − σ_{2} + 1),

s(kℓ, ℓm, mk) = \frac{1}{12}(7σ_{3}^{2} − 6σ_{2} σ_{3} + σ_{2}^{2} + σ_{1} σ_{3} − 1), S^{⋆}(\{kℓ, ℓm, mk\}) = \{2σ_{3} − σ_{2}\}.

2 Preliminary results

Suppose A is any set of positive integers with gcd A = 1, and let a ∈ A. For each residue class C modulo a, let m_{C} denote the least integer in Γ(A) ∩ C. It is well known that the functions g, n and s are easily determined from the values of m_{C}. The following result, part (i) of which is due to Brauer and Shockley [2], part (ii) to Selmer [6], and part (iii) to Tripathi [10], is often a key step in this determination.

Proposition 3. [2, 6, 10] Let A be any set of positive integers with gcd(A) = 1. For any a ∈ A,

g(A) = (max_{C} m_{C}) − a, n(A) = \frac{1}{a} ∑_{C} m_{C} − \frac{1}{2}(a − 1),

s(A) = \frac{1}{2a} ∑_{C} m_{C}^{2} − \frac{1}{2} ∑_{C} m_{C} + \frac{1}{12}(a^{2} − 1),

where the maximum and the sums are taken over all nonzero classes C modulo a.

Generating functions naturally enter as a tool in the study of the Frobenius problem. The results in Proposition 4 are the combinatorial analogues of the corresponding results in Proposition 3. The generating function f_{A} for the set A can be used to evaluate the functions g and n (this is almost folklore, but the evaluation of n in this manner actually appears in [7]). The use of the function f_{A} to evaluate s(A) is due to Brown and Shiue [1]; in fact, they used this method to determine s(a, b).

Proposition 4. [1, 7] Let A be any set of positive integers with gcd(A) = 1. Set

f_{A}(t) = ∑_{a∈A} t^{a}.

Then

f_{Γ^{c}(A)}(t) = \frac{1}{1 − t} − f_{Γ(A)}(t),

and

g(A) = deg f_{Γ^{c}(A)}(t), n(A) = lim_{t→1} f_{Γ^{c}(A)}(t), s(A) = lim_{t→1} f′_{Γ^{c}(A)}(t).

The following reduction formulae for g(A), due to Johnson [3] for the three variable case and to Brauer and Shockley [2] for the general case, and for n(A) due to Rødseth [5], are useful in cases when all but one member of A share a common divisor greater than 1.

Proposition 5. [2, 5] Let A be any set of positive integers with gcd(A) = 1. If a ∈ A is such that gcd(A\{a}) = d, and A′ = \frac{1}{d}(A \ \{a\}), then

g(A) = d · g(A′ ∪ \{a\}) + a(d − 1), n(A) = d · n(A′ ∪ \{a\}) + \frac{1}{2}(a − 1)(d − 1).

The set S^{⋆}(A) consists of integers n in Γ^{c}(A) such that translating the set of positive integers in Γ(A) by n results in a subset of Γ(A). Since g(A) ∈ S^{⋆}(A), determining S^{⋆}(A) ensures that g(A) is also determined. The following result is due to Tripathi [8].

Proposition 6. [8] Let A be any set of positive integers with gcd(A) = 1. Let a ∈ A, and let m_{x} denote the least integer in Γ(A) congruent to x modulo a, 1 ≤ x ≤ a − 1. Then

S^{⋆}(A) = {m_{x} − a : m_{x} + m_{y} ≥ m_{x+y} + a for 1 ≤ y ≤ a − 1}.

3 Main results

Throughout this section, we consider the set A = {a, b, c} with gcd(a, b, c) = 1 and a | lcm(b, c). We prove Theorem 1 by using the results in Section 2. More specifically, we use Proposition 3 and Proposition 5 to determine both g(A) and n(A). We also use Proposition 3 to determine s(A). We use Proposition 4 to determine g(A) and n(A) via the proofs using Proposition 3. Finally, we use Proposition 6 to determine S^{⋆}(A), which incidentally also provides another proof for the formula for g(A). The result of Corollary 2 is a direct consequence of Theorem 1; the details are omitted.

3.1 Determining g(A) and n(A) from Proposition 5

We first use the reduction formula given in Proposition 5 to determine both g(A) and n(A). The following lemma is crucial to many results in this section.

Lemma 7. Suppose a, b, c are positive integers, with gcd(a, b, c) = 1. If a | lcm(b, c), then a = gcd(a, b) · gcd(a, c).

Proof. Let p be a prime divisor of a, and let p^{α}, p^{β}, p^{γ} be the highest power of p dividing a, b, c, respectively. Then 0 = min{β, γ} < α ≤ max{β, γ}. Thus a = rs, where r = gcd(a, b), s = gcd(a, c) and gcd(r, s) = 1.

Proof of Theorem 1, (a) and (b). From Lemma 7 we have a = rs, where r = gcd(a, b), s = gcd(a, c) and gcd(r, s) = 1. Note that bs = ab/r = lcm(a, b) and cr = ac/s = lcm(a, c).

If 1 ∈ A, then Γ(A) = ℤ_{≥0}, and so we define g(A) = −1 in this case. We apply Proposition 5.

(a)

g(a, b, c) = r · g (\frac{a}{r}, \frac{b}{r}, c) + c(r − 1)
= r(s · g (1, \frac{b}{r}, \frac{c}{s}) + \frac{b}{r}(s − 1)) + c(r − 1)
= a · g (1, \frac{b}{r}, \frac{c}{s}) + b(s − 1) + c(r − 1)
= bs + cr − a − b − c
= lcm(a, b) + lcm(a, c) − (a + b + c).

(b)

n(a, b, c) = r · n (\frac{a}{r}, \frac{b}{r}, c) + \frac{1}{2}(c − 1)(r − 1)
= r(s · n (1, \frac{b}{r}, \frac{c}{s}) + \frac{1}{2} (\frac{b}{r} − 1) (s − 1)) + \frac{1}{2}(c − 1)(r − 1)
= a · n (1, \frac{b}{r}, \frac{c}{s}) + \frac{1}{2}(b − r)(s − 1) + \frac{1}{2}(c − 1)(r − 1)
= \frac{1}{2}(b − r)(s − 1) + \frac{1}{2}(c − 1)(r − 1)
= \frac{1}{2}(bs + cr − rs − b − c + 1)
= \frac{1}{2}( lcm(a, b) + lcm(a, c) − (a + b + c) + 1).
□

3.2 Determining g(A), n(A) and s(A) from Proposition 3

We next use Proposition 3 to determine g(A), n(A), and s(A). This requires the determination of m_{C} for each nonzero residue class C modulo a. We note that the maximum and the sum in Proposition 3 may also be taken to include m_{0} = 0.

Theorem 8. Let A = {a, b, c}, where gcd(a, b, c) = 1 and a | lcm(b, c). Let m_{i} denote the least integer in Γ({a, b, c}) which is congruent to i modulo a. Then

{m_{i} : 0 ≤ i ≤ a − 1} = {bx + cy : 0 ≤ x ≤ s − 1, 0 ≤ y ≤ r − 1},

where r = gcd(a, b) and s = gcd(a, c).

Proof. Suppose bx_{1} + cy_{1} ≡ bx_{2} + cy_{2} (mod a) with 0 ≤ x_{1}, x_{2} ≤ s − 1 and 0 ≤ y_{1}, y_{2} ≤ r − 1. Then bx_{0} ≡ cy_{0} (mod a) with |x_{0}| < s and |y_{0}| < r. Since r = gcd(a, b) and s = gcd(a, c), bx_{0} mod a ∈ {0, r, 2r, 3r, …, a−r} and cy_{0} mod a ∈ {0, s, 2s, 3s, …, a−s}. Since rs = a and gcd(r, s) = 1, it follows that bx_{0} mod a = cy_{0} mod a = 0. This is only possible if x_{0} = y_{0} = 0 since |x_{0}| < s and |y_{0}| < r, which in turn implies x_{1} = x_{2} and y_{1} = y_{2}. Since rs = a, it follows that the set {bx + cy : 0 ≤ x ≤ s − 1, 0 ≤ y ≤ r − 1} is a complete residue system modulo a.

Fix x_{0} ∈ {0, …, s − 1} and y_{0} ∈ {0, …, r − 1}. We show that bx_{0} + cy_{0} − a ∉ Γ({a, b, c}). Suppose, to the contrary, that bx_{0} + cy_{0} − a = az + bx + cy for some nonnegative integers x, y, z. Let x = x_{1} + ls, 0 ≤ x_{1} ≤ s − 1, l ≥ 0, and y = y_{1} + μr, 0 ≤ y_{1} ≤ r − 1, μ ≥ 0. Then bx_{1} + cy_{1} ≡ bx + cy ≡ bx_{0} + cy_{0} (mod a). By the argument in the preceding paragraph, x_{1} = x_{0} and y_{1} = y_{0}. But this is clearly impossible since bx_{0} + cy_{0} − a = az + bx + cy ≥ bx + cy ≥ bx_{1} + cy_{1} = bx_{0} + cy_{0}. Therefore bx_{0} + cy_{0} − a ∉ Γ({a, b, c}) for each 0 ≤ x_{0} ≤ s − 1 and 0 ≤ y_{0} ≤ r − 1.

Proof of Theorem 1, (a), (b), and (c).

(a) Recall that bs = lcm(a, b) and cr = lcm(a, c). We apply Proposition 3.

g(a, b, c) = ( max_{0≤i≤a−1} m_{i}) − a
= (  max_{0≤x≤s−1, 0≤y≤r−1}(bx + cy)) − a
= b(s − 1) + c(r − 1) − a
= lcm(a, b) + lcm(a, c) − (a + b + c).

(b)

n(a, b, c) = \frac{1}{a} ∑_{i=0}^{a−1} m_{i} − \frac{1}{2}(a − 1)

= \frac{1}{a} ∑_{x=0}^{s−1} ∑_{y=0}^{r−1}(bx + cy) − \frac{1}{2}(a − 1)

= \frac{1}{a} ∑_{x=0}^{s−1} (brx + \frac{1}{2}cr(r − 1)) − \frac{1}{2}(a − 1)

= \frac{1}{a} (\frac{1}{2}brs(s − 1) + \frac{1}{2}crs(r − 1)) − \frac{1}{2}(a − 1)
= \frac{1}{2}(b(s − 1) + c(r − 1)) − \frac{1}{2}(a − 1)
= \frac{1}{2}( lcm(a, b) + lcm(a, c) − (a + b + c) + 1).

s(a, b, c) = \frac{1}{2a} ∑_{i=0}^{a−1} m_{i}^{2} − \frac{1}{2} ∑_{i=0}^{a−1} m_{i} + \frac{1}{12}(a^{2} − 1)

= \frac{1}{2a} ∑_{x=0}^{s−1} ∑_{y=0}^{r−1}(bx + cy)^{2} − \frac{1}{2} ∑_{x=0}^{s−1} ∑_{y=0}^{r−1}(bx + cy) + \frac{1}{12}(a^{2} − 1)

= \frac{1}{2a} ∑_{x=0}^{s−1} (b^{2}rx^{2} + bcr(r − 1)x + \frac{1}{6}c^{2}r(r − 1)(2r − 1)) − \frac{1}{2} ∑_{x=0}^{s−1} (brx + \frac{1}{2}cr(r − 1))

+\frac{1}{12}(a^{2} − 1)

= \frac{1}{12a}b^{2}rs(s − 1)(2s − 1) + \frac{1}{4a}bcr(r − 1)s(s − 1) + \frac{1}{12a}c^{2}rs(r − 1)(2r − 1)

−\frac{1}{4}brs(s − 1) − \frac{1}{4}crs(r − 1) + \frac{1}{12}(a^{2} − 1)

= \frac{1}{12}(b^{2}(s − 1)(2s − 1) + c^{2}(r − 1)(2r − 1))

+\frac{1}{4}(bc(r − 1)(s − 1) − ab(s − 1) − ac(r − 1)) + \frac{1}{12}(a^{2} − 1)

= \frac{1}{12}(2((bs)^{2} + (cr)^{2}) − 3b(bs) − 3c(cr) + b^{2} + c^{2} + 3abc

−3bc(r + s) + 3bc + 3ab + 3ac − 3a(bs + cr) + a^{2} − 1)

= \frac{1}{12}(a^{2} + b^{2} + c^{2} + 3abc + 3(ab + bc + ca) − 3(a + b + c)( lcm(a, b) + lcm(a, c))

+2(( lcm(a, b))^{2} + ( lcm(a, c))^{2}) − 1).

□

3.3 Determining g(A), n(A) and s(A) from Proposition 4

Theorem 8 plays a crucial role in determining g(A), n(A), and s(A) using Proposition 4. In each case, however, we are only able to reduce the problem to an expression that we have already evaluated in Subsection 3.2, but not able to compute these functions directly. In effect, this is a demonstration of how the results in Proposition 3 and Proposition 4 are connected.

From Theorem 8 we know that every n ∈ Γ(A) may be uniquely expressed as bx+cy+az, with x ∈ {0, …, s − 1}, y ∈ {0, …, r − 1}, and z ∈ ℤ_{≥0}. Hence

f_{Γ^{c}(A)}(t) = \frac{1}{1 − t} − f_{Γ(A)}(t)
= \frac{1}{1 − t} − ∑_{\begin{matrix}0≤x≤s−1 \\ 0≤y≤r−1 \\ z≥0 \end{matrix}} t^{bx+cy+az}

= \frac{1}{1 − t} − ( ∑_{0≤x≤s−1} t^{bx}) ( ∑_{0≤y≤r−1} t^{cy}) (∑_{z≥0} t^{az})

= \frac{1}{1 − t} − \frac{1 − t^{bs}}{1 − t^{b}} · \frac{1 − t^{cr}}{1 − t^{c}} · \frac{1}{1 − t^{a}} .

However, it is perhaps more useful to use the equivalent formulation

f_{Γ^{c}(A)}(t) = \frac{1}{1 − t^{a}} ( ∑_{0≤z≤a−1} t^{z} − ∑_{\begin{matrix}0≤x≤s−1 \\ 0≤y≤r−1 \end{matrix}} t^{bx+cy})

to see how the computation of g(A) and n(A) would follow from Proposition 4 and Theorem 8. Deriving the formulae for g(A), n(A), and s(A) directly from either of the two equivalent versions of f_{Γ^{c}(A)}(t) appear to be difficult; instead, we use Proposition 4 to reduce the respective formulae to the situation in Subsection 3.2. The reduction of the formula for s(A) in Proposition 4 to that in Proposition 3 in this special case is tedious, and is omitted in this discussion.

(a)

g(a, b, c) = deg (\frac{1}{1 − t} − ∑_{\begin{matrix}0≤x≤s−1 \\ 0≤y≤r−1 \\ z≥0 \end{matrix}} t^{bx+cy+az}) = max Γ^{c}(A) = (max_{C} m_{C}) − a.

(b)

n(a, b, c) = lim_{t→1} \frac{1}{1 − t^{a}} ( ∑_{0≤z≤a−1} t^{z} − ∑_{\begin{matrix}0≤x≤s−1 \\ 0≤y≤r−1 \end{matrix}} t^{bx+cy})

= lim_{t→1} \frac{1}{−at^{a−1}} ( ∑_{1≤z≤a−1} zt^{z−1} − ∑_{\begin{matrix}0≤x≤s−1 \\ 0≤y≤r−1 \\ (x,y)≠(0,0) \end{matrix}}(bx + cy)t^{bx+cy−1})

= \frac{1}{a} ( ∑_{\begin{matrix}0≤x≤s−1 \\ 0≤y≤r−1 \\ (x,y)≠(0,0) \end{matrix}}(bx + cy) − ∑_{1≤z≤a−1} z)

= \frac{1}{a} ∑_{C} m_{C} − \frac{1}{2}(a − 1).
□

3.4 Deriving n(A) from g(A)

The results of Theorems 1 imply n ∈ Γ({a, b, c}) if and only if g(a, b, c) − n ∉ Γ({a, b, c}). Were this to hold, it would follow by pairing n with g(a, b, c) − n for n ∈ {0, …, g(a, b, c)} that

n(a, b, c) = \frac{1}{2}(g(a, b, c) + 1).

Thus the formula for n(a, b, c) would follow from that of g(a, b, c), and vice-versa, in this case.

It is easy to see that at least one of n and g(a, b, c) − n must belong to Γ^{c}({a, b, c}); if both belonged to Γ({a, b, c}), it would lead to their sum g(a, b, c) belonging to Γ({a, b, c}). Therefore we always have the inequality

n(a, b, c) ≥ \frac{1}{2}(g(a, b, c) + 1),

with equality precisely when

n ∉ Γ({a, b, c}) implies g(a, b, c) − n ∈ Γ({a, b, c})

holds.

Suppose n ∉ Γ({a, b, c}). Then n = bx + cy − az for some x ∈ [0, s − 1], y ∈ [0, r − 1], and z ≥ 1 by Theorem 8. Hence

g(a, b, c)−n = b(s−1)+c(r−1)−a−(bx+cy−az) = b(s−1−x)+c(r−1−y)+a(z−1) ∈ Γ({a, b, c}).

Therefore n(a, b, c) = \frac{1}{2}(g(a, b, c) + 1) holds for A = \{a, b, c\} with a | lcm(b, c).

3.5 Determining the set S^{⋆}(A)

Determining the set S^{⋆}(A) is dependent on being able to compute each m_{C}. Since Theorem 8 determines the set of all m_{C}, we may use Proposition 6 to determine S^{⋆}(A), which in turn gives us g(A).

Proof of Theorem 1 (d). Each m_{C} is of the form bx + cy with 0 ≤ x ≤ s − 1 and 0 ≤ y ≤ r − 1 by Theorem 8 (a); note that m_{0} = 0. Note that bx_{1} + bx_{2} ≡ b((x_{1} + x_{2}) mod s) (mod a) since bs = lcm(a, b) and cy_{1} + cy_{2} ≡ c((y_{1} + y_{2}) mod r) (mod a) since cr = lcm(a, c). So if m_{i} = bx_{1} + cy_{1} and m_{j} = bx_{2} + cy_{2}, then m_{i+j} = b((x_{1} + x_{2}) mod s) + c((y_{1} + y_{2}) mod r).

Although it is apparent from the definition of S^{⋆}(A) that g(A) ∈ S^{⋆}(A), we nevertheless provide a direct proof using Proposition 6. We recall that lcm(a, b) = bs and lcm(a, c) = cr, so that g(A) = lcm(a, b) + lcm(a, c) − (a + b + c) = b(s − 1) + c(r − 1) − a.

Let x ∈ {0, …, s − 1} and y ∈ {0, …, r − 1}, with (x, y) ≠ (0, 0). If x > 0 and y > 0, then

(b(s−1)+c(r−1))+(bx+cy) = b(x−1)+c(y−1)+lcm(a, b)+lcm(a, c) ≥ b(x−1)+c(y−1)+2a.

If x = 0, then y > 0 and

(b(s − 1) + c(r − 1)) + (bx + cy) = b(s − 1) + c(y − 1) + lcm(a, c) ≥ b(s − 1) + c(y − 1) + a.

If y = 0, then x > 0 and

(b(s − 1) + c(r − 1)) + (bx + cy) = b(x − 1) + c(r − 1) + lcm(a, b) ≥ b(x − 1) + c(r − 1) + a.

Hence b(s − 1) + c(r − 1) − a ∈ S^{⋆} by Proposition 6.

Suppose x_{0} ∈ [0, s − 1] and y_{0} ∈ [0, r − 1], with (x_{0}, y_{0}) ≠ (0, 0), (s − 1, r − 1). Then b(s − 1 − x_{0}) + c(r − 1 − y_{0}) is of form m_{x} and

(bx_{0} + cy_{0}) + b(s − 1 − x_{0}) + c(r − 1 − y_{0}) = b(s − 1) + c(r − 1),

so that Proposition 6 fails to hold for at least one x ∈ [1, a − 1]. Hence bx_{0} + cy_{0} − a ∉ S^{⋆} if (x_{0}, y_{0}) ≠ (s − 1, r − 1).

This completes the proof of this theorem. □

Remark 9. For any set of positive integers A with gcd A = 1, it can be shown that n(A) = \frac{1}{2}(1 + g(A)) implies S^{⋆}(A) = \{g(A)\}.

Remark 10. The results of this paper cannot be easily extended to the case A = {a, b_{1}, …, b_{k}} where gcd(a, b_{1}, …, b_{k}) = 1 and a | lcm(b_{1}, …, b_{k}) for k > 2. This is because the divisibility condition a | lcm(b_{1}, …, b_{k}) does not imply a = r_{1} ⋯ r_{k} where r_{i} = gcd(a, b_{i}) for 1 ≤ i ≤ k.

4 Acknowledgments

The author wishes to thank two anonymous referees for several helpful suggestions, including for the results using generating functions.

References

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

[2] A. Brauer and J. E. Shockley, On a problem of Frobenius, J. Reine Angew. Math. 211 (1962), 215–220.

[3] S. M. Johnson, A linear diophantine problem, Canad. J. Math. 12 (1960), 390–398.

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

[5] Ø. J. Rødseth, On a linear diophantine problem of Frobenius, J. Reine Angew. Math. 301 (1978), 171–178.

[6] E. S. Selmer, On the linear diophantine problem of Frobenius, J. Reine Angew. Math. 293/294 (1977), 1–17.

[7] J. J. Sylvester, Problem 7382, in W. J. C. Miller, ed., Mathematical Questions, with their Solutions, from the “Educational Times” 41 (1884), p. 21. Solution by W. J. Curran Sharp.

[8] A. Tripathi, On a variation of the coin exchange problem for arithmetic progressions, Integers 3 (2003), Article A01.

[9] A. Tripathi, On a linear diophantine problem of Frobenius, Integers 6 (2006), Article A14.

[10] A. Tripathi, On sums of positive integers that are not of the form ax + by = n, Amer. Math. Monthly 115 (2008), 363–364.

2010 Mathematics Subject Classification: Primary 11D07. Keywords: linear Diophantine equation, Frobenius problem.

Received April 27 2017; revised versions received May 1 2017; June 15 2017; June 26 2017. Published in Journal of Integer Sequences, July 2 2017.

Return to Journal of Integer Sequences home page.