1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Basic number theory

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

    My thoughts:
    Let n be a fixed integer such that[itex]n=ax_{0}+by_{0}[/itex]. Assume that we want to minimize [itex]x_{0}[/itex] but keep it nonnegative. Then the following must be true:
    [itex]0 \leq x_{0} \leq b-1[/itex]
    If n cannot be expressed where both x0 and y0 are positive (I am trying to get at the maximum number which cannot be expressed on above form), then the following must be true as well
    [itex]y_{0} \leq -1[/itex]
    and
    [itex]ax_{0}>n[/itex]
    Since y0 is negative, the following holds true:
    [itex]ax_{0}-b \geq n[/itex]
    And since [itex]x_{0}\leq b-1[/itex]
    [itex]a(b-1)-b \geq n \rightarrow ab-a-b \geq n[/itex]
    The largest number that cannot be written on above form is ab-a-b. How do I determine what numbers between 1 and ab-a-b that cannot be written on the form?

    IF you have any other ideas on how to solve this problem, please share them with me. But do keep in mind that I'm only a junior in high school so I may not be familiar with more "advanced" methods.
     
  2. jcsd
  3. May 8, 2015 #2
    Since ##a## and ##b## are relatively prime, you can find ##(u,v)\in \mathbb{Z}^2## such that ##1 = a u + bv## (Bezout theorem).
    You must have ## a (x -u(ax+by) ) = b (v(ax+by) - y) ##.
    Using again that ##\text{gcd}(a,b) = 1##, ## a ## divides ## (v(ax+by) - y) ## and ## b ## devides ## (x -u(ax+by) ) ##. Solving that will give you the set of solutions in ##\mathbb{Z}^2## for ##(x,y)## depending on ##a,b,u,v## and some factors ##k,k'##.
     
  4. May 9, 2015 #3

    NascentOxygen

    User Avatar

    Staff: Mentor

    geoffrey159, you replied to a post two years old. The poster hasn't logged in to PF since that time.
     
  5. May 9, 2015 #4
    Sorry, I won't do it anymore
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Basic number theory
  1. Number Theory (Replies: 1)

  2. Number Theory (Replies: 2)

  3. Number Theory (Replies: 7)

  4. Number of theory (Replies: 1)

Loading...