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

    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

    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,407
    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 12: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

    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,407
    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, 10:07 PM
  2. [SOLVED] Please help with proof
    Posted in the Calculus Forum
    Replies: 6
    Last Post: February 2nd 2010, 11:11 AM
  3. [SOLVED] set proof help
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: July 18th 2009, 08:48 AM
  4. [SOLVED] Proof GCD and LCM
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 7th 2009, 09:45 AM
  5. [SOLVED] proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: February 10th 2009, 05:04 PM

Search Tags


/mathhelpforum @mathhelpforum