Results 1 to 8 of 8

Thread: Divisibility

  1. #1
    Member
    Joined
    Mar 2008
    Posts
    99

    Divisibility

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

    Not quite sure how to do that one..

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

    Suppose $\displaystyle d|a$ and $\displaystyle d|b$

    $\displaystyle a=du$ for some u in Z
    $\displaystyle b=dv$ for some v in Z

    $\displaystyle a|(b+c)$
    $\displaystyle b+c=aw$
    $\displaystyle c=aw-b$
    $\displaystyle c=duw-dv$
    $\displaystyle c=d(uw-v)$
    $\displaystyle 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,410
    Thanks
    1
    #1
    Let $\displaystyle 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 $\displaystyle r, s$ such that $\displaystyle xr = \frac{a}{d} \: \: \iff \: \: dxr = a$ and $\displaystyle xs = \frac{b}{d} \: \: \iff \: \: dxs = b$.

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

    However, recall that $\displaystyle x \geq 1$. So, $\displaystyle 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 $\displaystyle (a,b) = d$, prove that $\displaystyle (\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: $\displaystyle (a,b) = d$ means that:
    (1) $\displaystyle d \mid a$ and $\displaystyle d \mid b$
    (2) If there is $\displaystyle x$ such that $\displaystyle x \mid a$ and $\displaystyle x \mid b$, then $\displaystyle x \mid d$

    also: $\displaystyle (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 $\displaystyle (a,b) = d$. then $\displaystyle na + mb = d$. dividing both sides by $\displaystyle d$ (note $\displaystyle d \ne 0$) we get $\displaystyle 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 $\displaystyle x$ such that $\displaystyle x \Bigg| \frac ad$ and $\displaystyle x \Bigg| \frac bd$. then $\displaystyle \frac ad = kx$ and $\displaystyle \frac bd = lx$. plug these into the equation that satisfies condition (1), we find that $\displaystyle (nk)x + (ml)x = (nk + ml)x = 1 \implies x \mid 1$. so that 1 satisfies condition (2), and we have $\displaystyle \bigg( \frac ad, \frac bd \bigg) = 1$ $\displaystyle ~ \blacksquare$

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

    Suppose $\displaystyle d|a$ and $\displaystyle d|b$

    $\displaystyle a=du$ for some u in Z
    $\displaystyle b=dv$ for some v in Z

    $\displaystyle a|(b+c)$
    $\displaystyle b+c=aw$
    $\displaystyle c=aw-b$
    $\displaystyle c=duw-dv$
    $\displaystyle c=d(uw-v)$
    $\displaystyle 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 $\displaystyle (a,b)$ and $\displaystyle (a,c)$.


    Proof:

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

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

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

    plugging in (eq 3) into (eq 2) and simplifying, we get: $\displaystyle (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: $\displaystyle (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. $\displaystyle \blacksquare$
    Last edited by Jhevon; Jul 7th 2008 at 09: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,410
    Thanks
    1
    #2
    Let $\displaystyle d_{1} = (a,b) \geq 1$ which implies $\displaystyle d_{1} | b$ Through your reasoning, we see that $\displaystyle d_{1} | c$. ($\displaystyle d_{1}$ is a common divisor of b and c)

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

    However, $\displaystyle (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 $\displaystyle d_{1} = (a,b) \geq 1$ which implies $\displaystyle d_{1} | b$ Through your reasoning, we see that $\displaystyle d_{1} | c$. ($\displaystyle d_{1}$ is a common divisor of b and c)

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

    However, $\displaystyle (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: Dec 20th 2008, 02:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 19th 2008, 04:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 19th 2008, 01:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Dec 19th 2008, 03:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Dec 14th 2008, 09:24 AM

Search Tags


/mathhelpforum @mathhelpforum