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: Number theory questions

  1. Jan 29, 2006 #1
    1. Prove (a,b)=1 iff (a+b, ab)=1

    I'm guessing the main tools I have here are xa+yb=1 and the lemma behind the Euclidean algorithm: if a=bq+r, (a,b)=(b,r). I figure I need to do lots of manipulation to build up a more complicated equality, but I can't make it quite work. Any suggestions?

    2. Suppose x an integer such that 0<x<n^3. Show there exist a_0, a_1, a_2 in {0,1,...,n-1} such that x=a_0+a_1n+a_2n^2

    I don't even know where to start this one.
     
    Last edited: Jan 29, 2006
  2. jcsd
  3. Jan 29, 2006 #2

    StatusX

    User Avatar
    Homework Helper

    For the second one, you mean ...+ a_2 n^2, right? If so, start with the division algorithm x=qn^2+r.
     
  4. Jan 29, 2006 #3
    Yes, that's what I meant; I've changed it now. Thanks for your help!
     
  5. Jan 29, 2006 #4

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    1) (a+b,ab)=1 => (a,b)=1 can be done the way you have planned, a linear combination of a+b and ab can be turned into a linear combination of a and b. Show what you've tried!

    For the other direction, if a prime p divides (a+b,ab) what else can you say it divides?

    Did you manage 2)? If not where has StatusX's hint led you?
     
  6. Jan 29, 2006 #5
    Since a,b are assumed to be integers, isn't x(a+b)+yab=(x+yb)a+xb an integer combination? My trouble is the other direction, starting from (a,b)=1. I don't think I see where your question is headed there.

    The second problem followed pretty quickly after StatusX's hint.
     
  7. Jan 29, 2006 #6
    All right, I think I follow your question a bit. If a prime divides (a+b,ab) then it divides a+b, ab, and at least one of a or b. What else do I need?
     
  8. Jan 29, 2006 #7

    StatusX

    User Avatar
    Homework Helper

    I don't know if this is what shmoe meant, but what about a^2 and b^2?
     
  9. Jan 30, 2006 #8
    the 2nd one is simple...its based on the counting principle/grouping and
    is about "base numbers" the thing you should think of is how do we create base-number systems ie. binary,tertiary,octal, decimal,hex...how is each one created. what makes a binary number binary and why does the entire binary set contian just the alphabet {0,1}

    for the first one is (,) an unknown operator or does it stand for remainder?
     
  10. Jan 30, 2006 #9
    I have the second one now. In the first one, the operator is greatest common divisor.
     
  11. Jan 30, 2006 #10

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    You're a small step away, can you show p will divide *both* a and b from what you have?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook