Results 1 to 3 of 3

Math Help - Number theory question i'm stuck on during exam revision

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    15

    Number theory question i'm stuck on during exam revision

    Let a, b, q, r be integers such that b=aq+r and a doesn't = 0. SHow that an integer c is a common divisor of b and a if and only if c is a common divisor of a and r. Explain why this means that gcd(b,a)= gcd(a,r).

    Here's the question i'm struggling with. I know that it is related to the Euclidean algorithm in some way and that i somehow need to show that c divides (a,b) and (a,r). I can also see that using ax +by = c will be helpful. I just can't seem to pull all my thoughts together so any help would be grateful.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Nov 2009
    Posts
    106
    Assume (1)\; c\mid  a and (2)\; c\mid  b. From (1) it follows that (3)\; c\mid qa, and from (3),(2) it follows that c \mid b-qa. But b-qa=r, so that c divides both r and (from (1)) a. The other direction ( c\mid r,\; c\mid a \Rightarrow c\mid b) follows in the same manner.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2010
    Posts
    15
    Thanks for the help there
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: February 25th 2011, 04:08 PM
  2. Replies: 1
    Last Post: April 26th 2010, 03:28 PM
  3. Revision related number theory question(s)
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 15th 2010, 08:57 AM
  4. vector problem - exam revision
    Posted in the Geometry Forum
    Replies: 3
    Last Post: January 6th 2010, 12:49 PM
  5. Re: More exam revision!
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: February 19th 2008, 04:40 PM

Search Tags


/mathhelpforum @mathhelpforum