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
Hint. I don't think you need the division algorithm, you just need to know something about divisibility.
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$.