Thread: 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 , and are relatively prime.

Proof. If , , and and are relatively prime, then . Since for some integers and , this relation can be written in terms of as . Therefore . This corresponds to a relation of the form . Because 3 and 4 are relatively prime, we can choose and so that , and therefore, the term must be zero for those same choices. If and , then . Thus, and will be relatively prime for any choice of .

Originally Posted by Haversine

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 , and are relatively prime.

Proof. If , , and and are relatively prime, then . Since for some integers and , this relation can be written in terms of as . Therefore . This corresponds to a relation of the form . Because 3 and 4 are relatively prime, we can choose and so that , and therefore, the term must be zero for those same choices. If and , then . Thus, and will be relatively prime for any choice of .

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.

Originally Posted by aman_cc

But for every (s,t) it might not work.

Neither will every (s,t) work for . The theorem runs like this -- the greatest common denominator will be the lowest possible positive integer for some linear combination . 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.

Originally Posted by Haversine

Neither will every (s,t) work for . The theorem runs like this -- the greatest common denominator will be the lowest possible positive integer for some linear combination . 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."

Originally Posted by aman_cc

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?

Originally Posted by Haversine

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)