Thread: Proof Improvement: a series of relatively prime pairs

1. 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$

2. 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 $\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.

3. Originally Posted by aman_cc
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.

4. Originally Posted by Haversine
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."

5. 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?

6. 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)