I am trying to do the following proof by contradiction and need verification if the proof is correct:
If an integer $n$ has the form $3k+1$, then $n$ does not have the form $9l+5$
This is my proof:
Let $n$ be an integer of the form $3k+1$ where $k$ is some integer.
We want to prove that $n$ does not have the form $9l+5$ where $l$ is some integer.
Suppose, on the contrary, $n$ does have the form $9l+5$
It follows that :
$3k +1 = 9l +5$
$3k -9l = 5-1$
$3(k-3l) = 4$
$k – 3l = \frac{4}{3}$
Since $k -3l$ is an integer by the closure properties of integers $k-3l$ can't equal $\frac{4}{3}$, which is a rational number. Therefore the assumption that $n$ does have the form $9l+5$ is false and the original statement holds.
I am new to proofs. Is this proof correct? Is it stylistically correct as well?
Best Answer
Yes, this works as a proof of it. Nicely done!
I would use that only $9l, 9l+3$ and $9l+6$ are multiples of $3$ for $l\in\Bbb Z$, so only $9l+1, 9l+4, 9l+7$ are of the form $3k+1$.