# Linear equation with prime coefficient.

Suppose we have a linear equation with two variables say $x$ and $y$ and three integer coefficient $a , b$ and $c$ (constant), where $a$ and $b$ are prime all are greater than zero.

$ax+by=c$

how can we find out maximum value of $c$ , above that value of $c$ in our equation always has a positive integer solution for both $x$ and $y$.

• I think you mean to find the minimum value of $c$ such that above that $c$ there is a solution. There isn't a maximum such $c$ clearly, since if $c$ works so does $c+1$. – coffeemath Aug 18 '13 at 9:51

## 1 Answer

Even if positive integers $a,b$ are not necessarily primes, but assuming $\gcd(a,b)=1$, there is a result known by various names such as "coins problem" or "postage stamp problem" which says that, if $u,v$ are restricted to be nonnegative integers, then the greatest integer not of the form $au+bv$ is $ab-a-b$. If now you require $x,y>0$ in the expression $ax+by$, note that you can put $x=u+1,y=v+1$ where now the restrictions on $u,v$ are that they be nonnegative, and you have $ax+by=(a+b)+[au+bv]$, which makes it clear that the greatest integer not of the form $ax+by$ with positive $x,y$ is $$(a+b)+[ab-a-b]=ab.$$ So any integer greater than or equal to $c=ab+1$ has an expression as $ax+by$ with positive $x,y$, and this is the smallest possible such $c$, since it can be shown that $c-1$ has no such representation.