# a number n as pa+qb

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

NOTE: $p$ AND $q$ CAN'T BE FRACTIONS.

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 ?

• 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}$ – James47 Feb 26 '16 at 22:39
• 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. – Martin Sleziak Feb 29 '16 at 17:24
• This seems related: math.stackexchange.com/questions/21007/… A comment there links to Wikipedia article about Frobenius number and Coin problem. – Martin Sleziak Feb 29 '16 at 17:28
• The minimum value you can get is $0$ witha choice of $p=0$ and $q=0$. – 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)$.
• 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. – carmichael561 Feb 26 '16 at 20:52
• @carmichael561 Notice that the OP has and additional condition that $p,q\ge0$. (Admittedly, the question is not entirely clear.) – Martin Sleziak Feb 29 '16 at 17:21