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$