1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Simple Number Theory

  1. May 31, 2010 #1
    1. The problem statement, all variables and given/known data
    Find the least positive integer N such that every integer [tex]n \geq N[/tex] can be written in the form 4a + 7b, where a,b are non-negative integers. Prove your N has this property

    2. Relevant equations

    3. The attempt at a solution
    Well, I kind of went about doing trial and error. I know 17 is not such a number, but 18,19,20,21,22 are. I figured I'd use (strong) induction. Suppose it's true for all [tex]22 \leq k \leq n[/tex]. Consider now [tex] 18 \leq n+1 -4 < n [/tex]. By the induction hypothesis n+1 -4 = 4a + 7b, so n+1 = 4(a+1) +7b, for some non-negative a,b.

    Is this correct? What if I wanted to do it more generally. That is, if gcd(x,y)=1 find N such that, for all [tex]n \geq N[/tex], n can be written as xa+yb, for non-negative a,b?
    Last edited: May 31, 2010
  2. jcsd
  3. May 31, 2010 #2
    That is correct.

    The general case is a little harder as we can't just use trial and error and confirm our observations. I will give you a sketch here of how to show that N=(x-1)(y-1) (especially the second part is pretty vague, but you can just ask if you're having trouble figuring it out).

    First to show that N must be at least (x-1)(y-1) assume that there exists non-negative integers a,b such that:
    ax + by = (x-1)(y-1)-1
    Then (a+1 - y)x + (b + 1)y = 0 so x | b+1, and therefore [itex]b \geq x-1[/itex] and similarly [itex]a \geq y-1[/itex]. Use these inequalities and ax+by = (x-1)(y-1) - 1 to obtain a contradiction and thereby showing N must be at least (x-1)(y-1).

    Assume without loss of generality x > y. Let r be an integer in {0,1,...,y-2}. Then
    [tex](y-2)x \leq (x-1)(y-1)+r[/tex]
    You can show that there exists an integer a in {0,1,...,y-2} such that
    [tex](y-1)(x-1) +r \equiv ax \pmod y[/tex]
    [HINT: 0x, 1x, 2x, ..., (y-2)x represents all residue classes modulo y except the residue class of -x]
    and use this to find a non-negative integer b such that (x-1)(y-1)+r = ax + by. This shows (x-1)(y-1)+r can be expressed as a linear combination of x and y with positive coefficients for r in {0,1,...,y-2}. We now only need to show it for r=y-1, but then (x-1)(y-1) + r = x(y-1).
  4. May 31, 2010 #3
    That last part I don't understand.
    How do you deduce from the inequality that there is an integer a with that property? I'm sorry if it should be obvious..:uhh:
  5. May 31, 2010 #4
    The inequality isn't actually used to find a suitable a, but rather to ensure that when we do the b we choose will be non-negative.

    0x, 1x, 2x, ..., (y-2)x, (y-1)x represent all residue classes modulo y. Therefore (x-1)(y-1)+r must be congruent to one of these modulo y. So we get that for some a in {0,1,...,y-1} we have:
    [tex](x-1)(y-1)+r \equiv ax \pmod y[/tex]
    a could not be y-1 because then we would have (using that y-1 is congruent to -1 modulo y):
    [tex]-x \equiv (y-1)x = ax \equiv (x-1)(y-1)+r \equiv -x+1+r \pmod y[/tex]
    Cancelling we get [itex]1+r \equiv 0 \pmod y[/itex], but this is a contradiction since r+1 is in {1,2,...,y-1}.
  6. Jun 1, 2010 #5
    Ok, thank you!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook