Number Theory - Largest Impossible Score

[Frillth]

Edit: I finally figured this problem out, although I didn't use residue systems, so a solution is no longer necessary.

Homework Statement

For this problem, I need to find a fomula for the largest unattainable score in a game where you can either score m or n points at a time (m and n are relatively prime) and prove that this formula will always work. Complete residue systems are suggested to be used in the proof.

Homework Equations

{0, n, 2n, 3n, ... , (m-1)n} is a complete residue system mod m when m and n are relatively prime.

The Attempt at a Solution

Through trial and error, I have found that the largest impossible score is mn - (m+n). I'm stuck, however, on proving this. I don't even know how to start, so any help would be greatly appreciated.

 

[mighty2000]

Great job on finding a solution to the problem! It is always satisfying to figure out a difficult problem. However, I would like to suggest that you revisit the use of complete residue systems in your proof. it is important to have a strong and logical reasoning behind any solution or theory we propose.

To start, let's define a complete residue system (CRS) as a set of numbers that, when divided by a certain number, leave different remainders. In this case, our CRS is {0, n, 2n, 3n, ... , (m-1)n} mod m. This means that when we divide these numbers by m, we will get different remainders ranging from 0 to m-1.

Now, let's consider the game where we can score m or n points at a time. In order for a score to be impossible, it must be larger than any combination of m and n that we can achieve. This means that the largest impossible score must be mn - (m+n), as you have found.

To prove this, let's consider the set of all possible scores that we can achieve in the game. This set can be represented as {0, n, 2n, 3n, ... , (m-1)n, m, m+n, 2m, 2m+n, ... , (m-1)m, (m-1)m+n}. Notice that this set is the same as our CRS mod m, except for the addition of multiples of m. This is because every time we score m points, we can also score (m+n) points by scoring n points as well.

Now, let's consider the set of impossible scores. This set can be represented as {mn, mn+n, mn+2n, ... , mn+(m-1)n}. Notice that this set is also the same as our CRS mod m, except for the addition of multiples of mn. This is because every time we score mn points, we can also score (mn+n) points by scoring n points as well.

Since our CRS mod m contains all possible remainders, and our set of impossible scores also contains all possible remainders, we can conclude that the largest impossible score must be the largest remainder in our CRS mod m, which is mn - (m+n).

I hope this helps to clarify the use of complete residue systems in your proof.