How can we express a number $n$ as $pa+qb$ where $p \geq0$ and $q \geq 0$ and $p$ and $q$ can't be fraction. In contest I got a puzzle as if we can express $c$ as sum of $a$ and $b$ in form $pa+qb$. Suppose $a$ is $3$ and $b$ is $4$ and $c$ is $7$ so we can express $7$ as $3+4$. Suppose $a$ is $4$ and $b$ is $6$ and $c$ is $15$ but we can't express $15$ as sum of $4 \cdot p+6 \cdot q$.


I came up with an approach to take $\gcd$ of $a$ and $b$ and check if their $\gcd$ leaves zero as remainder when $\gcd$ divides $c$. Is there any general method to check this ?

  • $\begingroup$ What about $a$ and $b$, can they be fractions? Can they be irrational numbers? e.g., $7 = \sqrt{2} \sqrt{2} + \sqrt{5} \sqrt{5}$ $\endgroup$ – James47 Feb 26 '16 at 22:39
  • $\begingroup$ If you require $p,q\ge 0$, then you will not get all multiples of their g.c.d. For example $\gcd(2,3)=1$, but you cannot get $1=2p+3q$ with $p$ and $q$ being non-negative integers. $\endgroup$ – Martin Sleziak Feb 29 '16 at 17:24
  • $\begingroup$ This seems related: math.stackexchange.com/questions/21007/… A comment there links to Wikipedia article about Frobenius number and Coin problem. $\endgroup$ – Martin Sleziak Feb 29 '16 at 17:28
  • $\begingroup$ The minimum value you can get is $0$ witha choice of $p=0$ and $q=0$. $\endgroup$ – TheRandomGuy Mar 18 '16 at 16:47

If $a,b$ are fixed natural numbers, then the set of all integers $n$ which can be written in the form $n=pa+qb$ for integers $p$ and $q$ is precisely the set of multiples of the greatest common divisor of $a$ and $b$. So $n$ can be written in the desired form if and only if $n$ is divisible by $\gcd(a,b)$.

  • $\begingroup$ Yes, that's how GCD is defined, or at least that's its most basic property. The GCD is the min positive member of this set. $\endgroup$ – peter.petrov Feb 26 '16 at 20:45
  • $\begingroup$ I would consider the definition of the gcd to be the common divisor of $a$ and $b$ which is divisible by every other common divisor, but of course the two definitions are equivalent. $\endgroup$ – carmichael561 Feb 26 '16 at 20:52
  • $\begingroup$ @carmichael561 Notice that the OP has and additional condition that $p,q\ge0$. (Admittedly, the question is not entirely clear.) $\endgroup$ – Martin Sleziak Feb 29 '16 at 17:21
  • $\begingroup$ Good point. That makes things more annoying. $\endgroup$ – carmichael561 Feb 29 '16 at 19:04

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.