Results 1 to 6 of 6

Math Help - 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 n, 5n + 3 and 7n + 4 are relatively prime.

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

    Proof. If a = 5n + 3, b = 7n + 4, and a and b are relatively prime, then \gcd(a,b) = 1. Since \gcd(a,b) = as + bt for some integers s and t, this relation can be written in terms of n as (5n + 3)s + (7n + 4)t = 1. Therefore (5s + 7t)n + 3s + 4t = 1. This corresponds to a relation of the form n \gcd(5,7) + \gcd(3,4) = 1. Because 3 and 4 are relatively prime, we can choose s and t so that 3s + 4t = 1, and therefore, the (5s + 7t)n term must be zero for those same choices. If s = 7 and t = -5, then (5s + 7t)n + 3s + 4t = (35 - 35)n + 21 - 20 = 0n + 1 = 1. Thus, a and b will be relatively prime for any choice of n. \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 \gcd(a,b) = 1. The theorem runs like this -- the greatest common denominator will be the lowest possible positive integer for some linear combination \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 \gcd(a,b) = 1. The theorem runs like this -- the greatest common denominator will be the lowest possible positive integer for some linear combination \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: December 7th 2009, 06:54 PM
  2. Improvement on a winding machine.
    Posted in the Trigonometry Forum
    Replies: 4
    Last Post: June 16th 2009, 06:41 AM
  3. Replies: 5
    Last Post: June 14th 2007, 02:10 PM
  4. Trial & Improvement
    Posted in the Math Topics Forum
    Replies: 12
    Last Post: June 10th 2007, 10:11 AM

Search Tags


/mathhelpforum @mathhelpforum