# Yet another question on the number of solutions of a Diophantine equation of Frobenius

In the simplest case, let $$a,b \in \mathbb{N}$$, with $$\gcd(a,b)=1$$. I want to find the smallest $$k \in \mathbb{N}$$ such that the Diophantine equation $$ax + by = k$$ has at least two distinct solutions, where $$x,y$$ are nonnegative integers.

Obviously, $$k \leq ab$$, since $$k=ab$$ has at least two solutions. However, I don't see any simple formula for the smallest such $$k$$.

More generally we have $$a_1, a_2, \ldots, a_n \in \mathbb{N}$$, where $$\gcd(a_1, \ldots, a_n)=1$$, and I want to find the smallest $$k \in \mathbb{N}$$ such that the linear Diophantine equation $$a_1 x_1 + \cdots a_n x_n = k$$ has at least two distinct solutions in the nonnegative integers.

Is there any formula (or bounds) for $$k$$?

• There's no nice formula for the simpler problem of finding the largest positive integer $k$ such that $ax+by+cz=k$ has no solution in nonnegative integers $x,y,z$, so I wouldn't expect a formula for your question. Jul 16 at 6:31

Have $$k$$ be a positive integer such that $$(x_1,y_1)$$ and $$(x_2,y_2)$$ are two distinct solutions in non-negative integers, so

$$ax_1+by_1=k=ax_2+by_2 \;\;\to\;\; a(x_1-x_2)=b(y_2-y_1) \tag{1}\label{eq1A}$$

Since $$\gcd(a,b)=1$$, then

$$a \mid y_2-y_1 \;\;\to\;\; y_2 - y_1 = ma, \;\; m\in\mathbb{Z}, \;\; m \neq 0 \tag{2}\label{eq2A}$$

If $$m \gt 0$$, then since $$y_1 \ge 0$$, we have $$y_2 \ge ma \;\;\to\;\; y_2 \ge a$$. Using this in \eqref{eq1A}, since $$x_2 \ge 0$$, gives that

$$k = ax_2 + by_2 \ge ab \tag{3}\label{eq3A}$$

Similarly, if $$m \lt 0$$, we get from \eqref{eq2A} that $$y_1 - y_2 = -ma$$ so $$y_1 \ge a$$, i.e., the indices are just switched around. Thus, in either case, we get from \eqref{eq3A} that $$k \ge ab$$. However, as you already stated, $$k \le ab$$ (since $$(0,a)$$ and $$(b,0)$$ are $$2$$ solutions for $$k = ab$$), this means

$$k = ab \tag{4}\label{eq4A}$$

is the smallest such $$k$$.

For your more general case where $$n \ge 3$$, I don't offhand know of any simple solution. Nonetheless, to get a generally quite reasonable bound, from among $$1 \le i \lt j \le n$$, choose the index values giving the minimum value of $$\operatorname{lcm}(a_{i},a_{j}) = \frac{a_{i}a_{j}}{\gcd(a_i,a_j)}$$. Then have

$$d = \gcd(a_i,a_j), \;\; a_i = dc_i, \;\; a_j=dc_j, \;\; \gcd(c_i,c_j)=1 \tag{5}\label{eq5A}$$

With $$x_m = 0$$ for all $$m \neq i,j$$, then $$k = dc_ic_j$$ (i.e., $$\operatorname{lcm}(a_{i},a_{j})$$) has $$2$$ solutions with $$(x_i,x_j)$$ being $$(0,c_i)$$ and $$(c_j,0)$$.

• Thank you very much. Very helpful. Let's wait a little bit, in case someone knows something about the general case. Jul 7 at 9:11