this link. (Yahoo! Answers - Sylvester's Proof that g(a,b) = ab - (a+b)?)
My book says that there is a simple proof to provide the following, but it doesn't give it. Can someone please explain this:
Suppose there is 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. Assuming that m and n are relatively prime, we can derive a formula for the largest unattainable score and prove that the answer is correct.
Can anyone help derive this formula and prove that its true?
Where did you see that the other poster's proof had an n? There are a, b, x, y, m, but no n.
It is merely a choice of letter assignments, which are really arbitrary. Here your m and n are instead called a and b. When we talk of a linear combination of a and b in nonnegative integers, that can be expressed as ax + by, for nonnegative integers x and y. (Any attainable score is a linear combination of a and b.)
m is introduced by the definition of congruence. Suppose
This is true if and only if c - d is a multiple of e; that is, there exists an integer f such that
which is the same as, there exists an integer f such that
I still have not looked over the lattice points part, but I did not find any errors in the proof provided by the poster regarding the first part.
So we need to prove two things. Given positive integers a, b with gcd(a,b)=1:
1. For all integers c > ab-a-b, there exist nonnegative integers x, y such that ax + by = c.
2. For c = ab-a-b, there are no solutions to ax + by = c in nonnegative integers.