Results 1 to 2 of 2

Thread: 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, $\displaystyle (a,a+b)=1$ to see this let $\displaystyle d=(a,a+b)\implies d|a\text{ and }d|b \implies d=1$ since $\displaystyle (a,b)=1$. Second, $\displaystyle (b,a+b)=1$ by similar reasoning. Therefore, $\displaystyle ax_1 + (a+b)y_1 = 1 \text{ and }bx_2 + (a+b)y_2 = 1$ for some $\displaystyle 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 $\displaystyle abN + (a+b)M = 1$ for some intergers $\displaystyle N,M$. Thus, $\displaystyle (ab,a+b)=1$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: Oct 19th 2010, 10:50 AM
  2. Replies: 0
    Last Post: Jun 29th 2010, 08:48 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jun 8th 2008, 01: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: Apr 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum