# On the Solutions of Three-Variable Frobenius-Related Problems Using Order Reduction Approach

Authors: Tian-Xiao He; Peter J.-S. Shiue; Rama Venkat
Journal: International Journal of Mathematics and Mathematical Sciences
 (2021)

---

## Abstract

This paper presents a new approach to determine the number of solutions of three-variable Frobenius-related problems and to find their solutions by using order reducing methods. Here, the order of a Frobenius-related problem means the number of variables appearing in the problem. We present two types of order reduction methods that can be applied to the problem of finding all nonnegative solutions of three-variable Frobenius-related problems. The first method is used to reduce the equation of order three from a three-variable Frobenius-related problem to be a system of equations with two fixed variables. The second method reduces the equation of order three into three equations of order two, for which an algorithm is designed with an interesting open problem on solutions left as a conjecture.


---

## Body

## 1. Introduction

Given positive integersa1,a2,…,aℓ with gcda1,a2,…,aℓ=1, we say n∈ℕ is representable if(1)n=m1a1+m2a2+⋯+mℓaℓ,for some m1,m2,…,mℓ∈ℕ. The well-known linear Diophantine problem asks for the largest integer g=ga1,a2,…,aℓ that is not representable. The linear Diophantine problems of Frobenius have many alternative names, such as the Frobenius coin problem, the postage stamp problem, and the chicken McNugget problem (cf. for example, Bardomero and Beck [1]).Sylvester [2] showed that ga1,a2=a1−1a2−1, that is, for any two relatively prime positive integers a1 and a2, the greatest integer that cannot be written in the form m1a1+m2a2 for nonnegative integers m1andm2 is a1−1a2−1−1=a1a2−a1−a2.A consequence of the theorem is that there are exactlym−1n−1/2 positive integers, which cannot be expressed in the form am+bn. The proof is based on the fact that, in each pair of the form k,m−1n−1−k−1, exactly one element is expressible.There are many stories surrounding the origin of the Chicken McNugget theorem. However, the most popular by far remains that of the Chicken McNugget. Originally, McDonald’s sold its nuggets in packs of 9 and 20. Thus, to find the largest number of nuggets that could not have been bought with these packs creates the Chicken McNugget Theorem (the answer worked out to be 151 nuggets). More description on the history of McNugget problem can be found, for example, in [3, 4].In Chapman and O’Neill [5], the McNugget number of order 3 is defined. We call n a McNugget number associated with p,q,ℓ, if there exists an ordered triple x,y,z of nonnegative integers such that(2)px+qy+ℓz=n,for p,q,ℓ,andn>0 and p≤q≤ℓ, where a,b,andc≥0. The paper [5] considers the case of p,q,ℓ=6,9,20, namely, the nonnegative solutions of(3)6x+9y+20z=n.The nonnegative solutions of equation (3) give the partitions of n into parts 6, 9, and 20. The number of those partitions is presented in the sequence A214772. It is worth noting that the coefficients of equation (3) are not pairwise relatively prime. In this paper, we consider the following related problems: (P1) for a given number n, how many solutions, if exist, does equation (2) have? (P2) How to solve for all solutions with respect to given n?Alfonsín [3], Hsu et al. [6], and Bardomero and Beck [1] presented a method to solve the problems similar to equation (3) by using the generating function. However, a large amount partial fraction steps are needed because the numbers 6, 9, and 20 are big. Chou et al. [7] gave a matrix method, which can be used to solve equation (3). However, this method needs to solve a complicated system of inequalities. In this paper, we present a simple approach to solve the above two problems, which can be extended to a general three-variable Frobenius-related problem. More materials on the linear Diophantine problem of Frobenius can be found in [8–11].Denote the number of the solutions of equation (2) for a given n by Np,q,ℓ,n. Let A=a1,a2,…,ak be a set of k relatively prime positive integers. Let pAn denote the partition function of n with parts in A, that is, pA is the number of partitions of n with parts belonging to A. Thus, if a,b, and c are relatively prime positive integers, then Na,b,c,n=pa,b,cn. To find pa1,a2,a3n, where a1,a2,a3 are relatively primes, we reduce it to pAn with relatively prime A=a,b and use the following formula to figure pa,bn: for A=a,b, where a,b=1, n=qab+r with 0≤r<ab. Brown, Chou, and one of the authors [12] found the table as follows:(4)pa,bn=q+1,ifab−a−b<r<ab;q,ifr=ab−a−b;q+1,ifr<ab−a−bandaa′r+bb′r+r=2ab;q,ifr<ab−a−bandaa′r+bb′r+r=ab,where a′n and b′n are defined by a′n≡−nb with 1≤a′n≤b and b′nb≡−na with 1≤b′n≤a, respectively. Then, Np,q,ℓ,n can be found accordingly.In the next section, we use the table to give the number of solutions of equation (2). The process to derive the result also suggests an order reduction algorithm. In Section 3, we will present another order reduction algorithm based on the Bézout’s lemma. A conjecture about the solution structure is also given.


## 2. The Number of Solutions of Equation (2)

