INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A14

ON A LINEAR DIOPHANTINE PROBLEM OF FROBENIUS

Amitabha Tripathi

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

                         atripath@maths.iitd.ac.in

Received: 3/17/06, Revised: 4/17/06, Accepted: 4/24/06, Published: 5/3/06

Abstract

Let a_{1}, a_{2}, …, a_{k} be positive and pairwise coprime integers with product P. For each i, 1 ≤ i ≤ k, set A_{i} = P/a_{i}. We find closed form expressions for the functions g(A_{1}, A_{2}, …, A_{k}) and n(A_{1}, A_{2}, …, A_{k}) that denote the largest (respectively, the number of) N such that the equation A_{1}x_{1} + A_{2}x_{2} + ⋯ + A_{k}x_{k} = N has no solution in nonnegative integers x_{i}. This is a special case of the well-known Coin Exchange Problem of Frobenius.

1. Introduction

Given positive integers a_{1}, a_{2}, …, a_{k}, relatively prime, it is well-known that for all sufficiently large N the equation

a_{1}x_{1} + a_{2}x_{2} + ⋯ + a_{k}x_{k} = N  (1)

has a solution with nonnegative integers x_{i}. If we denote by g(a_{1}, a_{2}, …, a_{k}) the largest integer N such that (1) has no solution in nonnegative integers, then it is a well-known result of Sylvester that g(a_{1}, a_{2}) = a_{1}a_{2} − a_{1} − a_{2}. The related functions n(a_{1}, a_{2}, …, a_{k}) and s(a_{1}, a_{2}, …, a_{k}) denote the number of positive integers N for which (1) has no solution and the sum of such integers, respectively. While it is well-known that n(a_{1}, a_{2}) = (a_{1} − 1)(a_{2} − 1)/2, the corresponding result s(a_{1}, a_{2}) = (a_{1} − 1)(a_{2} − 1)(2a_{1}a_{2} − a_{1} − a_{2} − 1)/12 is more recent and less known [4]. Except when the a_{i}’s are in arithmetic progression [1, 5, 9, 15] or in certain other particular cases with three or more variables [2, 3, 7, 10, 11, 12, 13, 14], there is no closed form expression for either g or n. More information on this problem may be found in the recently published monograph [8].

The purpose of this note is to obtain a formula for the functions g and n in a special case. More specifically, we shall henceforth assume that the a_{i}’s are pairwise coprime with product P, and set A_{i} = P/a_{i} for 1 ≤ i ≤ k. We determine g(A_{1}, A_{2}, …, A_{k}) and n(A_{1}, A_{2}, …, A_{k}) by two methods. The first method uses a reduction formula while the second method is direct. We note that g(A_{1}, A_{2}) = g(a_{1}, a_{2}) and n(A_{1}, A_{2}) = n(a_{1}, a_{2}).

We close by showing that the set S^{⋆} introduced in [16] has exactly one element in the special case we are dealing with. Since it is known (and easy to see from the definition of S^{⋆}) that g ∈ S^{⋆}, we have further confirmation of the result for g in the special case.

2. Main Results

For the sake of completeness, we prove two well-known results that help in evaluating the functions g and n in the general case.

Lemma 1 [3, 13]. Let gcd(a_{1}, a_{2}, …, a_{k}) = 1, and for 1 ≤ j ≤ a_{1} − 1, let m_{j} denote the least positive integer N congruent to j mod a_{1} such that (1) has a solution in nonnegative integers. Then

(a) g(a_{1}, a_{2}, …, a_{k}) = max_{1≤j≤a_{1}−1} m_{j} − a_{1};

(b) n(a_{1}, a_{2}, …, a_{k}) = \frac{1}{a_{1}} ∑_{j=1}^{a_{1}−1} (m_{j} − j) = \frac{1}{a_{1}} ∑_{j=1}^{a_{1}−1} m_{j} − \frac{a_{1} − 1}{2}.

Proof.

