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.


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

  • 1
    $\begingroup$ 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$. $\endgroup$ – coffeemath Aug 18 '13 at 9:51

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.