The largest number not in the form of ax+by, with gdc(a,b)=1.

lifom

I have tried some values of a,b. And I guess the largest number not in the form of ax+by, (x,y are non-negative integers) with gcd(a,b)=1 is ab-a-b. But I don't know how to prove it. Can anyone give me some hints or directions? I don't want the detail proof,as I want to try it by myself. thank you

Raphie

Edit

Raphie

All integers are constructible "in the form" ax + by. Just set x and y to 1 and then ax + by becomes a +b. Are you presupposing that a, b, x and y are all different values? Or maybe I am simply misreading the question?

Raphie

To be a bit more clear, if you set x and y to 1, then a + b (with gcd = 1) becomes, for the even numbers, a very broad generalization of Goldbach's Conjecture (which applies to primes only). And for the odd numbers, well, I am sure you can see the utility, with respect to that, of setting either a or b to 1.

e.g. in relation to the form you mentioned...

5*6 - 5 - 6 = 19
(18 * 1) + (1 * 1) = 19

dodo

Hi, lifom,
I assume you mean a,b > 1, otherwise it won't work.

Here is an observation that may help your way to a proof: first, make a list of all numbers, from 0 inclusive and less than ab-a-b, which DO have the form ax+by with x,y >= 0.

And now, make a second list with the numbers of the form ab-a-b-n, where n is a number in the first list. You will find that the second list contains exactly the missing numbers in the first list.

lifom

Consider 3x+7y, (x,y are non negative number),gcd(3,7) =1. some nonegative integers cannot be in form of 3x+7y (example, 3x+7y can't be 1,2,... the largest number not in the form of 3x+7y is 11. (3*7-3-7) so I guess the largest number not in the form of ax+by,gcd(a,b)=1 is ab-a-b. But I don't know how to prove.

yuiop

You seem to be saying that any number larger than (a*b-a-b) where a and b have a gcd of 1 can be constructed in the form ax+by where x and y can be any non negative integer (including zero) and x and y do not have to be equal. It seems to work for some random samples I ran in a simple program. For example if a=3 and b=11, then any number larger than (3*11-3-11 = 19) can be constructed in the form 3x+11y where x>-1 and y>-1. I look forward to seeing a proof!

dodo

In the example in post #6, the numbers of the required form are 0,3,6,7,9,10, and then 12,13,14... The numbers not of the form are all negatives (since a,b,x,y are not negative), 1,2,4,5,8,11, and then no more.

What I was suggesting is to realize the relation between these two lists: if you take 11-n, where n is one of 0,3,6,7,9,10, you obtain 1,2,4,5,8,11. Why?

To save some saliva, define the predicate P(n) to mean "n can be expressed as ax+by, with x,y non-negative". The question was why ab-a-b is the highest n such that P(n) is false.

A useful lemma in that direction is to prove first that P(n) is false if and only if P(ab-a-b-n) is true. Then we are done, since the minimum n for which P(n) is true is n=0.

Yuqing

This is actually a pretty well researched problem. I believe there are entire books related to variants of this problem. The problem of finding this lower bound is called the Frobenius problem or more well known as the coin problem. In the case of 2 variables, your equation is indeed correct.

dodo

Dang, there goes another wheel. : P

lifom

Thanks Dodo. I have written the proof.

Let P(n) : "n is a form of ax+by, gcd(a,b)=1, a,b are positive integers, x,y are non negative integers"

Clam 1: If P(n1) and P(n2) is true, then P(n1+n2) is also true.
(since n1=ax1+by1, n2=ax2+by2, then (n1+n2)=a(x1+x2)+b(y1+y2)
x1+x2>=0,y1+y2>=0)

Clam 2: P(ab-a-b) must be false.
Assume P(ab-a-b) is true, there exist x,y>=0 such that ax+by=ab-a-b
rearranging, a(x+1) = b(a-y-1), since gcd(a,b)=1. that means a|(a-y-1).
also a-y-1>=0 and a-y-1<a (because y>=0).
Therefore a-y-1 can only be 0.
Then a(x+1) = b(0) imply x=-1 which is contridiction! (x must be >=0!)
So we CANNOT find non negative integers x,y such that ax+by = ab-a-b.

Now consider P(n) and P(ab-a-b-n)
Since P(ab-a-b) must be false (by Clam 1)
P(n) and P(ab-a-b-n) cannot be both true. (by Clam 2)

Lastly, since n = 0 is the minimum integer such that P(n) is true. So the maximum number such that P(n) is not true = ab-a-b.

Is there any mistake(s) in my proof?

yuiop

Here is a closely related challenge. Prove that there are exactly only (a-1)*(b-1)/2 positive integers with the form ax+by where gcd(a,b)=1, a,b are positive integers and x,y are non negative integers (i.e. same constraints as the problem in the OP).

Not sure if this is true, but it seems to be.

<EDIT> This should of said there are exactly only (a-1)*(b-1)/2 positive integers NOT of the form ax+by. See posts 13 and 14.

lifom

I think it is not true. Example: the largest number not in the form 3x+7y is 3*7-3-7=11. That means it can be 12,13,14,... and so on. So any integer > 11 can be in the form of
3x+7y.

Do you mean there are exactly only (a-1)*(b-1)/2 positive integers NOT with the form ax+by where gcd(a,b)=1, a,b are positive integers and x,y are non negative integers?

yuiop

Yes, that is what I meant. Sorry... my bad.

For example with a=3 and b=7 the positive integers NOT with the form ax+by are 1,2,4,5,8 and 11. That is a total of 6 solutions in agreement with (a-1)*(b-1)/2 = (3-1)*(7-1)/2 = 6.

Actually another way of stating it, more closely related to your original formula, is that there are exactly only (ab-a-b+1)/2 positive integers NOT with the form ax+by where gcd(a,b)=1, a,b are positive integers and x,y are non negative integers.

Additionally, if x and y are constrained such that (0 <= x <= maxX) and (0 <= y <= maxY) where maxX and maxY are positive integers and (maxX>=b AND maxY>=a), then there are exactly (ab-a-b+1) positive integers NOT of the form ax+by.