Question

In some country there are 12-, 20-, and 30-florin coins only. What is the minimal amount that can be paid if both sides have many coins of each type?

Answer 1

The smallest amount that can be paid is the greatest common divisor ("gcd") of the denominations of the coins.

gcd (12, 20, 30) = gcd( gcd(12, 20), 30) = gcd(4, 30) = 2

So, 2 can be written as a linear combination of 12, 20, and 30.

For example, 2 = 12 + 20 - 30. So for an item that costs 2 florins, the Buyer gives the Seller a 12-florin and a 20-florin coin, and receives a 30-florin coin in change.