First, we establish the following result about the number of the solutions of equation (2).Theorem 1.
LetNp,q,ℓ,n be the number of the solutions of equation (2), and let p,q=u. Denote the set A=p/u,q/u. Then,(5)Np,q,ℓ,n=∑k=0n−jℓ/uℓpAn−jℓ/u−ℓk−ℓk,where j∈0,1,…,u−1 satisfies n−ℓj≡0modu.Proof.
Ifp,q=u, then equation (2) can be written as(6)xup+yuq=1un−ℓz.
Ifx,y, and z are solutions of the above equation for a given n, we need n−ℓz≡0modu. If n≡j1u with j1∈0,1,…,u−1, then we may find z=uk+j for k≥0 and some j∈0,1,…,u−1 such that(7)n−ℓz=n−ℓuk+j=αu+j1−ℓuk+j≡j1−ℓjmodu≡0modu,provided that ℓj≡j1modu. Since n−ℓz=n−ℓuk+j≥0, we have 0≤k≤n−jℓ/uℓ. Since p/u,q/u=1, the number of the solution of equation (6) is(8)pp/u,q/un−zℓu=pp/u,q/un−jℓu−ℓk,and the number of solutions of equation (2) is given by equation (5).Theorem 2.
LetNp,q,ℓ,n be the number of the solutions of equation (2), and let p,q=u. Denote A=p/u,q/u. Then,(9)Np,q,ℓ,n=∑0≤z≤n/ℓu|n−zℓpAn−zℓu=∑0≤z≤n/ℓu|n−zℓ1+Mz,where(10)Mz=upqn−zℓ−pa1z−qb1z,if n−zℓ−pa1z−qb1z≥0, and −1 otherwise, i.e., Mz=max−1,un−zℓ−pa1z−qb1z/pq, a1z, and b1z are the smallest nonnegative integers satisfying(11)pa1z≡n−zℓmodq,qb1z≡n−zℓmodp,respectively. Furthermore, the set of all nonnegative solutions of Diophantine equation (2) is(12)quiz+a1z,Mz−izpu+b1z,z:0≤iz≤Mz,for all 0≤z≤n/ℓ with u|n−zℓ, where Mz is defined by equation (10) if u/pqn−zℓ−pa1z−qb1z≥0; otherwise, nonnegative solution set equation (12) does not exist.Proof.
We may use the formula shown in Binner (Corollary 17 in [13]) to find the number pp/u,q/un−zℓ/u. Denote a=p/u, b=q/u, and mz=n−zℓ/u0≤z≤⌊n/ℓ⌋. Thus, gcda,b=1, and we need mz to be a nonnegative integer. In general, from [13], the number of nonnegative solutions of ax+by=mz is(13)pa,bmz=1+mz−aa1z−bb1zab,if the second term on the right-hand side of equation (13) is nonnegative, where a1z is the remainder when mza−1 is divided by b, b1 is the remainder when mzb−1 is divided by a, and a−1 and b−1 are the modular inverse of a with respect to b and b with respect to a, respectively, namely,(14)mza−1≡a1zmodb,mzb−1≡b1zmoda.
It is obvious that the last two equations are equivalent to(15)mz≡aa1zmodb,mz≡bb1zmoda.
Thus,a1z≥0 and b1z≥0 can be found by solving (cf. Remark 16 of [13])(16)ax≡mzmodb,by≡mzmoda,for x≡a1zmodb and y≡b1zmoda. From equation (16), we have equation (11) by noticing a=p/u and b=q/u. Denote Mz=mz−aa1z−bb1z/ab if it is nonnegative. Substituting mz=n−zℓ/u, a=p/u, and b=q/u into Mz, we obtain equation (10). Then, from equation (13), we have(17)pp/u,q/umz=1+Mz=1+upqn−zℓ−pa1z−qb1z,if u/pqn−zℓ−pa1z−qb1z≥0, which implies equation (9).
Furthermore, from [13], the set of all nonnegative solutions of ax+by=mz is(18)bi+a1z,Mz−ia+b1z:0≤i≤Mz,when Mz=u/pqn−zℓ−pa1z−qb1z≥0, which implies equation (12). If u/pqn−zℓ−pa1z−qb1z<0, then the set shown in equation (18) does not exist, which implies that 1+Mz in equation (9) must be zero. Hence, Mz=−1 in this case, which completes the proof of the theorem.
We use the formula of the number of nonnegative solutions ofax+by=m given in [13] with modification for the case the nonnegative solution does not exist. Binner’s formula is equivalent to the one given by Tripathi [14]. In addition, the paper [15] gives the pretty much the same idea as that used in [13].
We may use Theorems1 and2 to find N6,9,20,n. To use formula (5), we rewrite equation (3) as(19)6x+9y=n−20z,and(20)2x+3y=13n−20z.
Since 3 is a factor of the left-hand side of equation (19), we have(21)n−20z≡0mod3,which implies(22)n≡20z≡−zmod3.
Thus, we need to consider three cases forn≡0,1,and2mod3, respectively, namely,(23)z≡0mod3,(24)z≡1mod3,(25)z≡2mod3,respectively.
In the case of equation (23), by noticing n−20z=6a+9b≥0 and z=3k for k≥0, we have(26)0≤3k≤n20.
Thus, forn≡0mod3, from Theorem 1, the number of the solutions of equation (19) is(27)N6,9,20,n=∑k=0n/60p2,3n3−20k,n≡0mod3.
In the case of equation (24), because n≡1mod3, z≡2mod3. By setting z=3k+2, we have the number of the solutions of(28)2x+3y=13n−20z=13n−203k+2,which is(29)N6,9,20,n=∑k=0n−40/60p2,3n−403−20k,n≡1mod3.
Finally, in the case of equation (25), because n≡2mod3, z≡1mod3. By setting z=3k+1, we obtain the number of the solutions of(30)2a+3b=13n−20z=13n−203k+1,which is(31)N6,9,20,n=∑k=0n−20/60p2,3n−203−20k,n≡2mod3.
We now use formula (9) to count the solutions of problem equation (3). Since u=gcdp,q=gcd6,9=3, to have u|n−20z for n≡0,1,and2mod3 or n=3r,3r+1,and3r+2r∈ℕ, we need z≡0,2,and1mod3 or z=3k,3k+2,and3k+1k∈ℕ∪0, respectively. Thus,(32)Mz=354n−20z−6a1z−9b1z=118n−20z−6a1z−9b1z.
Forn=3r and z=3k, we have a13k and b13k satisfying(33)6a13k≡3r−60kmod3,9b13k≡3r−60kmod2.
Forn=3r+1 and z=3k+2, we have a13k+2 and b13k+2 satisfying(34)6a13k+2≡3r−60k−39≡0mod3,9b13k+2≡3r−60k−39mod2.
Forn=3r+2 and z=3k+1, we have a13k+1 and b13k+1 satisfying(35)6a13k+1≡3r−60k−18≡0mod3,9b13k+1≡3r−60k−18mod2.
Hence, the number of solutions of equation (3) is(36)N6,9,20,n=∑0≤z≤n/ℓ3|n−20zp2,3n−20z3=∑0≤z≤n/ℓ3|n−20z1+Mz=∑0≤z≤n/ℓ3|n−20z1+118n−20z−6a1z−9b1z,where a1z and b1z satisfy equations (33)–(35).
The nonnegative solutions of problem equation (3) are(37)3iz+a1z,2Mz−iz+b1z,z:0≤iz≤Mz,for all 0≤z≤n/20 with 3|n−20z, where Mz is given in equation (32). More specifically, for n=3r, 3r+1, and 3r+2, we have z=3k, 3k+2, and 3k+1, respectively, and the corresponding(38)M3k=1183r−60k−6a13k−9b13k,for 0≤k≤r/20,(39)M3k+2=1183r−60k−39−6a13k+2−9b13k+2,for 0≤k≤r−13/20, and(40)M3k+1=1183r−60k−39−6a13k+1−9b13k+1,for 0≤k≤r−6/20.
For instance, ifn=39, then M3k is given by equation (38), where a13k and b13k satisfying(41)2a13k≡13−20kmod3,3b13k≡13−20kmod2,for k=0. Thus, a13k=a10=2 and b13k=b10=1, and(42)M3k=M0=11839−6·2−9·1=1.
Consequently, the problem6x+9y+20z=39 has 1+M0=2 solutions, which are(43)∪0≤i≤M00≤k≤13/203i+2,2M3k−i+1,3k=2,3,0,5,1,0.
Ifn=46≡1mod3, then M3k+2 is given by equation (40), where a13k+2 and b13k+2 satisfying(44)2a13k+2≡2−20kmod3,3b13k+2≡2−20kmod2,for k=0. Thus, a13k+2=a12=1 and b13k+2=b12=0, and(45)M3k+2=M2=1186−6·1−9·0=0.
Consequently, the problem6x+9y+20z=46 has 1+M2=1 solution, which is(46)∪0≤i≤M20≤k≤2/203i+1,2M2−i+0,3k+2=1,0,2.
Ifn=50≡2mod3, then M3k+1 is given by equation (40), where a13k+1 and b13k+1 satisfying(47)2a13k+1≡10−20kmod3,3b13k+1≡10−20kmod2,for k=0. Thus, a13k+1=a11=2 and b13k+1=b11=0, and(48)M3k+1=M1=11830−6·2−9·0=1.
Consequently, the problem6x+9y+20z=50 has 1+M1=2 solutions, which are(49)∪0≤i≤M10≤k≤10/203i+2,2M1−i+0,3k+1=2,2,1,5,0,1.
To find all solutions of equation (2), we may use Theorem 2 to determine the number of solutions and use the following proposition to find each solution of equation (2).Proposition 1.
Letx,y=x0,y0 be a solution of px+qy=m. Then, all solutions of the equations are x0+qt,y0−pt for all t∈ℤ.Example 1.
Consider the equation(50)6x+9y+20z=84,and rewrite it as(51)2x+3y=1384−20z.
Since84≡03, we have the number of the solutions of the equation(52)N6,9,20,84=∑k=084/60p2,3843−20k=p2,328+p2,328−20.
Form the formula forpa,bn presented in the Introduction by noting a=2, b=3, and n=28, we have 28=4·6+4 with q=4 and r=4 satisfying 2·3−2−3=1<r<6=2·3. Thus, p2,328=q+1=5. While for a=2, b=3, and n=8, we have 8=1·6+2 with q=1 and r=2 satisfying 1<r<6. Thus, p2,38=q+1=2 and(53)N6,9,20,84=p2,328+p2,328−20=7.
The nonnegative solutions of2x+3y=28−20z=28 can be found from Proposition 1 and Euclidean algorithm as follows:(54)x=2,y=8,z=0;x=5,y=6,z=0;x=8,y=4,z=0;x=11,y=2,z=0;x=14,y=0,z=0.
The nonnegative solutions of2x+3y=28−20z=8 are(55)x=1,y=2,z=1,x=4,y=0,z=1.
For problems for which the Euclidean algorithm is inefficient, an alternate approach is presented below. Consider the equation to bepx+qy=m with the given triple p,q,m, for which m is divisible by d=gcdp,q, we are seeking integer solutions x,y.Step 1:
want a nonnegative integer solutionx0,y0 for(56)px′+qy′=m.Step 2:
use modular arithmetic on the equation in Step 1:(57)qy′≡mmodp.Step 3:
solve the above congruence using the smallest possible nonnegative valuey′. Substituting the value of y′ in the equation finds x′. If x′ and y′>0, then x0=x′ and y0=y′. Then, Step 4 can be skipped.Step 4:
ifx′<0, then use Bezout’s Lemma to obtain the first nonnegative solutionx0,y0 from x′,y′ with a positive integer n such that x0=x′+nq/d>0 and y0=y′−np/d>0, where d=gcdp,q. If no such n exists, then there are no nonnegative solutions to the problem. For example, 3x+4y=5 does not have any nonnegative solutions.
Illustration of the algorithm is as follows. Consider(58)3x+5z=14.
Note that the common divisor,d, of 3 and 5 is 1.Step 1: want nonnegative integer solution,x0,y0, for 3x0+5y0=14.Step 2:3x′+5y′≡14mod3 implies 2y′≡2mod3 and y′≡1mod3. Hence, y′=1 and x′=3.Step 3: sincex′=3>0 and y′=1>0, we have x0,y0=x′,y′=3,1.Remark 1.
We may also use the method presented in [13] to solve 2x+3y=28 for obtaining the set of all nonnegative solutions x,y. We set 2x≡28mod3 and 3y≡28≡0mod2 to obtain x≡2mod3 and y≡0mod2, respectively. Thus, a1=2, b1=0, and M=28−2·2−3·0/6=4. Consequently, the nonnegative solutions of 2x+3y=28 are 3i+2,24−i+0:0≤i≤4, which are exactly the same as what we have obtained.Remark 2.
From the theory of partition (cf. [16]), the generating function of the sequence Nn=Np,q,ℓ,nn≥0 is(59)∑n≥0Nntn=11−tp1−tq1−tℓ.
From Taylor’s expansion, we have(60)Nn=1n!dndtn11−tp1−tq1−tℓ|t=0.
For smaller coefficientsp,q, and ℓ, we may find Nn more efficiently. For instance, if p=1, q=2, and ℓ=3, then the solution number Nn can be found by using the partial fraction technique shown below. Let ω=e2πi/3=cos2π/3+isin2π/3. Then,(61)11−t1−t21−t3=11−t31+t1−ωt1−ω2t=161−t3+141−t2+17721−t+181+t+191−ωt+191−ω2t=∑n≥0n+3212−772+−1n8+29cos2nπ3tn=∑n≥0Nntn,for t<1. Since(62)−772+−1n8+29cos2nπ3≤3272<12,and Nn must be an integer, we obtain Nn=n+32/12, where αα≠1/2 is referred to as the closest integer to α. For instance, the solution number for x+2y+3z=14 is(63)N14=14+3212=24.


## 3. Order Reduction Algorithm and Exhaustive Method for Solving Equation (2)

To find all solutions of equation (2), we may use following Bézout’s Lemma (cf. Millman et al. (Theorem 9 in [17])).Lemma 1.
The linear Diophantine equationpx+qy=r has a solution if and only if r is divisible by d=p,q. Furthermore, if x0,y0 is any particular solution of this equation, then all other solutions are given by(64)x′=x0+qdky′=y0−pdk,where k is an arbitrary integer.Letp and q be integers with the greatest common divisor d. Then, from Bézout’s lemma, there exist integers x and y such that px+qy=d. More generally, the integers of the form px+qy are the multiples of d. Expressions x′ and y′ shown in equation (64) are clearly true.We are going to use Bézout’s lemma to solve a problem with two different features: (1) we are solving Diophantine equation (2) of order 3, and (2) we are seeking all nonnegative solutions.Our algorithm is based on an order reducing technique. More precisely, letp,q,ℓ, and n∈ℕ with p≤q≤ℓ, and let x,y,andz∈ℤ. A linear Diophantine equation ax+by+cz=d of three variables is reduced to the following three Diophantine equations of two variables after setting x,y,andz=0, respectively. Graphically, the positive solutions of ax+by+cz=d lie on the triangle ΔABC intersecting by the plane ax+by+cz=d and the first quadrant of the three-dimensional space ℝ3. Let AB (with z=0), BC (with x=0), and CA (with y=0) be the three boundaries of the triangle ΔABC. Then, along the boundaries, the equation ax+by+cz=d is reduced to three two-variable equations. This paper discusses the relationship among the solutions on the boundaries AB, BC, and CA and the solutions on the triangle ΔABA. This graphical description of our algorithm will be presented analytically and precisely below. More geometrical presentations of the ax+by+cz=d problem can be found in Arnol’d [18] and Ustinov [19] and their references. Suppose one of p,q, q,ℓ, and ℓ,p are divisors of n. Bézout’s Lemma 1 shows that at least one of the Diophantine equations(65)px+qy=n,qy+lz=n,px+lz=n,has solutions. For instance, if p,q|n, then one pair of nonnegative solutions x0,y0 of the first equation px+qy=n can be found easily by using an extended Euclidean algorithm easily. Particularly, if p,q=p (or q), then it is easier to obtain a pair of solutions as n/p,0 (or 0,n/q), and all pairs of solutions of the equation can be represented in the form(66)x0+kqp,q,y0−kpp,q,where k is an arbitrary integer. The set of all those solutions x,y,0 is denoted by S, i.e.,(67)S=x0+kqp,q,y0−kpp,q:k∈ℤ.We are seeking nonnegative solutions ofpx+qy=n, i.e., a particular solution pair x0,y0, where x0andy0≥0, and all solution pairs in equation (24) for k such that(68)k∈K=k∈ℤ:−x0p,qq≤k1≤y0p,qp,that is, x0+kq/p,q and y0−kp/p,q≥0.In the above algorithm, we must assume one of the conditions,p,q|n, q,ℓ|n, and p,ℓ|n, holds; otherwise, our algorithm fails because if gcdp,q does not divide n, then clearly px+qy=n has no solutions since gcdp,q divides the left-hand side but not the right-hand side.Consequently, ifp,q, and l are pairwise coprime numbers, then px+qy+lz=n can be solved by using our algorithm. As what we have defined before, the set of all solutions of the first equation in (65) is denoted by S1. Similarly, we let S2 and S3 denote the sets of the solutions of the second and the third equations of (65), respectively.It is obvious that, for any integersa,b, and c, with a+b+c≠0 and row vectors si∈Si, i=1,2, and 3, as1+bs2+cs3/a+b+c is also a solution of px+qy+ℓz=n because(69)as1+bs2+cs3a+b+c·p,q,ℓT=1a+b+can+bn+cn=n.Because a solution obtained by using our order reducing method has at least one zero component, we can see how important it is to use these linear combinations complete the set of all solutions of equation (2), say to calculate the solutions with nonzero components. We will also demonstrate how to build those linear combinations by using some examples.Proposition 2.
Let setsSi, i=1,2,and3, be defined before, and let a,b, and c be any nonintegers, with a+b+c≠0. We have notation(70)S^1=0,y2,0+k2lq,l,z2,0−k2qq,l:y2,0,z2,0≥0,k2∈K1,S^2=x3,0+k3lp,l,0,z3,0−k3pp,l:x3,0,z3,0≥0,k3∈K2,S^3=x1,0+k1qp,q,y1,0−k1pp,q,0:x1,0,y1,0≥0,k1∈K3,where y2,0,z2,0, x3,0,z3,0, and x1,0,y1,0 are solutions of qy+ℓz=n, px+ℓz=n, and px+qy=n, respectively, and(71)K1=k∈ℤ:−y2,0q,ll≤k≤z2,0q,lq,K2=k∈ℤ:−x3,0p,ll≤k≤z3,0p,lp,K3=k∈ℤ:−x1,0p,qq≤k≤y1,0p,qp.Then, all nonnegative elementsx,y,z in the set(72)as1+bs2+cs3a+b+c:a+b+c≠0,si∈S^i,i=1,2,3,are a solution of equation (2).The proof is obvious from the above discussion and is, therefore, omitted.To avoid using linear combinations, we may use the following exhaustive method. We assumep≤q≤ℓ, and let(73)Szi=x,y,i:px+qy=n−zi,zi=iℓwith0≤zi≤n.Then, the solution set of equation (2) is ∪i=0n/lSzi.Example 2.
Consider the equation(74)6x+9y+20z=84,and reduce it to three Diophantine equations of order 2:(75)9y+20z=84,(76)6x+20z=84,(77)6x+9y=84,for the cases of z=0, x=0, and y=0 in equation (74).
Equation (77) can be written as 2x+3y=28. Hence, y=0 yields a particular solution of equation (77) as x=14 and y=0. The solution set S^3 is(78)S^3=14+k196,9,0−k166,9,0:−143≤k1≤0=14,0,0,11,2,0,8,4,0,5,6,0,2,8,0.
Similarly, from equation (75), we have(79)y=84−20z9,which shows equation (75) has no nonnegative integer solutions y,z. Hence, the solution set of equation (75) is(80)S^1=ϕ.
Finally, from equation (76), we have(81)x=42−10z3=12−3z+6−z3.
To have nonnegative solutions of equation (76), we must have z=0 or z=3, which implies(82)S^2=14,0,0,4,0,3.
Hence, we have found 6 distinct solutions of equation (74). The 7th solution is from a linear combination of the elements 8,4,0, 11,2,0, and 4,0,3 of the solution set ∪i=13S^i with the coefficients a=1, b=−1, and c=1:(83)aa+b+c8,4,0+ba+b+c11,2,0+ca+b+c4,0,3=8,4,0−11,2,0+4,0,3=1,2,3.
Hence, the solutions of6x+9y+20ℓ=84 are(84)S=14,0,0,11,2,0,8,4,0,5,6,0,2,8,0,4,0,3,1,2,3.
If we use the exhaustive method to check our results, then we obtain(85)S0=14,0,0,11,2,0,8,4,0,5,6,0,2,8,0,S20=x,y,1:6x+9y=84−20=64=ϕ,S40=x,y,2:6x+9y=84−40=44=ϕ,S60=x,y,3:6x+9y=84−60=24=4,0,3,1,2,3.
Hence, the solutions of6x+9y+20ℓ=84 are as the same as equation (84).
However, sometimes, we have many solutions ofpx+qy+rz=n that are not from the union ∪i=13S^i. Therefore, we need calculate the number of the solutions and develop an efficient way (see below) to find the solutions in the form of as1+bs2+cs3/a+b+c, where a,b,andc∈ℤ and si∈S^i, i=1,2,and3. For instance, we may consider p,q,l=1,2,3, and the corresponding solution sets of x+2y+3z=14 by using our algorithm are S1=0,7+3k3,−2k3:k3∈ℤ, S2=14+3k2,0,−k2:k2∈ℤ, and S3=2k1,7−k1,0:k1∈ℤ, respectively. Hence,(86)S^1=0,7,0,0,4,2,0,1,4,(87)S^2=14,0,0,11,0,1,8,0,2,5,0,3,2,0,4,(88)S^3=0,7,0,2,6,0,4,5,0,6,4,0,8,3,0,10,2,0,12,1,0,14,0,0.
However, by using Theorem1, we may find that the number of the solutions of x+2y+3z=14 is(89)∑k=014/3p1,214−3k=p1,214+p1,211+p1,28+p1,25+p1,22=8+6+5+3+2=24,where p1,2n, n=14,11,8,5, and 2, are found by using Theorem 1.Remark 3.
For smallp and q, the number of the solutions, denoted by pp,qn, of the Diophantine equation px+qy=n can be also found by using the theory of partition, which is similar to the process of deriving equations (5) and (6). More precisely, from the theory of partition (cf. [16]), the generating function of the sequence Pn=pp,qnn≥0 is(90)∑n≥0Pntn=11−tp1−tq.
From Taylor’s expansion, we have(91)Pn=1n!dndtn11−tp1−tq|t=0.
LetNn and Pn be defined by equations (59), (60), (90), and (91), respectively. Then,(92)Nn=∑k=0n/ℓPn−ℓk.
Consequently, by using a straightforward exhaustive method for solving Diophantine equation (2), we have(93)dndtn11−tp1−tq1−tℓ=n!∑k=0n/ℓ1n−ℓk!dn−ℓkdtn−ℓk11−tp1−tq.
For smaller coefficientsp,q, and ℓ, we may find Pn more efficiently. For instance, if p=1 and q=2, then the solution number Pn can be found by using the partial fraction technique shown below. Since(94)11−t1−t2=1411+t+11−t+21−t2,t<1,the expansion of the power series can be written as(95)∑n≥0Pntn=∑n≥0−1n+1+2n+14tn.
Consequently,(96)Pn=142n+3+−1n,which gives p1,214=P14=8, p1,211=P11=6, p1,28=P8=5, p1,25=P5=3, and p1,22=P2=2.
Since(97)∪i=13S^i=0,7,0,2,6,0,4,5,0,6,4,0,8,3,0,10,2,0,12,1,0,14,0,0,11,0,1,8,0,2,5,0,3,2,0,4,0,4,2,0.1.4,we need to find 10 more solutions by using the linear combination as1+bs2+cs3/a+b+c, where si∈Si, i=1,2,3, and a+b+c≠0.
The algorithm to establish those linear combinations is to find setsa,b,c:a+b+c=1, say 1,1,−1,1,3,−2,…, etc. Denote si=xi,yi,zii=1,2,3. Then, we test all obtained solutions to find those distinct linear combinations (remember, a+b+c=1):(98)as1+bs2+cs3=ax1+bx2+cx3,ay1+by2+cy3,az1+bz2+cz3,such that ax1+bx2+cx3,ay1+by2+cy3,andaz1+bz2+cz3>0 because any solution of the form as1+bs2+cs3 with one zero component has been obtained already.
As the simplest linear combination, we choosea,b,c=1,−1,1 and calculate(99)s1−s2+s3=x1−x2+x3,y1−y2+y3,z1−z2+z3,such that x1−x2+x3,y1−y2+y3,andz1−z2+z3>0.
We now present the following conjecture for further discussion of finding all of nonnegative solutions of Diophantine equation (2).


