Results 1 to 6 of 6

Thread: Proof Improvement: a series of relatively prime pairs

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    33

    Proof Improvement: a series of relatively prime pairs

    I am relatively new to writing proofs. I'm working through Gallian's Contemporary Abstract Algebra. As a new proof writer, I occasionally feel a bit awkward . . . I get the sense I am "running in place," that is, obscuring the proof with too many steps, details, and general hem-hawing.

    Below I have given a proposition and my proof. I feel comfortable with the logic of the proof, but I look at it and think, "This could really be written better."

    However, that's where I'm drawing a blank. So I called in the experts.

    Can this proof be made "pretty"?

    Proposition: For all integers $\displaystyle n$, $\displaystyle 5n + 3$ and $\displaystyle 7n + 4$ are relatively prime.

    Proof. If $\displaystyle a = 5n + 3$, $\displaystyle b = 7n + 4$, and $\displaystyle a$ and $\displaystyle b$ are relatively prime, then $\displaystyle \gcd(a,b) = 1$. Since $\displaystyle \gcd(a,b) = as + bt$ for some integers $\displaystyle s$ and $\displaystyle t$, this relation can be written in terms of $\displaystyle n$ as $\displaystyle (5n + 3)s + (7n + 4)t = 1$. Therefore $\displaystyle (5s + 7t)n + 3s + 4t = 1$. This corresponds to a relation of the form $\displaystyle n \gcd(5,7) + \gcd(3,4) = 1$. Because 3 and 4 are relatively prime, we can choose $\displaystyle s$ and $\displaystyle t$ so that $\displaystyle 3s + 4t = 1$, and therefore, the $\displaystyle (5s + 7t)n$ term must be zero for those same choices. If $\displaystyle s = 7$ and $\displaystyle t = -5$, then $\displaystyle (5s + 7t)n + 3s + 4t = (35 - 35)n + 21 - 20 = 0n + 1 = 1$. Thus, $\displaystyle a$ and $\displaystyle b$ will be relatively prime for any choice of $\displaystyle n$. $\displaystyle \Box$
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by Haversine View Post
    I am relatively new to writing proofs. I'm working through Gallian's Contemporary Abstract Algebra. As a new proof writer, I occasionally feel a bit awkward . . . I get the sense I am "running in place," that is, obscuring the proof with too many steps, details, and general hem-hawing.

    Below I have given a proposition and my proof. I feel comfortable with the logic of the proof, but I look at it and think, "This could really be written better."

    However, that's where I'm drawing a blank. So I called in the experts.

    Can this proof be made "pretty"?

    Proposition: For all integers $\displaystyle n$, $\displaystyle 5n + 3$ and $\displaystyle 7n + 4$ are relatively prime.

    Proof. If $\displaystyle a = 5n + 3$, $\displaystyle b = 7n + 4$, and $\displaystyle a$ and $\displaystyle b$ are relatively prime, then $\displaystyle \gcd(a,b) = 1$. Since $\displaystyle \gcd(a,b) = as + bt$ for some integers $\displaystyle s$ and $\displaystyle t$, this relation can be written in terms of $\displaystyle n$ as $\displaystyle (5n + 3)s + (7n + 4)t = 1$. Therefore $\displaystyle (5s + 7t)n + 3s + 4t = 1$. This corresponds to a relation of the form $\displaystyle n \gcd(5,7) + \gcd(3,4) = 1$. Because 3 and 4 are relatively prime, we can choose $\displaystyle s$ and $\displaystyle t$ so that $\displaystyle 3s + 4t = 1$, and therefore, the $\displaystyle (5s + 7t)n$ term must be zero for those same choices. If $\displaystyle s = 7$ and $\displaystyle t = -5$, then $\displaystyle (5s + 7t)n + 3s + 4t = (35 - 35)n + 21 - 20 = 0n + 1 = 1$. Thus, $\displaystyle a$ and $\displaystyle b$ will be relatively prime for any choice of $\displaystyle n$. $\displaystyle \Box$

    Because 3 and 4 are relatively prime, we can choose and so that , and therefore, the term must be zero for those same choices.

    Not sure about the logic above - put (s,t) = (-1,1)

    EDIT:
    I was wrong. Your argument is convincing to me. But for every (s,t) it might not work.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2009
    Posts
    33
    Quote Originally Posted by aman_cc View Post
    But for every (s,t) it might not work.
    Neither will every (s,t) work for $\displaystyle \gcd(a,b) = 1$. The theorem runs like this -- the greatest common denominator will be the lowest possible positive integer for some linear combination $\displaystyle \gcd(a,b) = as + bt$. If we take a = 6 and b = 9, for example, one choice producing the lowest possible positive integer is s = -1 and t = +1. There are no choices of s and t that give lower positive integers; there are many choice that give equal or higher.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by Haversine View Post
    Neither will every (s,t) work for $\displaystyle \gcd(a,b) = 1$. The theorem runs like this -- the greatest common denominator will be the lowest possible positive integer for some linear combination $\displaystyle \gcd(a,b) = as + bt$. If we take a = 6 and b = 9, for example, one choice producing the lowest possible positive integer is s = -1 and t = +1. There are no choices of s and t that give lower positive integers; there are many choice that give equal or higher.

    Yes - Thanks. I think I misinterpreted your statement below - but I understand your proof.

    "Because 3 and 4 are relatively prime, we can choose and so that , and therefore, the term must be zero for those same choices."
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2009
    Posts
    33
    Quote Originally Posted by aman_cc View Post
    Yes - Thanks. I think I misinterpreted your statement below - but I understand your proof.
    I think that's what I'm driving at by asking this question . . . . Ideally, the logic for a proof should be clear, and difficult to misinterpret. That's a long, awkward sentence of mine . . . . definitely needs improvement . . . the question is, how?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by Haversine View Post
    I think that's what I'm driving at by asking this question . . . . Ideally, the logic for a proof should be clear, and difficult to misinterpret. That's a long, awkward sentence of mine . . . . definitely needs improvement . . . the question is, how?
    Borrowing your idea only - you may just want to say that

    For all n,

    (5n+3).7 + (7n+4).-5 = 1 => gcd((5n+3), (7n+4)) = 1

    (If that looks any prettier. It is definitely concise and complete though)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Dec 7th 2009, 05:54 PM
  2. Improvement on a winding machine.
    Posted in the Trigonometry Forum
    Replies: 4
    Last Post: Jun 16th 2009, 05:41 AM
  3. Replies: 5
    Last Post: Jun 14th 2007, 01:10 PM
  4. Trial & Improvement
    Posted in the Math Topics Forum
    Replies: 12
    Last Post: Jun 10th 2007, 09:11 AM

Search Tags


/mathhelpforum @mathhelpforum