# division algorithm proofs

I have a question regarding a division algorithm proof. I know the question has been posted here but I am confused with a very specific step. Here is the question:

$$\gcd(a,4)=2$$ $$\gcd(b,4)=2$$

so find the $\gcd(a+b,4)$ and prove it. Here is what I have so far:

I know that since $2|a$ then and $2|b$ then $a$ and $b$ must be even. So $a=2k$ and $b=2j$ for $k$, $j$ are integers. Then from here I know I need to use the division algorithm but how what is my divisor? do I need to work backwards? Thanks in advance

• $\gcd(a,4)=2$ tells you more than just $2 \mid a$, it tells you that no higher power of $2$ divides $a$. Therefore the $k,j$ you determined must be odd, then the conclusion follows easily. – dxiv Feb 5 '17 at 1:16
• Okay, so this means: 2|a so a=2k and k must be odd k=2q+1 , 2|b so b=2j and j must be odd so j=2h+1 adding these equations together we get 4p+4h+4 so we can factor 4 and thats the answer? i just want to make sure I get it. – Jamie John Feb 5 '17 at 1:23
• Right, that's it. FWIW it's the same as Ethan Bolker's hint. – dxiv Feb 5 '17 at 1:24
• Thank you guys so much@Ethan @dxiv. It seems like there is no need for division algorithm after all. – Jamie John Feb 5 '17 at 1:33

Your hypotheses tell you that $2$ divides $a$ but $4$ does not, so $a$ is twice an odd number. The same is true for $b$. What can you conclude about $a+b$?
Edit. Your comments show that you know how to solve the problem now, without the division algorithm. When you learn about congruences you'll do it this way: $$a \equiv 2 \pmod{4} \quad\text{and} \quad b \equiv 2 \pmod{4}$$ imply $$a + b \equiv 2 + 2 \equiv 0 \pmod{4}$$ so $\gcd(a+b,4) = 4$.
• Yes, but you can't take out two $2$s. – Ethan Bolker Feb 5 '17 at 1:08
• @HananIbraheim I don't think so. You would start by writing $a+b = 4q +r$ and figuring out the remainder $r$. To do that you would have to solve the problem first. – Ethan Bolker Feb 5 '17 at 1:11