### 3.1. Conjecture

For any solutionx^,y^,z^ of px+qy+lz=n with gcdp,q,l=1, there exist solutions si, i=1,2,3, of either qy+lz=n, px+lz=n, or px+qy=n such that(100)x^,y^,z^=s1−s2+s3,where si∈S^i, i=1,2,3, in the last expression do not need to be different. Hence, if all three si, i=1,2,3, are the same, equation (100) presents itself.We will illustrate that the conjecture is reasonable by using some examples. Meanwhile, we will give an algorithm to apply equation (100) to construct all of the solutions of the Diophantine equations in the examples.We say the setS^j is the smallest set of the collection S^i:i=1,2,3, if the cardinal number S^j=minS^1,S^2,S^3. We say the set S^k is the next smallest set of the collection S^i:i=1,2,3, if the cardinal number S^k=minS^1,S^2,S^3/S^j. We say xi,yi,zi is the smallest element of a set S^j=xj,yj,zj:j=1,2,…,, if xi+yi+zi is the smallest possible number in the set Sj. Assume p<q<ℓ in equation (2). Then, in general, S^1 is the smallest set and S^2 is the next smallest set. One can also check that this is the case, in expressions (86), (87), and (88). Our algorithm can be described based on Proposition 2 as follows:Step 1. Determine the smallest element of the smallest setStep 2. Use the smallest element s11,s12,s13 determined in the first step to subtract all of the elements in the next smallest set, S^2, provided that the differences of the third components are positiveStep 3. Add the resulting elements obtained in the second step to all of the elements in S^3, provided the resulting sums for all components are positiveStep 4. The union of the sets S^i, i=1,2,3, and those obtained in the third step consist of the whole solution set of equation (2)As an example, we now use this algorithm to find the remaining part of the solution set ofx+2y+3z=14, besides those 14 solutions shown in equation (97). Based on our definition, 0,1,4 is the smallest element of the smallest set S^3 in equation (86). We use 0,1,4 to subtract all of those elements in the next smallest set, S^2, in equation (87), such that the third components are positive, namely,(101)0,1,4−5,0,3=−5,1,1,0,1,4−8,0,2=−8,1,2,0,1,4−11,0,1=−11,1,3,0,1,4−14,0,0=−14,1,4.Following the algorithm, we add−5,1,1 to 6,4,0,8,3,0,10,2,0, 12,1,0, and 14,0,0 in equation (88) to obtain the following 5 solutions of x+2y+3z=14:(102)1,5,1,3,4,1,5,3,1,7,2,1,9,1,1.By adding−8,1,2 to 10,2,0,12,1,0, and 14,0,0 in equation (88), we obtain the following 3 solutions of x+2y+3z=14:(103)2,3,2,4,2,2,6,1,2.Adding−11,1,3 to 12,1,0 and 14,0,0 in equation (88), we get the 2 more solutions of x+2y+3z=14 as(104)1,2,3,3,1,3.Adding−14,1,4 to any element in equation (88), we cannot get an element with positive components, so we cannot get any more solutions. Thus, we obtain all 24 solutions of x+2y+3z=14 by combining the above 10 solutions and the 14 solutions shown in equation (97).We use the exhaustive method to check our results and find(105)S0=x,y,0:x+2y=14=0,7,0,2,6,0,4,5,0,6,4,0,8,3,0,10,2,0,12,1,0,14,0,0,S3=x,y,1:x+2y=14−3=11=11,0,1,9,1,1,7,2,1,5,3,1,3,4,1,1,5,1S6=x,y,2:x+2y=14−6=8=8,0,2,6,1,2,4,2,2,2,3,2,0,4,2S9=x,y,3:x+2y=14−9=5=5,0,3,3,1,3,1,2,3S12=x,y,4:x+2y=14−12=2=2,0,4,0,1,4,where(106)S0=8=p1,214,S3=6=p1,211,S6=5=p1,28,S9=3=p1,25,S12=2=p1,22.Our algorithm is efficient for solving many Diophantine equations. However, the algorithm may not work for some Diophantine equation (2) although we think the expression in equation (100) can still be applied to find all of the solutions of equation (2), with some modification of the above algorithm. Here is an example. Consider the Diophantine equation:(107)5x+7y+11z=71.For reducing equation5x+7y=71, from 5a1≡71≡1mod7 and 7b1≡71≡1mod5, we obtain a1=3 and b1=3. Thus,(108)M=13571−7·3−5·3=1,which implies 5x+7y=71 has 1+M=2 nonnegative solutions S^3=7i+3,5M−i+3,0:i=0,1=3,8,0,10,3,0. Similarly, for equation 7y+11z=71, the corresponding a1=7, b1=2, and(109)M=17771−7·7−11·2=0,which implies 7y+11z=71 has 1+M=1 nonnegative solution S^1=0,11i+7,7M−i+2:i=0=0,7,2. For equation 5x+11z=71, the corresponding a1=1, b1=1, and(110)M=15571−5·1−11·1=1,which implies 5x+11z=71 has 1+M=2 solutions S^2=11i+1,0,5M−i+1=1,0,6,12,0,1. Denote(111)S^=∪i=13S^i=0,7,2,1,0,6,12,0,1,3,8,0,10,3,0.Then, we pick up some three different elements from the five elements of the setS^ to find other solutions of equation (107) by using equation (100). For instance,(112)1,0,6−0,7,2+3,8,0=4,1,4,10,3,0−3,8,0+0,7,2=7,2,2,12,0,1−10,3,0+0,7,2=2,4,3,12,0,1−10,3,0+3,8,0=5,5,1.By using Theorem2, we may find equations 5x+7y=71−11z have 2, 2, 2, 1, 1, 0, and 1 nonnegative solutions for z=0,1,2,3,4,5, and 6, respectively. Hence, 5x+7y+11z=71 has 9 nonnegative solutions, and all of them can be presented by using equation (100). It worth mentioning that, for z=5, 5x+7y=71−11·5=16 has no nonnegative solution from Theorem 2 since M5=16−5a15−7b15/35=16−5·6−7·3/35<0.Here, we have two comments. First, some three elements may not give a nonnegative solution of equation (107) by using equation (100), say 12,0,1−0,7,2+3,8,0=13,1,−1. Secondly, it is clear that each element in S^ can also be presented by using equation (100). Hence, we have the following consequence of the conjecture.


