Number theory

If and a and b are relatively prime natural numbers, how many natural numbers cannot be written on the form xa+yb where x and y are nonnegative integers?

My thoughts:
First of all, we want to know the highest number that cannot be written on above form. That will make it easier to then investigate the numbers between 1 and said number that cannot be written on above form.

Let n be a fixed integer (also negative) such that

n = ax_{0}+by_{0}.

If n lacks solutions for positive x0 and y0, assume that we want x0 to be as small as positive but nonetheless nonnegative. Then the following holds true:

0 \leq x_{0} \leq b-1

y_{0} \leq -1

ax_{0} > n

We could go as far as state the following since y0 is negative

ax_{0}-b \geq n

since

x_{0}\leq b-1

we can write

a(b-1)-b \geq n \leftrightarrow ab-a-b \geq n

Now to my question: How do I continue to evaluate what numbers in the interval [1,ab-a-b] that may not be written on above form?

(edited 11 years ago)

Reply 1

Noble.

17

Actually, all natural numbers can be written in that form.

Since

a,b

are relatively prime, this implies that

\gcd(a,b) = 1

Then by Bézout's lemma there exists integers

x,y

such that

xa + yb = \gcd(a,b) = 1

Do you see how you can now conclude all natural numbers can be written in that form?

(edited 11 years ago)

Reply 2

EulerRules

OP

Original post by Noble.

Actually, all integers can be written in that form.

Since

a,b

are relatively prime, this implies that

\gcd(a,b) = 1

Then by Bézout's lemma there exists integers

x,y

such that

xa + yb = \gcd(a,b) = 1

Do you see how you can now conclude all integers can be written in that form?

I'm sorry if this wasn't clear, but x and y are nonnegative integers whereas x0 is nonnegative and y0 is any integer.

Reply 3

Noble.

17

Original post by EulerRules

I'm sorry if this wasn't clear, but x and y are nonnegative integers whereas x0 is nonnegative and y0 is any integer.

Yeah sorry, I realised that and edited my post. You can't make any integer in that case, just the positive ones (or the natural numbers rather).

Reply 4

EulerRules

OP

Original post by Noble.

Yeah sorry, I realised that and edited my post. You can't make any integer in that case, just the positive ones (or the natural numbers rather).

Correct, but the problem is rather figuring out what natural numbers cannot be written on the form ax+yb. I'll edit to "natural numbers" in my OP.

Reply 5

Lord of the Flies

19

Original post by EulerRules

If and a and b are relatively prime natural numbers, how many natural numbers cannot be written on the form xa+yb where x and y are nonnegative integers?

Famous problem! Try to show that one (and only one) of

m

and

ab-a-b-m

is expressible as

ax+by

(edited 11 years ago)

Reply 6

EulerRules

OP

Is m a natural number? Say for example a=3, b=7, then ab-a-b-m+1 results in 12-m, and you claim that there is only one m that would satisfy the equation 3x+7y = 12-m which is wrong. Can you please correct me because I'm guessing I have misunderstood the problem.

(edited 11 years ago)

Reply 7

Lord of the Flies

19

Original post by EulerRules

Is m a natural number? Say for example a=3, b=7, then ab-a-b-m+1 results in 12-m, and you claim that there is only one m that would satisfy the equation 3x+7y = 12-m which is wrong. Can you please correct me because I'm guessing I have understood the problem.

My claim was that for each m between 0 and ab-a-b, only one of 3x + 7y = 11 - m and 3x + 7y = m will have a solution (sorry, I added a 1 for God knows what reason). Let me know if I've misunderstood something.

3x + 7y = 0 has a solution and 3x + 7y = 11 does not.
3x + 7y = 1 has no solution and 3x + 7y = 10 does.

etc.

3x + 7y = 5 has no solution and 3x + 7y = 6 does.