Chicken McNugget Theorem

https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem#Generalization The Chicken McNugget Theorem (or Postage Stamp Problem or Frobenius Coin Problem) states that for any two relatively prime positive integers $m,n$, the greatest integer that cannot be written in the form $am+bn$ for nonnegative integers $a,b$ is $mn-m-n$.

Generalization

If $m$ and $n$ are not relatively prime, then we can simply rearrange $am+bn$ into the form

$\gcd (m,n)\left(a\frac{m}{\gcd (m,n)}+b\frac{n}{\gcd (m,n)}\right)$

$\frac{m}{\gcd (m,n)}$ and $\frac{n}{\gcd (m,n)}$ are relatively prime, so we apply Chicken McNugget to find a bound $\frac{mn}{\gcd (m,n{)}^2}-\frac{m}{\gcd (m,n)}-\frac{n}{\gcd (m,n)}$

We can simply multiply $\gcd (m,n)$ back into the bound to get $\frac{mn}{\gcd (m,n)}-m-n=\text{lcm}(m,n)-m-n$

Therefore, all multiples of $\gcd (m,n)$ greater than $\text{lcm}(m,n)-m-n$ are representable in the form $am+bn$ for some positive integers $a,b$.