Need Critique of Proof. Self Studying Intro to Proofs Course.

Question

I am currently self-studying an intro to proofs textbook, and I wanted to revisit a proof from earlier on to make sure I'm developing my proof-writing skill. Any critiques and tips for this proof would be greatly appreciated. Also, if anyone knows of a more simple proof, please do share. Thank you all in advance!

Theorem. For each integer $a$, if 3 does not divide $a$, then there exists integers $x$ and $y$ such that $3x+ay=1$.

Proof. We assume that $a$ is an integer. By the division algorithm theorem, there exists unique integers $q$ and $r$ such that $$a = 3q+r \text{ where } 0\leq r < 3.$$ Thus, we will prove the theorem for 3 cases. \begin{align} a = 3q \\ a = 3q+1 \\ a = 3q+2 \end{align} Case 1: If $a=3q$, then the hypothesis of the theorem is false. Thus, the theorem holds true for $a=3q$.

Case 2: For this case where $a=3q+1$, and thus $a$ is not divisible by 3, we will develop a constructive proof for the existence of $x$ and $y$. First, we will substitute $a=3q+1$ into $3x+ay=1$. Thus, we get $$3x+(3q+1)y=1. $$ Then, we use the previous equation to solve for $y$ which yields $$y = \frac{1-3x}{3q+1}.$$ We allow $x=2q+1$. Thus, $x$ is an integer because the set of integers is closed under addition and multiplication. We then substitute $x$ into the previous equation. $$y = \frac{1-3(2q+1)}{3q+1}$$ After algebraic manipulation of the previous equation, we get $$ y =-2.$$ Thus, we have proven the theorem for this case by proving the existence of $x$ and $y$ through construction.

Case 3: For this case where $a=3q+2$, and thus $a$ is not divisible by 3, we will develop a constructive proof for the existence of $x$ and $y$. First, we will substitute $a=3q+2$ into $3x+ay=1$. Thus, we get $$3x+(3q+2)y=1. $$ Then, we use the previous equation to solve for y which yields $$y = \frac{1-3x}{3q+2}.$$ We allow $x=q+1$. Thus, x is an integer because the set of integers is closed under addition. We then substitute x into the previous equation. $$y = \frac{1-3(q+1)}{3q+2}$$ After algebraic manipulation of the previous equation, we get $$ y =-1.$$ Thus, we have proven the theorem for this case by proving the existence of $x$ and $y$ through construction. Since we have proven the theorem for every case, the theorem is true. $\blacksquare$

Answer 1

Your proof is too long.

You could simply say

If $ a=3q+1$ then $1.a-3q=1=ay+3x$.

and

if $ a=3q+2 =3(q+1)-1$ then

$$3(q+1)-a=1=3x+ay.$$

other approach:

$3 $ is prime.So, If $ 3 $ does not divide the integer $ a$, it means that $ 3 $ and $ a$ are relatively prime.

then, By Bezout theorem, there exist integers $ x $ and $ y $ such that $$3x+ay=1.$$

Answer 2

Your proof is correct and clear. It is a bit wordy, but if you’re just starting, it’s better to say too much than not enough. It would be a good idea to explain how you came up with $x=2q+1$ and $x=q+1$, especially if you used some kind of systematic approach.

For instance, in Case 2 you might have decided to try letting $x=aq+b$, with $a$ and $b$ integer constants yet to be determined. Then $$\begin{align*}y&=\frac{1-3(aq+b)}{3q+1}=\frac{-3aq+1-3b}{3q+1}\\&=\frac{-a(3q+1)+(a+1-3b)}{3q+1}\;,\end{align*}$$ and at that point it’s clear that $y$ will be an integer if $a+1-3b=0$, something that can easily be done by inspection: $a=2$ and $b=1$ does the job (and is in fact the solution that you found).

In case you’re curious, this is a special case of Bézout’s theorem.