Problem 5 : A Problem in Number Theory

I attended a coaching center for preparing for competitive examinations. So, it wasn’t unexpected that I’d come across students who were extremely brilliant. Back then, I met an interesting guy who’d give up all other problems and sit with interesting problems in geometry and number theory. This just was one of the few theorems that became etched in my mind.

Problem Statement

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\).

The Solution

It is easy to see that \(mn - m - n\) cannot be written in the form \(am + bn\). We need to show that for any whole number \(k\), \(mn - m - n + k\) can be written in the form \(am + bn\). WLOG consider \(n > m\), we can formalize the equation we need to prove as -

\[\exists \; \alpha >=1 , \; \beta >= 1\] \[\alpha.m + \beta.n = mn + k \; \forall \; k >= 0\]

Now, we can write \(\delta = \left \lceil{k/n}\right \rceil\), \(k = \delta.n + k.mod n\) and \(\gamma < = m + \delta\), then, the RHS of the aforementioned equation can be written as -

\[\implies \alpha.m + \beta.n = (m+\delta-\gamma).n + \gamma.n + k.mod n\]

Comparing, both sides we can set \(\beta = m + \delta - \gamma\),

\[\implies \alpha = \frac{\gamma.n + k.mod n}{m}\]

Now, note that the range of \(\gamma\) includes \(0,1,...., m-1\).

Since m and n are co-prime, the set formed by \((\gamma.n).mod n\) for \(\gamma < m\) is simply a permutation of the set \(S = {0,1,...,m-1}\).

Permutation [Permutation Proof]

Alos, \(k.modn\) is congruent to some \(j.mod m\) for some \(j\) in \(S\).

Therefore, we can always find a \(\gamma\) such that \(\gamma.n + k.mod n\) is divisible by \(m\).