Proof that the greatest common divisor of $(a, a+2)$ is $2$ if $a$ is even and $1$ if $a$ is odd

Question

Some help would be great on this, my teacher hasn't explained how to construct proofs to us, he just keeps doing them for us in class.

I have at the beginning: Let a be even. Since the sum of two even numbers is always even, a+2 is even.

Any help would be appreciated!

Answer 1

Let $d=\gcd(a,a+2)$. Then $d$ divides $a$ and $a+2$. Thus $d$ Divides their difference, I.e. $d$ divides $2$. So $d$ can be either $1$ or $2$. If $a$ is even then $a+2$ will also be even, so $d$ must be $2$, otherwise $d$ is $1$.

Answer 2

If $a$ is even then there exists $k$ such that $a=2k$. Then $a+2=2k+2=2k'$ where $k'=k+1$, then $2$ is a common divisor of $a$ and $a+2$. Now let $d$ a common divisor of $a$ and $a+2$, then $d$ is a divisor of $(a+2)-a=2$ and then $d \leq 2$. That means that $2$ is the greatest common divisor of $a$ and $a+2$.

If $a$ is odd then if $d$ a common divisor of $a$ and $a+2$, then $d$ is a divisor of $(a+2)-a=2$ and then $d \leq 2$ and $d=1$ or $d=2$. But $2$ is not a divisor of $a$ since it is odd then $d=1$.

Answer 3

I think the OP's question was about proof writing and not so much this particular question. So, I will try a different approach for an answer.

Many schools provide an introduction to proof writing before one takes more advanced mathematics courses. This is because writing proofs can be a tricky thing. The first thing to understand is the way we talk or write looks nothing like logic. And since logic is how one justifies an argument, then we typically must re-write our statements to fit logical reasoning. Logical statements typically flow from assumptions to conclusions. In fact, in logic we write, $$p\to q$$ to indicate this. To provide an argument that other mathematicians will agree with, one needs to assume $p$, write some convincing statements about $p$, and then conclude $q$. Of course, there are other ways to proof things and after practice proofs turn more into Art than Logic. But lets just stick to the basics.

"The greatest common divisor of $(a,a+2)$ is 2 if $a$ is even and 1 if $a$ is odd."

Step 1. Re-write so that it looks like how a proof should flow (If...then...). When written properly we find that there are actually two statements.

"If $a$ is an even number, then the greatest common divisor of $(a,a+2)$ is 2."

"If $a$ is an odd number, then the greatest common divisor of $(a,a+2)$ is 1."

Step 2. Our job is write a few sentences that justify why our hypotheses imply our conclusions. When first learning to write proofs it is customary to state your hypothesis at the beginning of each proof and also finish your proofs with your conclusion. We point out, that the sentences above could not be proven (or even understood) if the words in the sentences are not defined. Hence, I assume we were told what odd numbers are and what even numbers are and what a greatest common divisor is. Those things would be considered definitions; definitions never need to be proven, they are simply the definitions of the words we use.

Step 3. Let's write a proof. Similar to grammar school, we should have an introduction (what are we assuming), body (convincing arguments), and conclusion.

We want to show "If $a$ is an even number, then the greatest common divisor of $(a,a+2)$ is 2."

Proof. Assume $a$ is an even number. Since $a$ is an even number, then there is a number $n$ such that $a=2\cdot n$. Hence, $(a,a+2)=(2n,2n+2)=2\cdot (n,n+1)$. Since, we know $(n,n+1)=1$ for any number, then $(a,a+2)=2$. We have shown that the greatest common divisor of $a$ and $a+2$ is $2$. QED.

My proof above is reliant upon knowing the definition of even and using previously proven facts or theorems. If I want my proof to be as elligant as possible, I might re-write it to include justifications along the way.

Proof. Assume $a$ is an even number. Since $a$ is an even number, then by definition (page 5) there is a number $n$ such that $a=2\cdot n$. Hence, $(a,a+2)=(2n,2n+2)=2\cdot (n,n+1)$, by Theorem 3 (see page 7). Theorem 5 (page 8) tells us that $(n,n+1)=1$ for any number, $n$, hence we conclude that $$(a,a+2)=(2n,2n+2)=2(n,n+1)=2\cdot 1=2.$$ Thus, we have shown that the greatest common divisor of $a$ and $a+2$ is in fact $2$. QED.

Certainly, I made up the page numbers since I don't know what book you are using. I don't even know if the above proof is a correct proof for your particular class without knowing exactly how your class defined even numbers and defined the GCD or more importantly what theorems have already been established in your class for use in proofs. But I hope this helps illustrate how proof writing should be done.