Results 1 to 3 of 3

Math Help - b=aq+r then gcd(b,a)=gcd(a,r)

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    b=aq+r then gcd(b,a)=gcd(a,r)

    If b=aq+r, then the gcd(a,b)=gcd(a,r)

    Not to sure with what to do here.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2010
    Posts
    715
    Thanks
    2
    \begin{aligned} \gcd(a, b) & = ax+by \\& = ax+(aq+r)y \\& = ax+aqy+ry \\& = a(x+qy)+ry \\& = \gcd(a, r). \end{aligned}
    Last edited by TheCoffeeMachine; May 25th 2011 at 07:40 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2011
    From
    Florida
    Posts
    16

    This was not quite clear to me, so I found a way that might be easier

    * c|b notation reads c divides b
    Let (b,a) = c and (a,r) = d

    c|b and c|a, then c|b-aq
    r = b - aq, so c|r
    c (less than or equal to) d

    d|a and d|r, then d|aq + r
    b = aq + r, so d|b
    d (less than or equal to) c

    Therefore d=c
    Follow Math Help Forum on Facebook and Google+


/mathhelpforum @mathhelpforum