# Pythagorean coins

To make payments, the Pythagoreans use coins in no more than three denominations. The three denominations are in whole Oboloi amounts, and the sum of the squares of the two smaller denominations equals the square of the largest denomination. The amount of $1,000$ Oboloi, and any larger whole Oboloi sum, can be obtained using the three distinct types of coins. However, the exact amount of $999$ Oboloi can not be obtained (and hence requires change).

What coin denominations do the Pythagoreans use?

• Is this a Project Euler style puzzle, where the tricky part is figuring out how to write the program? I don't have much hope for an analytic solution. – Lopsy Feb 22 '15 at 21:21
• @Lopsy - this particular three coin problem does have an analytical solution. – Johannes Feb 23 '15 at 2:11
• If the amount of 999 Oboloi can not be exactly obtained with their 3 types of coin, what do they use for change? – KSmarts Feb 23 '15 at 22:16
• @KSmarts - To make a 999 Oboloi net payment requires a payment of 16 coins (8 each of 65 Oboloi and 72 Oboloi) and a return of one 97 Oboloi coin. – Johannes Feb 24 '15 at 16:13

Answer: The three denominations are $65$, $72$ and $97$.

• How did I detect this answer? I searched the list of primitive Pythagorean triples at [link to triple list], while using the Frobenius applet available at [applet link]. Based on my search I know that the answer to the puzzle is unique; still, I would like to see a clean mathematical argument for this (that is not based on enumeration).

• Even proving that all values from $1000$ onwards are representable is very tedious. I checked $65$ underlying individual cases with a computer program.

• The proof that the value $999$ is not representable is doable. Suppose that there exist non-negative integers $x,y,z$ with $65x+72y+97z=999$. By considering the equation modulo 9, we get that $x\equiv z \pmod9$. By considering the equation modulo 2, we get that $x+z$ must be odd. Since $0\le x\le15$ and $0\le z\le10$, this only leaves a handful of subcases with $x=z+9$ or $z=x+9$; none of these subcases yields an integral value for $y$.

• I have also found a [scientific paper] that provides an explicit formula for the Frobenius number of primitive Pythagorean triples:
$$F(m^2-n^2, 2mn, m^2+n^2)=(m−1)(m^2−n^2)+(m−1)(2mn)−(m^2+n^2).$$ By setting $m=9$ and $n=4$, we recover the solution $65$, $72$ and $97$ for the Pythagorean coin puzzle as stated above.

• The closed form of the paper gives that m divides 999, so there are only 8 candidate values of m to consider, each with at most 2 candidate values of n. – Peter Taylor Mar 8 '16 at 13:25
• In fact, since m > n for a primitive triple, it turns out that each candidate value of m only has 1 candidate value of n. – Peter Taylor Mar 8 '16 at 23:21