(a) From the definition of m_{i} it follows that m_{i} − a_{1} is not representable by a_{1}, …, a_{k} in nonnegative integers for each i, 1 ≤ i ≤ a_{1}. On the other hand, any N greater than each m_{i} − a_{1} and congruent to j mod a_{1} must be at least m_{j}, and hence representable by a_{1}, …, a_{k} in nonnegative integers.

(b) Since the numbers congruent to j mod a_{1} and not representable by a_{1}, …, a_{k} in nonnegative integers form an arithmetic progression with first term j, last term m_{j} − a_{1} and common difference a_{1}, their number is given by (m_{j} − j)/a_{1}. The second part of the lemma now easily follows. □

Lemma 2 [6, 11]. Let a_{1}, a_{2}, …, a_{k} be positive integers. If gcd(a_{2}, …, a_{k}) = d and a_{j} = da′_{j} for each j > 1, then

(a) g(a_{1}, a_{2}, …, a_{k}) = d g(a_{1}, a′_{2}, …, a′_{k}) + a_{1}(d − 1);

(b) n(a_{1}, a_{2}, …, a_{k}) = d n(a_{1}, a′_{2}, …, a′_{k}) + \frac{1}{2}(a_{1} − 1)(d − 1); Proof. As in Lemma 1, for each j, 1 ≤ j ≤ a_{1} − 1, let m_{j} and m′_{j} denote the least positive integer congruent to j mod a_{1} representable as a nonnegative linear combination of a_{1}, a_{2}, …, a_{k} and a_{1}, a′_{2}, …, a′_{k}, respectively. Since each such m_{j} and m′_{j} must also be representable as a nonnegative linear combination of a_{2}, …, a_{k} and of a′_{2}, …, a′_{k}, respectively, it follows that {m_{j} : 1 ≤ j ≤ a_{1} − 1} = {dm′_{j} : 1 ≤ j ≤ a_{1} − 1}. We now apply Lemma 1.

For part (a) we have

g(a_{1}, a_{2}, …, a_{k}) = max_{1≤j≤a_{1}−1} m_{j} − a_{1}
= d ( max_{1≤j≤a_{1}−1} m′_{j} − a_{1}) + a_{1}(d − 1)
= d g(a_{1}, a′_{2}, …, a′_{k}) + a_{1}(d − 1).

For part (b) we have

n(a_{1}, a_{2}, …, a_{k}) = \frac{1}{a_{1}} ∑_{j=1}^{a_{1}−1} m_{j} − \frac{1}{2}(a_{1} − 1)

= d (\frac{1}{a_{1}} ∑_{j=1}^{a_{1}−1} m′_{j} − \frac{1}{2}(a_{1} − 1)) + \frac{1}{2}(a_{1} − 1)(d − 1)
= d n(a_{1}, a′_{2}, …, a′_{k}) + \frac{1}{2}(a_{1} − 1)(d − 1).
□

Theorem 1. Let a_{1}, a_{2}, …, a_{k} be pairwise coprime, positive integers with product P. Let A_{i} = P/a_{i} for 1 ≤ i ≤ k. Let σ_{r} denote the sum of the products of the a_{i}’s taken r at a time, so that σ_{k} = P and σ_{k−1} = A_{1} + A_{2} + ⋯ + A_{k}. Then

(a) g(A_{1}, A_{2}, …, A_{k}) = (k − 1)σ_{k} − σ_{k−1};

(b) n(A_{1}, A_{2}, …, A_{k}) = \frac{1}{2}\{(k − 1)σ_{k} − σ_{k−1} + 1\}.

Proof. This is a direct consequence of Lemma 2. We induct on k. If k = 2, these are just the well-known results mentioned in the Introduction. We observe that A_{k} is a multiple of A_{j}/a_{k} = A′_{j} for each j ≠ k since A_{j}|a_{k}A_{k} = σ_{k} and a_{k}|A_{j} if j ≠ k.

For part (a), by the induction hypothesis, we have

