# 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

$g(m,n)(agcd(m,n)m +bgcd(m,n)n )$

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

We can simply multiply $g(m,n)$ back into the bound to get $gcd(m,n)mn −m−n=lcm(m,n)−m−n$

Therefore, all multiples of $g(m,n)$ greater than $lcm(m,n)−m−n$ are representable in the form $am+bn$ for some positive integers $a,b$.