1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ My bad, gonna fix it. $\endgroup$ – Zonko Jan 31 '17 at 23:47
3
$\begingroup$

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)$

$\endgroup$
  • $\begingroup$ By now this Q must be a duplicate of a duplicate of a ...... $\endgroup$ – DanielWainfleet Feb 1 '17 at 0:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.