Results 1 to 7 of 7
Like Tree2Thanks
  • 1 Post By SlipEternal
  • 1 Post By SlipEternal

Math Help - GCD proofs

  1. #1
    Member
    Joined
    Nov 2012
    From
    israel
    Posts
    164
    Thanks
    2

    GCD proofs

    I need to prove the following:

    1. Let a,b,d\in\mathbb{Z}

    If d|a and d|b, then:

    d=gcd(a,b) \Leftrightarrow (\frac{a}{d},\frac{b}{d})=1

    Here I was able to prove only one direction:

    d=gcd(a,b) \Rightarrow (\frac{a}{d},\frac{b}{d})=1

    Since d=gcd(a,b), there exist s,t\in\mathbb{Z} such that d=sa+tb.
    I divide the whole thing by d and get:
    s\frac{a}{d}+t\frac{b}{d}=1

    Now since gcd(x,y)=\min_{u,v\in\mathbb{Z}}}\left \{ xu+yv\in\mathbb{N}} \right \}, and 1 is the minimal natural number, then gcd(\frac{a}{d},\frac{b}{d})=1.

    2. gcd(ab,ac)=a\cdot gcd(b,c)

    Here I don't have a clue what to do.

    any help would be greatly appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,857
    Thanks
    720

    Re: GCD proofs

    For 2, use what you proved in part 1. For part 1, it looks like you got the answer already. Just do the proof in the opposite direction.

    Assume \left(\dfrac{a}{d},\dfrac{b}{d}\right) = 1. Then there exist integers s,t such that s\dfrac{a}{d} + t\dfrac{b}{d} = 1. Then multiply both sides by d. Now, (a,b) \le d and since d|a and d|b, (a,b) \ge d.
    Last edited by SlipEternal; October 23rd 2013 at 03:42 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2012
    From
    israel
    Posts
    164
    Thanks
    2

    Re: GCD proofs

    Thanks, SlipEternal.

    Quote Originally Posted by SlipEternal View Post
    Now, (a,b) \le d and since d|a and d|b, (a,b) \ge d.
    I get why d|a and d|b \Rightarrow (a,b) \ge d, but why is (a,b) \le d?

    edit*
    OK, I couldn't think of a way to use 1 to prove 2, but I came up with something else for 2...:

    gcd(ab,ac)=\min_{u,v\in\mathbb{Z}}\left \{ u(ab)+v(ac)\in\mathbb{N} \right \}=\min_{u,v\in\mathbb{Z}}\left \{ a(ub+vc)\in\mathbb{N} \right \}=
    a\cdot\min_{u,v\in\mathbb{Z}}\left \{ ub+vc\in\mathbb{N} \right \}=a\cdot\gcd(b,c)

    Hope it's valid...
    Nonetheless, if you have some other way, I would love to see.
    Last edited by Stormey; October 24th 2013 at 01:37 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,857
    Thanks
    720

    Re: GCD proofs

    Quote Originally Posted by Stormey View Post
    I get why d|a and d|b \Rightarrow (a,b) \ge d, but why is (a,b) \le d?
    Because after you multiply out by d, you get sa+tb = d, and (a,b) = \min_{u,v \in \mathbb{Z}} \{ua+vb \in \mathbb{N}\} \le sa+tb = d.

    Quote Originally Posted by Stormey View Post
    edit*
    OK, I couldn't think of a way to use 1 to prove 2, but I came up with something else for 2...:

    gcd(ab,ac)=\min_{u,v\in\mathbb{Z}}\left \{ u(ab)+v(ac)\in\mathbb{N} \right \}=\min_{u,v\in\mathbb{Z}}\left \{ a(ub+vc)\in\mathbb{N} \right \}=
    a\cdot\min_{u,v\in\mathbb{Z}}\left \{ ub+vc\in\mathbb{N} \right \}=a\cdot\gcd(b,c)

    Hope it's valid...
    Nonetheless, if you have some other way, I would love to see.
    You would need to explain in words why you are able to factor a number from a set, but yes. That proof would work. To use part (1) to prove part (2):

    \begin{align*}& \gcd(b,c) = \gcd(b,c) \\ \Leftrightarrow & \gcd\left(\dfrac{b}{\gcd(b,c)},\dfrac{c}{\gcd(b,c)  }\right) = 1 \\ \Leftrightarrow & \gcd\left(\dfrac{ab}{a\cdot \gcd(b,c)},\dfrac{ac}{a\cdot \gcd(b,c)}\right) = 1 \\ \Leftrightarrow & \gcd(ab,ac) = a\cdot \gcd(b,c)\end{align*}.

    I start with an obviously true statement. By part (1), that is true if and only if the second expression is true. Multiplying top and bottom of each fraction by a gives the third, and to get to the fourth expression, we just need to check that a\cdot \gcd(b,c) | ab and a\cdot \gcd(b,c) | ac. Those are obviously true, so again by part (1), the third biconditional implies the fourth expression. Since the first expression is true, the last expression is true.
    Thanks from Stormey
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Nov 2012
    From
    israel
    Posts
    164
    Thanks
    2

    Re: GCD proofs

    Great. once again, thanks!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Nov 2012
    From
    israel
    Posts
    164
    Thanks
    2

    Re: GCD proofs

    And just a note: I'm learning a lot from your posts.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,857
    Thanks
    720

    Re: GCD proofs

    Oh, and I didn't state it, but there are some cases that you might want to check. For part (1), a=b=0 is a weird case for \gcd(a,b), so depending on your definitions, you may need to check it separately. Some mathematicians say \gcd(0,0) is undefined. Some say it is zero (useful if you want to look at the natural numbers as a distributive lattice with \text{lcm} and \gcd as join and meet respectively). If using the extended integers, it would be \infty. So, if your book defines it, you need to check it. Since \{s\cdot 0 + t\cdot 0 \in \mathbb{N} \mid s,t \in \mathbb{Z}\} = \emptyset if 0\notin \mathbb{N}, it may be undefined in your book. If it is defined as zero (or if your book uses the convention that 0 \in \mathbb{N}), then the check is easy. Zero does not divide zero, so the statement is automatically true.

    For part (2), again, if your book defined \gcd(0,0)=0, you need to check the case when a=0 or when b=c=0 separately. Note for (2), it is false if a<0. Writing it \gcd(ab,ac) = |a|\cdot \gcd(b,c) would make it true for a<0, as well. And if \gcd(0,0) = 0, it is easy to show that \gcd(0b,0c) = \gcd(0,0) = 0 = 0\cdot \gcd(b,c).
    Last edited by SlipEternal; October 24th 2013 at 08:28 AM.
    Thanks from Stormey
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Need help with these proofs
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 23rd 2010, 03:16 AM
  2. Help with some proofs
    Posted in the Calculus Forum
    Replies: 1
    Last Post: May 18th 2009, 12:39 PM
  3. Last two proofs
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 1st 2008, 11:14 AM
  4. Proofs.
    Posted in the Algebra Forum
    Replies: 10
    Last Post: April 13th 2008, 06:22 AM
  5. Replies: 3
    Last Post: October 6th 2007, 02:01 PM

Search Tags


/mathhelpforum @mathhelpforum