Results 1 to 4 of 4

Math Help - GCD questions

  1. #1
    Newbie
    Joined
    Sep 2008
    Posts
    6

    Question GCD questions

    1.Let a be an integer and p be a positive integer. Prove that if p divides a, then
    GCD(a,p)=p.


    2.Show that if GCD(a, c)=1 and c divides ab, then c divides b.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    #1: Since p \mid a, we can say that a = kp for some k.

    So we're trying to find d = (p, kp).

    Since d \mid p and p is prime, d = 1 or  d = p... Can you finish off?

    #2:
    (a,c) =1 \ \Rightarrow \ ax + cy = 1 \ \iff \ abx + cby = b. Can you conclude?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by o_O View Post
    #1: Since p \mid a, we can say that a = kp for some k.

    So we're trying to find d = (p, kp).

    Since d \mid p and p is prime, d = 1 or  d = p... Can you finish off?
    Huh.. It is not said that p is a prime integer..

    __________________________________________________
    Let d=gcd(a,p). We can say, in particular, that d divides p.
    Since p divides both p (obvious) and a (because a is a multiple of p), we can say that p divides the gcd of a and p, that is d.

    d | p and p | d
    Hence p=d.

    #2:
    (a,c) =1 \ \Rightarrow \ ax + cy = 1 \ \iff \ abx + cby = b. Can you conclude?
    Note that the first \Rightarrow can be an equivalence
    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
    Ah whoops, too many prime p's today xD
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. More log questions
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 31st 2010, 05:58 PM
  2. Please someone help me with just 2 questions?
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 4th 2009, 05:55 AM
  3. Some Questions !
    Posted in the Geometry Forum
    Replies: 1
    Last Post: May 3rd 2009, 04:09 AM
  4. Replies: 4
    Last Post: July 19th 2008, 08:18 PM
  5. Replies: 3
    Last Post: August 1st 2005, 02:53 AM

Search Tags


/mathhelpforum @mathhelpforum