Results 1 to 8 of 8

Math Help - [SOLVED] gcd proof 1

  1. #1
    Junior Member maths900's Avatar
    Joined
    Jan 2009
    Posts
    35

    [SOLVED] gcd proof 1

    Show that if g.c.d.(x,y) = g.c.d.(x,z) = 1 then g.c.d.(x,yz) = 1
    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 maths900
    Quote Originally Posted by maths900 View Post
    Show that if g.c.d.(x,y) = g.c.d.(x,z) = 1 then g.c.d.(x,yz) = 1
    gcd(x, yz) > 1 \Rightarrow \exists a prime p such that p|x and p |yz

    \Rightarrow p |y or p| z

    \Rightarrow gcd(x, y) = p or gcd(x,z) = p

    Contradiction.

    \Rightarrow gcd(x, yz) = 1

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member maths900's Avatar
    Joined
    Jan 2009
    Posts
    35
    Thanks. Is there another way to proof this-without having a contradiction or or something?
    Follow Math Help Forum on Facebook and Google+

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

    GCD

    Hello maths900
    Quote Originally Posted by maths900 View Post
    Thanks. Is there another way to proof this-without having a contradiction or or something?
    Why should you want to? This is a standard mathematical technique.

    If you want to try to prove it directly, you could perhaps start by saying

    gcd(x, y) = 1 \Rightarrow \exists m,n \in \mathbb{Z}, mx + ny = 1

    Grandad
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member maths900's Avatar
    Joined
    Jan 2009
    Posts
    35
    Quote Originally Posted by Grandad View Post
    Hello maths900Why should you want to? This is a standard mathematical technique.

    If you want to try to prove it directly, you could perhaps start by saying

    gcd(x, y) = 1 \Rightarrow \exists m,n \in \mathbb{Z}, mx + ny = 1

    Grandad
    Yes that is the way i had started it but i couldnt end the proof.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    One important fact:
    • If (a,b) = k and c \mid a and c \mid b, then c \mid k \qquad {\color{red}\star}


    Basically, any common divisor of two numbers will divide the gcd of those two numbers.

    ___________

    Let d = (x,yz) \geq 1.

    (x,y) = 1 \ \Leftrightarrow \ mx + ny = 1

    Multiply both sides by z: mxz + nyz = z

    Since d \mid x(mz) and d \mid yz(n), then d \mid z. (Why?)

    But this means  d \mid x and  d\mid z which implies d \mid (x,z) because of {\color{red}\star}.

    But (x,z) = 1. Can you conclude?
    Last edited by o_O; February 17th 2009 at 01:29 PM. Reason: Minor details
    Follow Math Help Forum on Facebook and Google+

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

    Divisors and multiples

    Quote Originally Posted by o_O View Post
    • If (a,b) = k and c \mid a and c \mid b, then c \mid k \qquad {\color{red}\star}


    Basically, any common
    multiple of two numbers will divide the gcd of those two numbers.
    The proof is fine, but I think you mean divisor here.

    Grandad

    Follow Math Help Forum on Facebook and Google+

  8. #8
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    Whoops! Yes, that's what I meant.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 11:07 PM
  2. [SOLVED] Please help with proof
    Posted in the Calculus Forum
    Replies: 6
    Last Post: February 2nd 2010, 12:11 PM
  3. [SOLVED] set proof help
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: July 18th 2009, 09:48 AM
  4. [SOLVED] Proof GCD and LCM
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 7th 2009, 10:45 AM
  5. [SOLVED] proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: February 10th 2009, 06:04 PM

Search Tags


/mathhelpforum @mathhelpforum