Results 1 to 2 of 2

Math Help - Greatest common divisor proofs

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    8

    Red face Greatest common divisor proofs

    Here are some GCD questions I am struggling with:

    1. Prove that, for a,n positive integers:
    (a) n is divisible by gcd(a,a+n). (hint use the division identity M=aq+r)
    (b) Hence show that GCD(a,a+1)=1

    2. Show that for a,b gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,-b)

    3. prove that, for a,b,c,x, y integers tha c=ax+by if and only if gcd(a,b) divides c

    4. Prove that for a,b,x,y integers if ax+by=gcd(a,b), then x and y are relatively prime.

    5. Prove that the product of any three consecutive integers is divisible by 6.

    Any help much appreciated.

    cheers
    Cabouli
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Cabouli View Post
    :
    1. Prove that, for a,n positive integers:
    (a) n is divisible by gcd(a,a+n). (hint use the division identity M=aq+r)
    (b) Hence show that GCD(a,a+1)=1
    Let d=(a,a+n) it means d|a,d|(a+n) so d|((a+n)-a)\implies d|n.
    2. Show that for a,b gcd(a,b)=gcd(a,-b)=gcd(-a,b)=gcd(-a,-b)
    These are straight forward ( a,b\not = 0). If d = (a,b) \text{ and }d' = (a,-b) then d|a,d|b\implies d|a,d|(-b) so d'|d. However, d'|a,d'|(-b)\implies d'|a,d'|b so d|d' which means d=d'. Likewise for all the other ones.

    3. prove that, for a,b,c,x, y integers tha c=ax+by if and only if gcd(a,b) divides c
    If ax+by=c let d=(a,b) then LHS is divisible by d so d|c. Now for conserve. We can write ax+by=d since d|c it means de=c and so a(xe) + b(ye) = de = c.

    4. Prove that for a,b,x,y integers if ax+by=gcd(a,b), then x and y are relatively prime.
    You can write (a/d)x+(b/d)y=1, now it is clear that (x,y)=1.

    5. Prove that the product of any three consecutive integers is divisible by 6.
    We want to prove 6|x(x+1)(x+2). Notice that (2,3)=1 and 2\cdot 3 = 6. Thus, it is sufficient to prove that 2|x(x+1)(x+2)\text{ and }3|x(x+1)(x+2). It is easy to see why that is true.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 06:45 AM
  2. Greatest common divisor
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: April 18th 2010, 04:16 PM
  3. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 17th 2009, 08:16 PM
  4. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 4th 2008, 02:08 AM
  5. Greatest common divisor-proofs?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 31st 2008, 07:27 PM

Search Tags


/mathhelpforum @mathhelpforum