An inductive proof of the Frobenius coin problem of two denominations

2023/08/06 by Kapetanakis, Giorgos, Rizos, Ioannis
#11D07 (Primary) 11D04 (Secondary) #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2308.03050

Abstract

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

Related

• Teaching perspectives of the Frobenius coin problem of two denominators
• A new Rational Generating Function for the Frobenius Coin Problem
• Short Proof: Exact Solution to the Finite Frobenius Coin Problem
• Computing a Frobenius Coin Problem decision problem in O(n²)
• On the Frobenius Coin Problem in Three Variables