For positive integers having greatest common divisor one, the Frobenius number is the largest integer not expressible as with nonnegative integer coefficients . A coin interpretation allows unlimited copies of denominations , rather than a fixed number of coins.
For denominations and , the value is . The next four values are representable: , , and . Repeatedly adding then covers every larger integer. The two-generator Frobenius theorem proves the formula for two coprime denominations.
The hypotheses exclude two different degeneracies. If all denominations have a common divisor greater than one, infinitely many positive amounts are impossible, so no largest impossible amount exists. If denomination one is present, every nonnegative integer is possible; the usual positive-gap problem disappears. Some conventions assign the latter case the value .
First, cannot equal with nonnegative integers . Reducing modulo gives ; coprimality forces to be a positive multiple of . Hence , a contradiction.
Now take any integer . Multiplication by permutes the residue classes modulo , so choose with . The difference is a multiple of and satisfies . It is therefore nonnegative, giving and . This proves both the largest gap and representability of every greater integer.
Articles by others on the same topic
There are currently no matching articles.