If $(a,4)=2=(b,4)$, prove $(a+b,4)=4$. I'm almost embarrassed to be asking about a problem such as this one (exercise 12 in Niven 1.2), but here goes:

Given $(a,4)=(b,4)=2$, show that $(a+b,4)=4$.

I have plenty of tricks for working with gcds multiplicatively, however I have honestly no idea how to attack this problem. I sort of halfheartedly tried using Bezout's identity, writing $ax_0+4y_0 = 2$ and $bx_1+4y_1 = 2$. Adding the equations gives
$$ax_0+bx_1+4(y_0+y_1) = 4$$
and hence if I were able to use that $x_0=x_1$ I'd only have to show minimality. However, seeing the exercises around this one I am completely sure I am overcomplicating things here. What am I missing?

Nothing to be embarrassed about, professional mathematicians don't always write things in the way that is clearest to the average person. If I were Niven, I would have worded the exercise thus:

Given $\gcd(a, 4) = 2$ and $\gcd(b, 4) = 2$, show that $\gcd(a + b, 4) = 4$.

It would've been more ink, but I think it would have been clearer. Another problem is this idea that every math problem requires some advanced method, formula, theorem or jargon. Sometimes all you need is simple, basic reasoning.
So let's reason this one through: $\gcd(a, 4) = 2$ means that $a$ is even but not a multiple of 4. We can write $a = 4j + 2$ (where $j$ is any positive or negative integer whatsoever, or maybe 0) and we can write $a \equiv 2 \pmod 4$. If we wanted to use jargon, we could say that $a$ is a "singly even number" (see Sloane's A016825).
Next, $\gcd(b, 4) = 2$ means that $b$ is also a singly even number. We can write $b = 4k + 2$ (where $k \in \mathbb{Z}$) and we can write $b \equiv 2 \pmod 4$.
So $a + b = 4j + 4k + 4 = 4(j + k + 1)$ by simple algebraic rewriting. By congruences we have $a + b \equiv 2 + 2 \equiv 0 \pmod 4$, confirming the assertion.
Maybe I would have made this the next exercise:

Express each of the following multiples of 4 as a sum of two singly even numbers: $128, 0, -12$.

