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$?

  • $\begingroup$ 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. $\endgroup$ Jul 16 at 6:31

1 Answer 1


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)$.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .