Hey there! Sign in to join this conversationNew here? Join for free
x Turn on thread page Beta
    • Thread Starter
    Offline

    0
    ReputationRep:
    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?
    Offline

    17
    ReputationRep:
    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?
    • Thread Starter
    Offline

    0
    ReputationRep:
    (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.
    Offline

    17
    ReputationRep:
    (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).
    • Thread Starter
    Offline

    0
    ReputationRep:
    (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.
    Offline

    18
    ReputationRep:
    (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
    • Thread Starter
    Offline

    0
    ReputationRep:
    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.
    Offline

    18
    ReputationRep:
    (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.
    • Thread Starter
    Offline

    0
    ReputationRep:
    Edit: Double post.
    • Thread Starter
    Offline

    0
    ReputationRep:
    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 M = \left\{0,1,2,3...ab-a-b\right\} and m\in M. Then either
    xa+yb = m
    or
    xa+yb = ab-a-b-m
    holds true.
    Proof: If xa+yb = m lacks solutions, then GCD (a,m) = 1 and GCD (b,m) = 1. Therefore, GCD(ab-a-b-m,m) = 1. To see why, divide ab-a-b-m with m:
    \frac{ab-a-b-m}{m} = \frac{ab}{m} - {a+b}{m}-1
    Obviously, GCD(ab,m) = 1. Also, the following is NOT true:
    ab \equiv a+b \hspace{6} (mod\hspace{6}  m)
    This is because
    a+b = ab(\frac{1}{a}+\frac{1}{b})
    and as we know GCD(a,b) =1. Therefore the above cannot be true and thus GCD(ab-a-b-m,m)=1.

    As GCD(ab-a-b-m,m)=1, there must be a c and d such that:
    c(ab-a-b-m) + dm = 1.It follows that there exists a k for which
    k(c(ab-a-b-m)+dm) = ax+by.This only goes for the the numbers m where there are no solutions for ax+by=m.
    • Thread Starter
    Offline

    0
    ReputationRep:
    Ups, I'm pretty convinced my proof is false. I will try to formulate a new one (which should be simpler as well).
 
 
 
Reply
Submit reply
Turn on thread page Beta
Updated: March 28, 2013
Poll
Are you going to a festival?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.