# Show that this set of integers can be expressed in the form $7r+10s$ with $r, s$ non-negative integers.

The set of integers are: ${54,55,...,60}$

I am having trouble with the non-negative integers part, otherwise the question appears to be quite simple.

I have that since $gcd(7,10) = 1$, by extended euclidean algorithm, I can easily find r,s such that $7r+10s = 1$

So I can easily multiply by the respective element of the set to find $r,s$ in each case. But one of $r,s$ must be negative.

I know this question is similar to:

But I have reviewed and don't completely follow the accepted answer. Could someone elaborate a little further for me, or give me a hint to solve this problem?

• The easiest way is simply to express each of these $7$ numbers in the desired form. For instance, $54=40+14=2\cdot7+4\cdot10$, and $55=35+20=5\cdot7+2\cdot10$. There’s no need to invoke theory here. If your goal is to prove that all integers $\ge54$ can be so represented, this is an easy induction once you establish that these $7$ can be. – Brian M. Scott Sep 1 '13 at 4:17
• Yeah, checking that each number 54-60 can be represented in the desired way is the base-case of your induction, and I think that the only really reasonable way to do it is to noodle out each one by just seeing how many 10's you have to subtract to get a multiple of 7. – G Tony Jacobs Sep 1 '13 at 5:15
• @GTonyJacobs: It’s not the only way, but it is the most elementary. One can also quote Sylvester’s result whose proof is sketched in the answer at the link; that’s essentially what vadim123 has done. – Brian M. Scott Sep 1 '13 at 5:45

To elaborate on the answer that you linked to, we have that

$3\cdot 7 +(- 2)\cdot 10 =1$.

Now, we multiply this by, say, 54, so now we have

$162\cdot 7 +(- 108)\cdot 10 =54$.

$162\cdot 7 +(- 108)\cdot 10 + k\cdot 10\cdot 7-k\cdot 10 \cdot 7=54$,

with $k\in\mathbb{Z}$. Remember that we want a linear combination with non negative coefficients, so we factor the equation like this:

$(162-k\cdot 10)\cdot 7 +(- 108+k\cdot 7)\cdot 10 =54$.

Taking $k=16$, we have that

$2\cdot 7 +4\cdot 10 =54$.

I hope this helps.

• Perfect. Thanks so much! – JackReacher Sep 2 '13 at 4:37

The Frobenius number of 7 and 10 is $$g(7,10)=7\cdot 10-7-10=53$$ Hence every integer greater than or equal to 54 may be expressed as a nonnegative linear combination of 7 and 10.