Check whether positive integral solution $(x,y)$ exists for $ax + by = n$ 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:


*

*$a > b$ 

*$a + b \le n$

 A: 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$.
A: 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.