g(A_{1}, A_{2}, …, A_{k}) = a_{k} g (\frac{A_{1}}{a_{k}} , \frac{A_{2}}{a_{k}} , …, \frac{A_{k−1}}{a_{k}} , A_{k}) + A_{k}(a_{k} − 1)
= a_{k} g (\frac{A_{1}}{a_{k}} , \frac{A_{2}}{a_{k}} , …, \frac{A_{k−1}}{a_{k}} ) + σ_{k} − A_{k}
= a_{k} g(A′_{1}, A′_{2}, …, A′_{k−1}) + σ_{k} − A_{k}
= (k − 2)σ_{k} − (σ_{k−1} − A_{k}) + σ_{k} − A_{k}
= (k − 1)σ_{k} − σ_{k−1}.

For part (b), by the induction hypothesis, we have

n(A_{1}, A_{2}, …, A_{k}) = a_{k} n (\frac{A_{1}}{a_{k}} , \frac{A_{2}}{a_{k}} , …, \frac{A_{k−1}}{a_{k}} , A_{k}) + \frac{1}{2}(a_{k} − 1)(A_{k} − 1)
= a_{k} n (\frac{A_{1}}{a_{k}} , \frac{A_{2}}{a_{k}} , …, \frac{A_{k−1}}{a_{k}} ) + \frac{1}{2}σ_{k} − \frac{1}{2}a_{k} − \frac{1}{2}A_{k} + \frac{1}{2}
= a_{k} n(A′_{1}, A′_{2}, …, A′_{k−1}) + \frac{1}{2}σ_{k} − \frac{1}{2}a_{k} − \frac{1}{2}A_{k} + \frac{1}{2}
= \frac{1}{2}\{(k − 2)σ_{k} − (σ_{k−1} − A_{k}) + a_{k} + σ_{k} − a_{k} − A_{k} + 1\}
= \frac{1}{2}\{(k − 1)σ_{k} − σ_{k−1} + 1\}.
□

The proof of Theorem 1 given above is based on Lemma 2. It is indeed possible to give an independent proof. Using the notation of Theorem 1, we give a

Second proof of Theorem 1. Let a_{1}, a_{2}, …, a_{k} be pairwise coprime, positive integers. Let σ_{r} denote the sum of the products of the a_{i}’s taken r at a time, and let A_{j} = σ_{k}/a_{j} for 1 ≤ j ≤ k. Then g(A_{1}, A_{2}, …, A_{k}) = (k − 1)σ_{k} − σ_{k−1}.

Proof. If each x_{j} ≥ 0 and

A_{1}x_{1} + A_{2}x_{2} + ⋯ + A_{k}x_{k} = (k − 1)σ_{k} − σ_{k−1},  (2)

A_{j}x_{j} ≡ −A_{j} mod a_{j}, so that x_{j} ≥ a_{j} − 1 since gcd(a_{j}, A_{j}) = 1. But then

∑_{j=1}^{k} A_{j}x_{j} ≥ ∑_{j=1}^{k} A_{j}(a_{j} − 1) ≥ kσ_{k} − σ_{k−1},

and (2) has no solution in nonnegative integers.

Since the A_{i}x_{i} + A_{j}x_{j} = A_{i}(x_{i} + a_{i}) + A_{j}(x_{j} − a_{j}), and since gcd(A_{1}, A_{2}, …, A_{k}) = 1, we can always write any N in the form A_{1}x_{1} + A_{2}x_{2} + ⋯ + A_{k}x_{k} with 0 ≤ x_{j} ≤ a_{j} − 1 for 1 ≤ j ≤ k − 1. Now, if N > (k − 1)σ_{k} − σ_{k−1} and we choose x_{j} as above, then

x_{k} = \frac{N − ∑_{j=1}^{k−1} A_{j}x_{j}}{A_{k}} > \frac{∑_{j=1}^{k−1} A_{j}(a_{j} − x_{j} − 1)}{A_{k}} − 1 ≥ −1.

Thus x_{k} ≥ 0, and every N greater than (k − 1)σ_{k} − σ_{k−1} is expressible as a nonnegative linear combination of the A_{j}’s. □

