Results 1 to 8 of 8

Math Help - Divisibility

  1. #1
    Member
    Joined
    Mar 2008
    Posts
    99

    Divisibility

    1) If (a,b) = d, prove that (\frac{a}{d}, \frac{b}{d}) = 1

    Not quite sure how to do that one..

    2) If a|(b+c) and (b,c)=1, prove that (a,b) = 1 = (a,c)

    Suppose d|a and d|b

    a=du for some u in Z
    b=dv for some v in Z

    a|(b+c)
    b+c=aw
    c=aw-b
    c=duw-dv
    c=d(uw-v)
    d|c

    Now, how do I say that (a,b) = 1 = (a,c) ?

    Thanks for any help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    #1
    Let x = \left(\frac{a}{d}, \frac{b}{d}\right) \: {\color{blue} \geq 1} (gcd of any two integers is always greater than or equal to 1).

    By definition, there are some integers r, s such that xr = \frac{a}{d} \: \: \iff \: \: dxr = a and xs = \frac{b}{d} \: \: \iff \: \: dxs = b.

    In other words, dx is a common divisor of a and b. Since (a,b) = d, then dx \leq d \: \: \Rightarrow \: \: x \leq 1.

    However, recall that x \geq 1. So, x = \left(\frac{a}{d}, \frac{b}{d}\right) = 1
    Follow Math Help Forum on Facebook and Google+

  3. #3
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by shadow_2145 View Post
    1) If (a,b) = d, prove that (\frac{a}{d}, \frac{b}{d}) = 1
    i really like o_O's solution to this. but here is how i was thinking of proving it. being very unimaginative, i like to go by definitions a lot and leave the fancy stuff to geniuses like o_O

    disclaimer (?): to avoid having to say, "for some integers..." or "where so and so are integers..." all the time (which you should do!) just assume that whenever i introduce a new variable it is an integer.

    recall the properties of the gcd:

    Definition: (a,b) = d means that:
    (1) d \mid a and d \mid b
    (2) If there is x such that x \mid a and x \mid b, then x \mid d

    also: (a,b) = d \implies na + mb = d....this is pretty much equivalent to condition (1), we will use this a lot.

    these are the properties we will use in answering both questions. i hope you are familiar with them. now lets get to it.


    Proof:

    Assume (a,b) = d. then na + mb = d. dividing both sides by d (note d \ne 0) we get n \bigg( \frac ad \bigg) + m \bigg( \frac bd \bigg) = 1, so that 1 satisfies condition (1) above. now, to show it satisfies condition (2), assume there is some x such that x \Bigg| \frac ad and x \Bigg| \frac bd. then \frac ad = kx and \frac bd = lx. plug these into the equation that satisfies condition (1), we find that (nk)x + (ml)x = (nk + ml)x = 1 \implies x \mid 1. so that 1 satisfies condition (2), and we have \bigg( \frac ad, \frac bd \bigg) = 1 ~ \blacksquare

    2) If a|(b+c) and (b,c)=1, prove that (a,b) = 1 = (a,c)

    Suppose d|a and d|b

    a=du for some u in Z
    b=dv for some v in Z

    a|(b+c)
    b+c=aw
    c=aw-b
    c=duw-dv
    c=d(uw-v)
    d|c

    Now, how do I say that (a,b) = 1 = (a,c) ?

    Thanks for any help.
    we will use the same plan of attack on this guy. we need to verify the two conditions for 1 in regards to both (a,b) and (a,c).


    Proof:

    Assume a \mid (b + c) and (b,c) = 1. then we have:

    b + c = ak...................(eq 1)
    nb + mc = 1................(eq 2)

    From (eq 1), b = ak - c ..............(eq 3), and c = ak - b .................(eq 4).

    plugging in (eq 3) into (eq 2) and simplifying, we get: (nk)a + (m - n)c = 1, so that 1 satisfies condition (1) in regards to (a,c)

    plugging in (eq 4) into (eq 2) and simplifying, we get: (mk)a + (n - m)b = 1, so that 1 satisfies condition (1) in regards to (a,b)

    now, proving condition (2) for both of these is pretty much identical to the way i did it in the last question. i leave it to you. \blacksquare
    Last edited by Jhevon; July 7th 2008 at 10:04 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    #2
    Let d_{1} = (a,b) \geq 1 which implies d_{1} | b Through your reasoning, we see that d_{1} | c. ( d_{1} is a common divisor of b and c)

    Similarly, if we let d_{2} = (a, c) \geq 1 (implying d_{2} | c), we see that d_{2} | b. ( d_{2} is also a common divisor of b and c)

    However, (b,c) = 1 \: \: \Rightarrow d_{1} = d_{2} =  1.

    Edit: Ah beaten by Jhevon
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Mar 2008
    Posts
    99
    Woo, thanks. I was having problems incorporating the definitions
    Follow Math Help Forum on Facebook and Google+

  6. #6
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by o_O View Post
    #2
    Let d_{1} = (a,b) \geq 1 which implies d_{1} | b Through your reasoning, we see that d_{1} | c. ( d_{1} is a common divisor of b and c)

    Similarly, if we let d_{2} = (a, c) \geq 1 (implying d_{2} | c), we see that d_{2} | b. ( d_{2} is also a common divisor of b and c)

    However, (b,c) = 1 \: \: \Rightarrow d_{1} = d_{2} =  1.

    Edit: Ah beaten by Jhevon
    did you change something? i notice you deleted the your last post. it seems as if it was identical to this one. anyway, i thanked you in your last post. it stays even after you delete it, so no worries. nice solutions!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by shadow_2145 View Post
    Woo, thanks. I was having problems incorporating the definitions
    ok, so i take it you are familiar with the definitions i gave then? did you see how o_O and i applied them?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Mar 2008
    Posts
    99
    Yes, I am okay for now. Thank you.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility 11
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 20th 2008, 03:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 05:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 02:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 19th 2008, 04:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 10:24 AM

Search Tags


/mathhelpforum @mathhelpforum