### 3.2. Consequence of the Conjecture

DenoteS^i=Ni and N^=N1+N2+N3. Then, the number of solutions of equation (2) has bounds:(113)0≤Np,q,ℓ,n≤3N^3,which is implied by the conjecture if it is true.


## 3.1. Conjecture

For any solutionx^,y^,z^ of px+qy+lz=n with gcdp,q,l=1, there exist solutions si, i=1,2,3, of either qy+lz=n, px+lz=n, or px+qy=n such that(100)x^,y^,z^=s1−s2+s3,where si∈S^i, i=1,2,3, in the last expression do not need to be different. Hence, if all three si, i=1,2,3, are the same, equation (100) presents itself.We will illustrate that the conjecture is reasonable by using some examples. Meanwhile, we will give an algorithm to apply equation (100) to construct all of the solutions of the Diophantine equations in the examples.We say the setS^j is the smallest set of the collection S^i:i=1,2,3, if the cardinal number S^j=minS^1,S^2,S^3. We say the set S^k is the next smallest set of the collection S^i:i=1,2,3, if the cardinal number S^k=minS^1,S^2,S^3/S^j. We say xi,yi,zi is the smallest element of a set S^j=xj,yj,zj:j=1,2,…,, if xi+yi+zi is the smallest possible number in the set Sj. Assume p<q<ℓ in equation (2). Then, in general, S^1 is the smallest set and S^2 is the next smallest set. One can also check that this is the case, in expressions (86), (87), and (88). Our algorithm can be described based on Proposition 2 as follows:Step 1. Determine the smallest element of the smallest setStep 2. Use the smallest element s11,s12,s13 determined in the first step to subtract all of the elements in the next smallest set, S^2, provided that the differences of the third components are positiveStep 3. Add the resulting elements obtained in the second step to all of the elements in S^3, provided the resulting sums for all components are positiveStep 4. The union of the sets S^i, i=1,2,3, and those obtained in the third step consist of the whole solution set of equation (2)As an example, we now use this algorithm to find the remaining part of the solution set ofx+2y+3z=14, besides those 14 solutions shown in equation (97). Based on our definition, 0,1,4 is the smallest element of the smallest set S^3 in equation (86). We use 0,1,4 to subtract all of those elements in the next smallest set, S^2, in equation (87), such that the third components are positive, namely,(101)0,1,4−5,0,3=−5,1,1,0,1,4−8,0,2=−8,1,2,0,1,4−11,0,1=−11,1,3,0,1,4−14,0,0=−14,1,4.Following the algorithm, we add−5,1,1 to 6,4,0,8,3,0,10,2,0, 12,1,0, and 14,0,0 in equation (88) to obtain the following 5 solutions of x+2y+3z=14:(102)1,5,1,3,4,1,5,3,1,7,2,1,9,1,1.By adding−8,1,2 to 10,2,0,12,1,0, and 14,0,0 in equation (88), we obtain the following 3 solutions of x+2y+3z=14:(103)2,3,2,4,2,2,6,1,2.Adding−11,1,3 to 12,1,0 and 14,0,0 in equation (88), we get the 2 more solutions of x+2y+3z=14 as(104)1,2,3,3,1,3.Adding−14,1,4 to any element in equation (88), we cannot get an element with positive components, so we cannot get any more solutions. Thus, we obtain all 24 solutions of x+2y+3z=14 by combining the above 10 solutions and the 14 solutions shown in equation (97).We use the exhaustive method to check our results and find(105)S0=x,y,0:x+2y=14=0,7,0,2,6,0,4,5,0,6,4,0,8,3,0,10,2,0,12,1,0,14,0,0,S3=x,y,1:x+2y=14−3=11=11,0,1,9,1,1,7,2,1,5,3,1,3,4,1,1,5,1S6=x,y,2:x+2y=14−6=8=8,0,2,6,1,2,4,2,2,2,3,2,0,4,2S9=x,y,3:x+2y=14−9=5=5,0,3,3,1,3,1,2,3S12=x,y,4:x+2y=14−12=2=2,0,4,0,1,4,where(106)S0=8=p1,214,S3=6=p1,211,S6=5=p1,28,S9=3=p1,25,S12=2=p1,22.Our algorithm is efficient for solving many Diophantine equations. However, the algorithm may not work for some Diophantine equation (2) although we think the expression in equation (100) can still be applied to find all of the solutions of equation (2), with some modification of the above algorithm. Here is an example. Consider the Diophantine equation:(107)5x+7y+11z=71.For reducing equation5x+7y=71, from 5a1≡71≡1mod7 and 7b1≡71≡1mod5, we obtain a1=3 and b1=3. Thus,(108)M=13571−7·3−5·3=1,which implies 5x+7y=71 has 1+M=2 nonnegative solutions S^3=7i+3,5M−i+3,0:i=0,1=3,8,0,10,3,0. Similarly, for equation 7y+11z=71, the corresponding a1=7, b1=2, and(109)M=17771−7·7−11·2=0,which implies 7y+11z=71 has 1+M=1 nonnegative solution S^1=0,11i+7,7M−i+2:i=0=0,7,2. For equation 5x+11z=71, the corresponding a1=1, b1=1, and(110)M=15571−5·1−11·1=1,which implies 5x+11z=71 has 1+M=2 solutions S^2=11i+1,0,5M−i+1=1,0,6,12,0,1. Denote(111)S^=∪i=13S^i=0,7,2,1,0,6,12,0,1,3,8,0,10,3,0.Then, we pick up some three different elements from the five elements of the setS^ to find other solutions of equation (107) by using equation (100). For instance,(112)1,0,6−0,7,2+3,8,0=4,1,4,10,3,0−3,8,0+0,7,2=7,2,2,12,0,1−10,3,0+0,7,2=2,4,3,12,0,1−10,3,0+3,8,0=5,5,1.By using Theorem2, we may find equations 5x+7y=71−11z have 2, 2, 2, 1, 1, 0, and 1 nonnegative solutions for z=0,1,2,3,4,5, and 6, respectively. Hence, 5x+7y+11z=71 has 9 nonnegative solutions, and all of them can be presented by using equation (100). It worth mentioning that, for z=5, 5x+7y=71−11·5=16 has no nonnegative solution from Theorem 2 since M5=16−5a15−7b15/35=16−5·6−7·3/35<0.Here, we have two comments. First, some three elements may not give a nonnegative solution of equation (107) by using equation (100), say 12,0,1−0,7,2+3,8,0=13,1,−1. Secondly, it is clear that each element in S^ can also be presented by using equation (100). Hence, we have the following consequence of the conjecture.


## 3.2. Consequence of the Conjecture

DenoteS^i=Ni and N^=N1+N2+N3. Then, the number of solutions of equation (2) has bounds:(113)0≤Np,q,ℓ,n≤3N^3,which is implied by the conjecture if it is true.



---

*Source: 6396792-2021-09-11.xml*