Lemma 3. Let a_{1}, a_{2}, …, a_{k} be pairwise coprime, positive integers, and let A_{j} = σ_{k}/a_{j} for 1 ≤ j ≤ k. If p, q are integers such that p + q = g(A_{1}, A_{2}, …, A_{k}), then exactly one of the equations A_{1}x_{1} + A_{2}x_{2} + ⋯ + A_{k}x_{k} = p and A_{1}x_{1} + A_{2}x_{2} + ⋯ + A_{k}x_{k} = q is solvable in nonnegative integers x_{j}.

Proof. If both the equations had a solution, so would g(A_{1}, A_{2}, …, A_{k}), contradicting its definition. Suppose A_{1}x_{1} + A_{2}x_{2} + ⋯ + A_{k}x_{k} = p has no solution in nonnegative integers. Choose x_{j} such that 0 ≤ x_{j} ≤ a_{j} − 1 for 1 ≤ j ≤ k − 1. But then x_{k} < 0, and

q = (k − 1)σ_{k} − σ_{k−1} − p = ∑_{j=1}^{k−1} A_{j}(a_{j} − x_{j} − 1) + A_{k}(−x_{k})

is expressible in the given form, proving the lemma. □

Corollary 1. Let a_{1}, a_{2}, …, a_{k} be pairwise coprime, positive integers. Let σ_{r} denote the sum of the products of the a_{i}’s taken r at a time, and let A_{j} = σ_{k}/a_{j} for 1 ≤ j ≤ k. Then n(A_{1}, A_{2}, …, A_{k}) = \frac{1}{2}\{(k − 1)σ_{k} − σ_{k−1} + 1\}.

Proof. If we pair p with q whenever p + q = g(A_{1}, A_{2}, …, A_{k}) and p, q ≥ 0, by Lemma 1,

n(A_{1}, A_{2}, …, A_{k}) = \frac{1}{2} \{1 + g(A_{1}, A_{2}, …, A_{k})\} .

The corollary now follows from Theorem 1. □

The evaluation of g given in Theorem 1 can also be derived by explicitly determining the set S^{⋆}, introduced in [16], since g(a_{1}, a_{2}, …, a_{k}) is the largest element in S^{⋆}(a_{1}, a_{2}, …, a_{k}). For positive and coprime integers a_{1}, a_{2}, …, a_{k}, let Γ^{⋆} denote the positive integers in the set {a_{1}x_{1} + a_{2}x_{2} + ⋯ + a_{k}x_{k} : x_{j} ≥ 0}. Then

S^{⋆}(a_{1}, a_{2}, …, a_{k}) := {n ∉ Γ^{⋆} : n + Γ^{⋆} ⊂ Γ^{⋆}} ⊆ {m_{j} − a_{1} : 1 ≤ j ≤ a_{1} − 1}.

Moreover,

m_{j} − a_{1} ∈ S^{⋆}(a_{1}, a_{2}, …, a_{k}) ⟺ m_{j} + m_{i} > m_{j+i} for 1 ≤ i ≤ a_{1} − 1.  (3)

We refer to [16] for the more notations and results. With the notations above, we show that S^{⋆}(A_{1}, A_{2}, …, A_{k}) = {(k − 1)σ_{k} − σ_{k−1}} for each k ≥ 2. Since g(a_{1}, a_{2}, …, a_{k}) ∈ S^{⋆}(a_{1}, a_{2}, …, a_{k}), this further verifies the first result of Theorem 1.

Theorem 2. Let a_{1}, a_{2}, …, a_{k} be pairwise coprime, positive integers. Let σ_{r} denote the sum of the products of the a_{i}’s taken r at a time, and let A_{j} = σ_{k}/a_{j} for 1 ≤ j ≤ k. Then S^{⋆}(A_{1}, A_{2}, …, A_{k}) = {(k − 1)σ_{k} − σ_{k−1}} for k ≥ 2.

