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