Results 1 to 4 of 4

Math Help - gcd property

  1. #1
    Newbie
    Joined
    Jul 2011
    Posts
    10

    gcd property

    Suppose gcd(a, b) = 1. Prove gcd(c, b) divides gcd(ac, b).

    Attempt: Let x = gcd(c, b), y = gcd(ac, b). Then \exists r_1, r_2, s.t. b = x . r_1, b = y . r_2. Hence y = x . r_1/r_2.

    Iím stuck after this, because I canít show that r_2 divides r_1.


    Can anyone help me? Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jul 2011
    Posts
    1

    Re: gcd property

    Hi,
    try it this way:
    d_1=gcd(c,b), d_2=gcd(ac,b)
    => cx_1+by_1=d_1 and acx_2+by_2=d_2
    From gcd(a,b)=1 you get
    => ax+by=1 | *d_1
    => d_1=cx_1+by_1
    Now we have to show, that d_2|d_1:

    d_1*(ax+by=1) => ax(cx_1+by_1)+bd_1y=d_1 => ac(xx_1)+b(axy_1+d_1y)=d_1
    You know d_2=gcd(ac,b), so d_2 divides any linear combination of ac and b => d_2|d_1

    Repeat the steps for d_2 and you will get d_1|d_2 and d_2|d_1 => d_1=d_2

    Greetings
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1

    Re: gcd property

    Quote Originally Posted by jozou View Post
    Suppose gcd(a, b) = 1. Prove gcd(c, b) divides gcd(ac, b).

    Attempt: Let x = gcd(c, b), y = gcd(ac, b). Then \exists r_1, r_2, s.t. b = x . r_1, b = y . r_2. Hence y = x . r_1/r_2.

    Iím stuck after this, because I canít show that r_2 divides r_1.


    Can anyone help me? Thanks.
    hello jozou!
    the condition gcd(a,b)=1 forces gcd(c,b)=gcd(ac,b).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jul 2011
    Posts
    10

    Re: gcd property

    Thank you Trampeltier, abhishekkgp. Finally I got it~
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] another gcd property
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 25th 2011, 09:38 AM
  2. Mean Value Property Implies "Volume" Mean Value Property
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: March 16th 2011, 08:13 PM
  3. set property help
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: June 28th 2010, 04:09 AM
  4. One-To-One Property
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: September 28th 2009, 02:59 PM
  5. property
    Posted in the Calculus Forum
    Replies: 1
    Last Post: July 12th 2008, 08:32 PM

/mathhelpforum @mathhelpforum