Proof. We prove the result by inducting on k. The case k = 2 is a special case of the main result in [16]. Given pairwise coprime, positive integers a_{1}, a_{2}, …, a_{k}, define integers A_{1}, A_{2}, …, A_{k} as above. As in the proof of Lemma 2, for each j, 1 ≤ j ≤ A_{k} − 1, let M_{j} and M′_{j} denote the least positive integer congruent to j mod A_{k} representable as a nonnegative linear combination of A_{1}, A_{2}, …, A_{k} and A′_{1}, A′_{2}, …, A′_{k−1}, A_{k}, respectively, where A′_{j} = A_{j}/a_{k} for 1 ≤ j ≤ k − 1. Then {M_{j} : 1 ≤ j ≤ A_{k} − 1} = {a_{k}M′_{j} : 1 ≤ j ≤ A_{k} − 1}. Observe that each A′_{i} divides A_{k}, and that {A′_{1}, A′_{2}, …, A′_{k−1}} is just the set of A_{i}’s corresponding to a_{1}, a_{2}, …, a_{k−1}. From (3), M_{j} − A_{k} ∈ S^{⋆}(A_{1}, A_{2}, …, A_{k}) if and only if M_{j} + M_{i} > M_{j+i} for 1 ≤ i ≤ A_{k} − 1, which holds precisely when M′_{j} + M′_{i} > M′_{j+i} for 1 ≤ i ≤ A_{k} − 1. Thus M_{j} − A_{k} ∈ S^{⋆}(A_{1}, A_{2}, …, A_{k}) if and only if M′_{j} − A_{k} ∈ S^{⋆}(A′_{1}, A′_{2}, …, A′_{k−1}, A_{k}) = S^{⋆}(A′_{1}, A′_{2}, …, A′_{k−1}), which is the set {(k − 2)a_{1}a_{2} ⋯ a_{k−1} − (A′_{1} + ⋯ + A′_{k−1})}, by the induction hypothesis. It now follows that S^{⋆}(A_{1}, A_{2}, …, A_{k}) = {a_{k}M′_{j} − A_{k}} = {(k − 2)a_{1}a_{2} ⋯ a_{k} −a_{k}(A′_{1} +⋯+A′_{k−1})+a_{k}A_{k} −A_{k}} = {(k −1)a_{1}a_{2} ⋯ a_{k} −(A_{1} +A_{2} +⋯+A_{k})}, as desired. □

Acknowledgment. The author wishes to thank the referee for some valuable comments and for pointing out the eighth reference.

References

[1] P. T. Bateman, Remark on a Recent Note on Linear Forms, American Mathematical Monthly 65 (1958), 517-518.

[2] A. Brauer, On a Problem of Partitions, American Journal of Mathematics 64 (1942), 299-312.

[3] A. Brauer and J. E. Shockley, On a problem of Frobenius, Crelle 211 (1962), 215-220.

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

[5] D. D. Grant, On linear forms whose coefficients are in Arithmetic progression, Israel Journal of Mathematics 15 (1973), 204-209.

[6] S. M. Johnson, A Linear Diophantine Problem, Canadian Journal of Mathematics 12 (1960), 390-398.

[7] A. Nijenhuis and H. S. Wilf, Representations of integers by linear forms in non negative integers, Journal of Number Theory 4 (1972), 98-106.

[8] J. L. Ramirez Alfonsin, The Frobenius Diophantine Problem, Oxford University Press, 2006.

[9] J. B. Roberts, Note on Linear Forms, Proceedings of the American Mathematical Society 7 (1956), 465-469.

[10] J. B. Roberts, On a Diophantine problem, Canadian Journal of Mathematics 9 (1957), 219-222.

[11] Ö. J. Rödseth, On a linear Diophantine problem of Frobenius, Crelle 301 (1978), 171-178.

[12] Ö. J. Rödseth, On a linear Diophantine problem of Frobenius II, Crelle 307/308 (1979), 431-440.

[13] E. S. Selmer, On the linear Diophantine problem of Frobenius, Crelle 293/294 (1977), 1-17.

[14] E. S. Selmer and Ö. Beyer, On the linear Diophantine problem of Frobenius in three variables, Crelle 301 (1978), 161-170.

[15] A. Tripathi, The Coin Exchange Problem for Arithmetic Progressions, American Mathematical Monthly (1994), no. 10, 779-781.

[16] A. Tripathi, On a variation of the Coin Exchange Problem for Arithmetic Progressions, Integers: Electronic Journal of Combinatorial Number Theory (2003), 3, no. A01, 1-5.