An inductive proof of the Frobenius coin problem of two denominations

Abstract

Let $a,b$ be positive, relatively prime, integers. We prove, using induction, that for every $d>ab-a-b$ there exist $x,y\in {\mathbb{Z}}_{\ge 0}$, such that $d=ax+by$. As a byproduct, we obtain a constructive recursive algorithm for identifying appropriate $x,y$ as above.

5 pages