Results 1 to 4 of 4

Math Help - Greatest common divisor

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    8

    Exclamation Greatest common divisor

    Some help with these would be appreciated

    1. Prove that if gcd(a,b)=1 and gcd(a,c)=1 then gcd(a,bc)=1

    2. Prove that if a and b are relatively prime and c|a, then c and b are relatively prime

    3. Prove that if a is odd, then 24|a(a^2-1)

    4. Prove that if a and b are relatively prime, then gcd(a+b,a-b)=1 or 2

    5. Prove that, if a and b are relatively prime, then so are a^n and B^n, where a and b and n are positive integers

    6. Prove that lcm(a,b)xgcd(a,b)=ab
    Follow Math Help Forum on Facebook and Google+

  2. #2
    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 Cabouli View Post
    Some help with these would be appreciated

    1. Prove that if gcd(a,b)=1 and gcd(a,c)=1 then gcd(a,bc)=1

    2. Prove that if a and b are relatively prime and c|a, then c and b are relatively prime

    3. Prove that if a is odd, then 24|a(a^2-1)

    4. Prove that if a and b are relatively prime, then gcd(a+b,a-b)=1 or 2

    5. Prove that, if a and b are relatively prime, then so are a^n and B^n, where a and b and n are positive integers

    6. Prove that lcm(a,b)xgcd(a,b)=ab
    please show what you have tried or where you are getting stuck. this seems like you just want someone to do your homework for you
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    Posts
    8

    Unhappy Here are my attempts

    1. Prove that if gcd(a,b)=1 and gcd(a,c)=1 then gcd(a,bc)=1

    gcd(a,b)=1 then ax+by=1
    gcd(a,c)=1 then ax+cy=1
    let gcd(a,bc)=d then ax+bcy=d

    I cannot see how to proceed

    2. Prove that if a and b are relatively prime and c|a, then c and b are relatively prime

    gcd(a,b)=1 ax+by=1
    c|a therefore a=cm ,m an integer
    therefore cmx+by=1
    so c(mx)+by=1
    therefore gcd(c,b)=1

    Does this work?

    3. Prove that if a is odd, then 24|a(a^2-1)

    sufficient to show RHS is divisible by 3, 2 and 4
    let a=2k+1 since it is odd
    a(a^2-1)=2k(2k+1)(2k+2)
    this is clearly divisible by 2, 3 and 4

    Is that idea sufficient?

    4. Prove that if a and b are relatively prime, then gcd(a+b,a-b)=1 or 2

    gcd(a,b)=1 and ax+by=1
    let gcd(a+b,a-b)=d so (a+b)x+(a-b)y=d so d|(a+b) and d|(a-b)

    I can see I need d|2a and d|2b but can't see how to get there

    5. Prove that, if a and b are relatively prime, then so are a^n and B^n, where a and b and n are positive integers

    gcd(a,b)=1 and ax+by=1

    let gcd(a^n,b^n)=d so a^nx+b^ny=d and a^n=md b^n=pd

    again don't know where to proceed

    6. Prove that lcm(a,b)xgcd(a,b)=ab

    If a=mnp.. m,n,p,... are prime and b=efg.. e,f,g,... are prime
    then lcm(a,b)=mnp...efg... assuming none of mnp... and efg... are common
    If any are common they will not be in the lcm(a,b)
    gcm(a,b)= common elements from mnp.... and efg.... if none then gcm(a,b)=1
    aXb=mnp...efg...
    gcd(a,b)Xlcm(a,b)=mnp...efg... from above

    I think I have the right idea but a messy approach to showing it.

    Please any help would be appreciated.

    Also I am too old to still be doing homework but I do voluntary tutoring for disadvantaged kids. This is the first time I have come across a student needing help with number theory.

    Cheers
    Cabouli
    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,407
    Quote Originally Posted by Cabouli View Post
    1. Prove that if gcd(a,b)=1 and gcd(a,c)=1 then gcd(a,bc)=1

    gcd(a,b)=1 then ax+by=1
    gcd(a,c)=1 then ax+cy=1
    let gcd(a,bc)=d then ax+bcy=d

    I cannot see how to proceed
    So we have: \gcd(a,b) = 1 \ \Rightarrow \ ax + by = 1

    Multiply both sides by c to get: acx + bcy = c

    Now, since \gcd(a,b) \mid acx and \gcd(a,b) \mid bcy, then \gcd(a,b) \mid c (Why?).

    Thus, \gcd (a,b) is a divisor of both a and c. What can you conclude?


    2. Prove that if a and b are relatively prime and c|a, then c and b are relatively prime

    gcd(a,b)=1 ax+by=1
    c|a therefore a=cm ,m an integer
    therefore cmx+by=1
    so c(mx)+by=1
    therefore gcd(c,b)=1

    Does this work?
    Sure does.


    3. Prove that if a is odd, then 24|a(a^2-1)

    sufficient to show RHS is divisible by 3, 2 and 4
    let a=2k+1 since it is odd
    a(a^2-1)=2k(2k+1)(2k+2)
    this is clearly divisible by 2, 3 and 4

    Is that idea sufficient?
    Although you would probably want to say more as to why it is 'clear' that this is the case.

    4. Prove that if a and b are relatively prime, then gcd(a+b,a-b)=1 or 2

    gcd(a,b)=1 and ax+by=1
    let gcd(a+b,a-b)=d so (a+b)x+(a-b)y=d so d|(a+b) and d|(a-b)

    I can see I need d|2a and d|2b but can't see how to get there
    Suppose p \mid (a+b) and p \mid (a-b) where p is prime. This means that: p \mid (a+b + (a-b) \Leftrightarrow p \mid 2a. Similarly, we get p \mid 2b.

    Can you finish off?

    5. Prove that, if a and b are relatively prime, then so are a^n and B^n, where a and b and n are positive integers

    gcd(a,b)=1 and ax+by=1

    let gcd(a^n,b^n)=d so a^nx+b^ny=d and a^n=md b^n=pd

    again don't know where to proceed

    Suppose \gcd (a^n, b^n) > 1. This means that there exists a prime p such that p \mid a^n and p \mid b^n. Can you arrive at a contradiction? (Remember, if p \mid mn, then either p \mid m or p \mid n)


    6. Prove that lcm(a,b)xgcd(a,b)=ab

    If a=mnp.. m,n,p,... are prime and b=efg.. e,f,g,... are prime
    then lcm(a,b)=mnp...efg... assuming none of mnp... and efg... are common
    If any are common they will not be in the lcm(a,b)
    gcm(a,b)= common elements from mnp.... and efg.... if none then gcm(a,b)=1
    aXb=mnp...efg...
    gcd(a,b)Xlcm(a,b)=mnp...efg... from above

    I think I have the right idea but a messy approach to showing it.
    Can't quite read what you have there but I'm guessing you're going down the prime factorization approach.

    So, let a = p_1^{e_1}p_2^{e_2}\cdots p_n^{e_n} and b  = p_1^{f_1}p_2^{f_2}\cdots p_n^{f_n} where e_j, f_j may equal to 0.

    By definition, we have: \gcd (a,b) = p_1^{\min (e_1, f_1)}p_2^{\min (e_2, f_2)}\cdots p_n^{\min (e_n, f_n)}

    and: \text{lcm} (a,b) = p_1^{\max (e_1, f_1)}p_2^{\max (e_2, f_2)}\cdots p_n^{\max (e_n, f_n)}

    Multiply them both together and it should be clear from there.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Greatest Common Divisor of (9m+8, 6m+5)
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 15th 2011, 06:43 AM
  2. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 06:45 AM
  3. Greatest Common Divisor.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 23rd 2009, 01:36 AM
  4. greatest common divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 04:24 AM
  5. greatest common divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 25th 2008, 10:36 AM

Search Tags


/mathhelpforum @mathhelpforum