Results 1 to 2 of 2

Math Help - a gcd proof

  1. #1
    Junior Member
    Joined
    Apr 2008
    Posts
    30

    a gcd proof

    I would just like some feedback on the work I have done for the following proof.

    Prove that if gcd(a,b)=1, then gcd(a+b, ab)=1.

    Proof: Let gcd(a,b) = 1. From an earlier exercise it is known that for any positive integer n and any integer a, gcd(a, a+n) divides n. Let d = gcd(a, a+n). This implies that d|a, and thus a = dx for some integer x, and also that d|(a+n), and thus a+n = dy for some integer y. So n = dy - a => n = dy - dx => n = d(y-x) => d|n. Since gcd(a,b)=1, let b=n. This implies d = gcd(a, a+b) but d|b since gcd(a,b)=1, so d=1. Let a=n. Then d=gcd(b,b+a) which implies d|b and d|(a+b), but d|a since gcd(a,b)=1, so d=1. Now, 1=ax+(a+b)y and 1=bx+(a+b)y so (ax+(a+b)y)*(bx+(a+b)y)=1. {expand and simplify} (a+b)(an integer)+(ab)(an integer) = 1. Therefore by theorem 2.4{a and b are relatively prime iff there exist integers x andy such that 1=ax+by}, gcd(ab, a+b)=1.

    Any constructive criticism would be appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by GoldendoodleMom View Post
    I would just like some feedback on the work I have done for the following proof.

    Prove that if gcd(a,b)=1, then gcd(a+b, ab)=1.

    Proof: Let gcd(a,b) = 1. From an earlier exercise it is known that for any positive integer n and any integer a, gcd(a, a+n) divides n. Let d = gcd(a, a+n). This implies that d|a, and thus a = dx for some integer x, and also that d|(a+n), and thus a+n = dy for some integer y. So n = dy - a => n = dy - dx => n = d(y-x) => d|n. Since gcd(a,b)=1, let b=n. This implies d = gcd(a, a+b) but d|b since gcd(a,b)=1, so d=1. Let a=n. Then d=gcd(b,b+a) which implies d|b and d|(a+b), but d|a since gcd(a,b)=1, so d=1. Now, 1=ax+(a+b)y and 1=bx+(a+b)y so (ax+(a+b)y)*(bx+(a+b)y)=1. {expand and simplify} (a+b)(an integer)+(ab)(an integer) = 1. Therefore by theorem 2.4{a and b are relatively prime iff there exist integers x andy such that 1=ax+by}, gcd(ab, a+b)=1.

    Any constructive criticism would be appreciated!
    It works but your proof does not look nice.
    Here is what I would do.

    First, (a,a+b)=1 to see this let d=(a,a+b)\implies d|a\text{ and }d|b \implies d=1 since (a,b)=1. Second, (b,a+b)=1 by similar reasoning. Therefore, ax_1 + (a+b)y_1 = 1 \text{ and }bx_2 + (a+b)y_2 = 1 for some x_1,x_2,y_1,y_2\in \mathbb{Z}. (This is another problem, how do you know the x's and y's you choose in your proof are the same! They may be different). And by multiplying them we see abN + (a+b)M = 1 for some intergers N,M. Thus, (ab,a+b)=1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: October 19th 2010, 11:50 AM
  2. Replies: 0
    Last Post: June 29th 2010, 09:48 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 11:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 05:07 PM

Search Tags


/mathhelpforum @mathhelpforum