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!

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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Number theory questions
Loading...