Results 1 to 8 of 8

Thread: [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
    $\displaystyle gcd(x, yz) > 1$ $\displaystyle \Rightarrow \exists$ a prime $\displaystyle p$ such that $\displaystyle p|x$ and $\displaystyle p |yz$

    $\displaystyle \Rightarrow p |y$ or $\displaystyle p| z$

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

    Contradiction.

    $\displaystyle \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

    $\displaystyle 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

    $\displaystyle 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,410
    Thanks
    1
    One important fact:
    • If $\displaystyle (a,b) = k$ and $\displaystyle c \mid a $ and $\displaystyle c \mid b$, then $\displaystyle c \mid k \qquad {\color{red}\star}$


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

    ___________

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

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

    Multiply both sides by $\displaystyle z$: $\displaystyle mxz + nyz = z$

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

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

    But $\displaystyle (x,z) = 1$. Can you conclude?
    Last edited by o_O; Feb 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
    Thanks
    1

    Divisors and multiples

    Quote Originally Posted by o_O View Post
    • If $\displaystyle (a,b) = k$ and $\displaystyle c \mid a $ and $\displaystyle c \mid b$, then $\displaystyle 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,410
    Thanks
    1
    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: Feb 27th 2010, 10:07 PM
  2. [SOLVED] Please help with proof
    Posted in the Calculus Forum
    Replies: 6
    Last Post: Feb 2nd 2010, 11:11 AM
  3. [SOLVED] set proof help
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Jul 18th 2009, 08:48 AM
  4. [SOLVED] Proof GCD and LCM
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Mar 7th 2009, 09:45 AM
  5. [SOLVED] proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Feb 10th 2009, 05:04 PM

Search Tags


/mathhelpforum @mathhelpforum