# Largest integer which cannot be made with 5x + 7y where x and y are integers

What is the largest positive integer $n_0$ for which there are no $x, y ∈ \mathbb{Z}$ with $x, y ≥ 0$ so that $n_0 = 5x + 7y$?

Give a proof that if $n > n_0$ then there are non-negative integers $x$ and $y$ so that $n = 5x + 7y$.

• No, he stated it correctly. (The smallest is trivially $1$.) – TMM Jan 31 '17 at 23:08
• From some point onwards, every integer is representable as $5x+7y$, so it does make sense to ask for the largest which cannot be so represented. – Old John Jan 31 '17 at 23:10
• The largest integer not possible is $(5-1)(7-1)-1=23$. see math.stackexchange.com/questions/2118907/… – SSepehr Jan 31 '17 at 23:11
• – астон вілла олоф мэллбэрг Jan 31 '17 at 23:28
• Oops. I misread old johns comment. He basically said the same thing I did. Sorry. – fleablood Jan 31 '17 at 23:56

There is a formula if the least common divisor of the 2 numbers (5, 7) is equal to 1, which is always true for primes: $$g(a,b)=(a-1)(b-1)-1,gcd(a,b)=1$$ $$g(5,7)=(5-1)(7-1)-1=23$$
This is the Frobenius coin problem. For given $c_1,c_2$ with $\gcd(c_1,c_2)=1$, the largest number which cannot be represented by $ac_1+bc_2$ with $a,b \ge 0$ is $(c_1c_2-c_1-c_2)$.
The intuition I prefer to understand this is to see what the value of multiples of the larger coin, say $c_1$, is modulo the smaller $c_2$, and see that the last modular equivalence is filled at $c_1c_2-c_1$, which means it must still be open at $(c_1c_2-c_1-c_2)$