2
$\begingroup$

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:

General set of integer solutions $(p,q)$ to $1 = pa + qb$ for integers $a,b$ such that $\gcd(a,b)=1$

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?

Many thanks in advance!

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Brian M. Scott Sep 1 '13 at 4:17
  • $\begingroup$ 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. $\endgroup$ – G Tony Jacobs Sep 1 '13 at 5:15
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Sep 1 '13 at 5:45
1
$\begingroup$

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

Now we add a zero:

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

$\endgroup$
  • $\begingroup$ Perfect. Thanks so much! $\endgroup$ – JackReacher Sep 2 '13 at 4:37
1
$\begingroup$

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.

$\endgroup$

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.