Conjecture about linear diophantine equations

Question

I've been dabbling with linear Diophantine equations and came across a rather interesting pattern that I would like to conjecture as true but I have no idea how about to come up with a proof.

Let $ax+by=c$ be the linear Diophantine equation such that $gcd(a,b)=1$. Obviously $1|c$ so there are solutions to the equation. If we consider only positive solution pairs (x,y) for the equation, then the number of ordered pairs that satisfy the equation is equal to (c/a)/b, rounded down to the nearest integer.

Can anyone verify this by counterexample or by proof? Thanks

Answer 1

The specific proposed solution is false, as can be seen by a counterexample like $c=5$, $a=2$, $b=3$. More generally the number of solutions, while rather well-behaved, does not increase monotonically, also not for larger $c$; there is some (minor) fluctuation.

The number of solutions of a linear Diophantine equation $$a_1x_1 + \dots +a_m x_m = n$$ in non-negative integers is referred to as denumerant (sometimes also Sylvester's Denumerant). Whether one asks for positive or non-negative solutions does not change much as one can just adjust the $n$.

The quantity is a quasi-polynomial of degree $m-1$, so in the present case linear. Quasi-polynomial mean roughly that there is a modulus such that on the respective residue classes it is an actual polynomial. The modulus is the LCM of the coefficients so in this case $ab$.

With the term "denumerant", which I learned from Gerry Myerson on a site close by some time ago, at hand plenty of further information is readily accessible, so I stop here.

The question Count the number of positive solutions for a linear diophantine equation (already provided in comments by A.P.) also provides relevant information, in particular the key-word Ehrhart Polynomials and Ehrhart Quasi-Polynomials.

Answer 2

If $a$ and $b$ have different signs, then the Diophantine equation $ax + by = c$ may have infinitely many solutions with $x,y > 0$. For example, consider $$ 3 x - 2 y = 1 $$ which has a solution for every $y \equiv 1 \pmod{3}$. Thus in what follows we shall consider only equations with $a,b,c > 0$.

From this answer know that the number of non-negative solutions, i.e. of solutions with $x,y \geq 0$, is $$ P_2(a,b,c) = \sum_{x\in [0, c/a]\cap \mathbb{N}} P_1(b, c-xa) $$ where $P_1(\alpha,\gamma)$ is $1$ if $\alpha$ divides $\gamma$ and $0$ otherwise. Now, since $a$ and $b$ are coprime we know that $a$ is invertible modulo $b$, which means that $P_2(a,b,c)$ is the same as the number of integers $x$ in $[0,c/a]$ such that $$ ca^{-1} \equiv x \pmod{b} $$ of which there are at most $$ \left\lfloor \left(\frac{c}{a}\right) \frac{1}{b} \right\rfloor + 1 = \left\lfloor \frac{c}{ab} \right\rfloor + 1 $$ Finally, note that this bound is tight, because it is attained whenever $c$ is a multiple of $ab$. On the other hand, $P_2(a,b,c) = 0$ for infinitely many triples $(a,b,c)$, for example whenever $c < a$ and $b \nmid c$.

Note: There is no real difference between counting solutions with $x,y > 0$ or with $x,y \geq 0$ (see quid's comment below).

Answer 3

In this answer, it is shown that

Theorem $\boldsymbol{1}$: Suppose $\operatorname{gcd}(a,b)=1$ and $c \ge (a-1)(b-1)$. Then $ax+by=c$ has a non-negative solution, that is, one in which both $x$ and $y$ are non-negative integers.

and

Theorem $\boldsymbol{2}$: Suppose $\operatorname{gcd}(a,b)=1$, $0 \lt c \lt ab$, and neither $a\mid c$ nor $b\mid c$. Then one and only one of $$ ax+by=c $$ and $$ ax+by=ab-c $$ has a non-negative solution.

Theorem $2$ shows that there are solutions even if $c\lt ab$; that is, $\left\lfloor\frac{c}{ab}\right\rfloor=0$. In fact, half of the integers between $0$ and $ab$ that are not multiples of $a$ or $b$ will have positive solutions.

Note that if $$ ax+by=c\tag{1} $$ has $k$ positive solutions, $\{(x-jb,y+ja):0\le j\lt k\}$, then $$ ax+by=c+ab\tag{2} $$ has $k+1$ positive solutions, $\{(x-jb+b,y+ja):0\le j\lt k+1\}$

Even if $(1)$ has no solutions, Theorem $1$ guarantees that $(2)$ has one solution (and only one; if it had two, we could reverse the argument to show that $(1)$ has a solution).

Therefore, if $0\lt c\lt ab$, then $$ ax+by=c+kab\tag{3} $$ has $k$ positive solutions if $(1)$ has no positive solutions and has $k+1$ positive solutions if $(1)$ has a positive solution.

Thus, $(1)$ has either $\left\lfloor\frac{c}{ab}\right\rfloor$ positive solutions or $\left\lfloor\frac{c}{ab}\right\rfloor+1$ positive solutions.