---
tag: 0V11FEXK08
kind: statement
role: theorem
name: Frobenius coin problem
aliases: [coin-problem, frobenius-number]
msc: [11D07]
uses: [0GFKP8F8AG]
sources:
  - url: https://en.wikipedia.org/wiki/Coin_problem
    locator: n = 2
same_as:
  wikidata: Q2295746
  wikipedia: Coin problem
---

## Statement

Let $a$ and $b$ be [[coprime|0GFKP8F8AG]] integers with $a > 1$ and $b > 1$.
Then $ab - a - b$ is not of the form $ax + by$ with natural numbers $x$ and $y$.
Every integer $n > ab - a - b$ is of this form.

## Remarks

The number $ab - a - b$ is the Frobenius number of $a$ and $b$: the largest amount that one cannot pay with coins of values $a$ and $b$.
For example, with coins of $3$ and $5$, the amount $7$ is impossible, but $8$, $9$, $10$ and all larger amounts are possible.
Exactly $(a - 1)(b - 1)/2$ positive integers are not of the form $ax + by$.
For three or more coin values, no such simple formula is known.

## History

James Joseph Sylvester found the formula for two coins in 1882.

## Explanations

### L1 human

With coins of values $a$ and $b$, you can pay all large amounts when $a$ and $b$ are coprime.
The theorem gives the largest amount that you cannot pay: $ab - a - b$.