Sometimes we are only interested in solutions to ax + by = c using nonnegative values for x and y. ?

Question

1.) Make a list of some of the numbers of the form 3x + 5y with x >= 0 and y >= 0. Make a conjecture as to which values are not possible. Then prove that your conjecture is correct.

2.) For each of the following values of (a,b), find the largest number that is not of the form ax + by with x >= 0 and y >= 0.

a) (a,b)=(3,7)

b) (a,b)=(5,7)

c) (a,b)=(4,11)

3.) Let gcd(a,b)=1. Using your result from (2.) find a conjectural formula in terms of a and b for the largest number that is not of the form ax + by with x >= 0 and y >= 0. Check your conjecture for at least two more values of (a,b).

4.) Prove that your conjectural formula in (3.) is correct.

5.) Try to generalize this problem to sums of three terms ax + by = cz with x >= 0, y >= 0, and z >= 0.

Answer 1

You mean of course non negative INTEGER values for x and y, otherwise the problem is not interesting.

Please read my answer to a related question some time ago, that will help You to understand the further explanation:

http://answers.yahoo.com/question/index;...

1.) The linear form 3x + 5y does not represent the following

4 = (3-1)(5-1)/2 numbers: 1, 2, 4,and 7;

the largest 7 = 3*5 - 3 - 5.

2.) 3x + 7y does not represent the following

6 = (3-1)(7-1)/2 numbers: 1, 2, 4, 5, 8 and 11;

the largest 11 = 3*7 - 3 - 7.

5x + 7y does not represent the following

12 = (5-1)(7-1)/2 numbers: 1, 2, 3, 4, 6, 8, 9 ,11, 13, 16, 18 and 23;

the largest 23 = 5*7 - 5 - 7.

4x + 11y does not represent the following

15 = (4-1)(11-1)/2 numbers: 1, 2, 3, 5, 6, 7, 9, 10, 13, 14, 17,18, 21, 25 and 29; the largest 29 = 4*11 - 4 - 11.

3.) The largest number, not representable by the form

ax + by /1 < a < b; x, y ≥ 0, a, b, x, y - integer, GCD(a, b) = 1/

is ab - a - b.

4.) Proof: let ax + by = ab - a - b, then taking congruence by modulo a:

ax + by ≡ ab - a - b (mod a) or by ≡ - b (mod a)

Here we CAN divide by b, since a and b are co-prime and obtain:

y ≡ -1 ≡ a - 1 ≡ 2a - 1 ≡ . .  (mod a)

Since y ≥ 0 if we cannot take -1, taking y = a - 1, then

ax = ab - a - b - by = ab - a - b(a - 1) = -a < 0, hence ax and x cannot be non-negative. Taking other admissible values for y we get even smaller values for ax. That means ab - a - b is not representable in the desired manner.

But every integer greater than ab - a - b is. Indeed let

ax + by = ab - a - b + k for k = 1, 2, . ., a-1; again

by ≡ k - b (mod a) - this congruence has solution for some

y = 0, 1,  . ., a-2, but NOT for y ≡ -1 as above, then

ax = ab - a - b + k - by ≥ab - a - b + k - b(a-2) = b - a + k > 0, so there exists a solution with x non negative.

If k = a we have obviously ax + by = ab - b = a*0 + b*(a-1), the greater values of k are treated likely.

The above can be proven easily rewriting

ax + by = ab - a - b ((+ k)) as a(x+1) + b(y+1) = ab ((+ k)) or

ax' + by' = ab ((+ k)) and referring to my previous answer.