1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Unattainable scores

  1. Aug 4, 2006 #1
    Suppose you have a game in which there are two kinds of scoring events. One event gives a score of m points, and the other gives a score of n points. Assume gcd(m,n)=1. Derive a formula for the largest unattainable score. Prove your answer is correct.

    Well, I only can figure of these:

    since (m, n)= 1, then we have

    {0, m, 2m,...., (n-1)m} as a complete residue system mod n


    {0, n, 2n,...., (m-1)n} as a complete residue system mod m.

    What should I do then?
  2. jcsd
  3. Aug 4, 2006 #2


    User Avatar
    Homework Helper

    Start with am+bn=N, which has integer solutions a,b for all N since (m,n)=1. Now, these solutions aren't necessarily positive, but if a,b are one set of solutions, then a+kn, b-km are also solutions, where k ranges over the integers.

    Now assume a<0, in which case b>N/n. Now try new solutions a1=a+n, b1=b-m. If a1<0 still, then b1>N/n, and we can continue this process until ai>=0. But at this point, bi will only remain positive if N is greater than... See if you can complete this argument.
    Last edited: Aug 4, 2006
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook