Check whether positive integral solution $(x,y)$ exists for $ax + by = n$

Question

Is there any method to check whether there exist positive integral solutions $(x,y)$ for the equation

$$ax + by = n $$ given $$a,b,n \in \mathbb{Z}^+$$

Also, please note $a$ and $b$ were given, and the following relations exist:

1. $a > b$
2. $a + b \le n$

Answer 1

Note that $\mathbb Z^+ = \{1,2,3,\dots\}.$

The Chicken McNugget Theorem (or Postage Stamp Problem or Frobenius Coin Problem) states that for any two relatively prime positive integers $a,b$, the greatest integer that cannot be written in the form $ax+by$ for nonnegative integers $x,y$ is $(a-1)(b-1)-1 = ab-a-b.$

A corollary of the proof states that every integer $c \ge (a-1)(b-1)$ can be written in the form $ax+by=c$, where $x,y \in \mathbb Z^+$, in exactly one way. So you may want to also exclude multiples of $a$ and multiples of $b$ since they require that either $x$ or $y$ be equal to $0$.

Answer 2

Here is an outline of an answer based on Section 5.1, "The Equation $ax + by = c$," of I. Niven, H. S. Zuckerman, H. L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley (New York), 1991. You can prove the statements with the help of this theorem.

There is a positive solution if and only if

• $n$ is a multiple of gcd($a ,b$) = $g$, and
• $n > ab/g$.

To understand that second requirement, let $(x_0, y_0)$ be one solution. Then the solutions are of the form $$\left(x_0 + \frac{kb}{g}, y_0 - \frac{ka}{g}\right)$$ where $k$ is an integer, so you want to find $k$ such that $$x_0 + \frac{kb}{g} > 0, \text{ and } y_0 - \frac{ka}{g} > 0,$$ which is equivalent to $$\frac{-gx_0}{b} < k < \frac{gy_0}{a}.$$ Because $(x_0, y_0)$ satisfies $ax + by = n$, the length of that open interval for $k$ is $gn/(ab)$. A gap for you to fill in is to prove why that length must be greater than $1$ for there to be a positive solution.