x Turn on thread page Beta
 You are Here: Home >< Maths

# Number theory watch

1. 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 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:

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

since we can write

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?
2. Actually, all natural numbers can be written in that form.

Since are relatively prime, this implies that

Then by Bézout's lemma there exists integers such that

Do you see how you can now conclude all natural numbers can be written in that form?
3. (Original post by Noble.)
Actually, all integers can be written in that form.

Since are relatively prime, this implies that

Then by Bézout's lemma there exists integers such that

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.
4. (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).
5. (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.
6. (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 and is expressible as
7. 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.
8. (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.
9. Edit: Double post.
10. What I meant to write was "[...]I'm guessing I have misunderstood the problem". But let's try to formalize it a bit:
Lemma: Let and Then either

or

holds true.
Proof: If lacks solutions, then and . Therefore, . To see why, divide ab-a-b-m with m:

Obviously, . Also, the following is NOT true:

This is because

and as we know . Therefore the above cannot be true and thus

As , there must be a c and d such that:
It follows that there exists a k for which
This only goes for the the numbers m where there are no solutions for ax+by=m.
11. Ups, I'm pretty convinced my proof is false. I will try to formulate a new one (which should be simpler as well).

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: March 28, 2013
Today on TSR

### Negatives of studying at Oxbridge

What are the downsides?

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams