# 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 $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$

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

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

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

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)