un número n como pa+qb

Question

¿Cómo podemos expresar un número $n$ $pa+qb$ donde $p \geq0$ $q \geq 0$ $p$ $q$ no puede ser fracción. En el concurso tengo un rompecabezas como si podemos expresar $c$ como la suma de $a$ $b$ en forma de $pa+qb$. Supongamos $a$$3$$b$$4$$c$$7$, por lo que podemos expresar $7$$3+4$. Supongamos $a$ $4$ $b$ $6$ $c$ $15$ pero no podemos expresar $15$ como la suma de $4 \cdot p+6 \cdot q$.

NOTA: $p$ $q$ NO PUEDE SER FRACCIONES.

Me ocurrió con un enfoque que tome $\gcd$ $a$ $b$ y comprobar si su $\gcd$ deja en cero, como resto al $\gcd$ divide $c$. ¿Hay algún método general para comprobar esto ?

Answer 1

Si $a,b$ son fijos números naturales, entonces el conjunto de todos los enteros $n$ que puede ser escrito en la forma $n=pa+qb$ para los números enteros $p$ $q$ es, precisamente, el conjunto de los múltiplos de el máximo común divisor de a$a$$b$. Por lo $n$ puede ser escrita en la forma deseada, si y sólo si $n$ es divisible por $\gcd(a,b)$.