Results 1 to 2 of 2

Math Help - GCD proofs

  1. #1
    Member Maccaman's Avatar
    Joined
    Sep 2008
    Posts
    85

    GCD proofs

    Hi There,
    I really don't like Number theory, and i'm terrible with it. Can someone please show me how to prove the following?
     gcd(ac,bd) >= gcd(a,b) * gcd(c,d) for all a,b,c,d which are natural numbers.

    Also, Is  gcd(ac,bd) = gcd(a,b) * gcd(c,d) for all a,b,c,d which are natural numbers? Why?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    GCD

    Hello Maccaman
    Quote Originally Posted by Maccaman View Post
    Hi There,
    I really don't like Number theory, and i'm terrible with it. Can someone please show me how to prove the following?
     gcd(ac,bd) >= gcd(a,b) * gcd(c,d) for all a,b,c,d which are natural numbers.
    Let \gcd(a,b) = p, \gcd(c,d) = q.

    Then \exists\, s,t,u,v \in \mathbb{N},a = ps, b=pt, c = qu, d=qv

     \Rightarrow ac = pqsu, bd=pqtv

     \Rightarrow pq is a common factor of ac and bd

     \Rightarrow \gcd(ac, bd) \ge pq = \gcd(a,b)\cdot\gcd(c,d)

    Also, Is  gcd(ac,bd) = gcd(a,b) * gcd(c,d) for all a,b,c,d which are natural numbers? Why?
    No; whenever (for p, q, s,t,u,v defined as above) \gcd(s, v) > 1 or \gcd(t,u) > 1, \gcd(ac, bd) > pq.

    E.g. a = 4, b = 6, c = 5, d = 10 \Rightarrow \gcd(a,b) = 2, \gcd(c,d) = 5, but \gcd(ac,bd) = \gcd(20,60) = 20 \ne 2\times 5

    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proofs
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 2nd 2010, 03:54 AM
  2. lim sup and lim inf proofs
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: February 24th 2010, 07:02 PM
  3. More Proofs
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 13th 2008, 07:05 PM
  4. Proofs
    Posted in the Calculus Forum
    Replies: 1
    Last Post: February 3rd 2008, 04:23 AM
  5. Replies: 3
    Last Post: October 6th 2007, 02:01 PM

Search Tags


/mathhelpforum @mathhelpforum