# If $\gcd (x,4) = 2$ and $\gcd(y,4) = 2$ then $\gcd(x+y,4) = 4$

I was working my way through some number theoretic proofs and being a newbie am stuck on this problem :

If $(x, 4) = 2$ and $(y, 4) =2$, then $(x + y, 4) = 4$, where $(a,b)$ denotes the greatest common divisor of $a$ and $b$.

My Solution (Incorrect)

• $x-4 = 2t$
• $y-4 = 2p$
• $x + y - 8 = 2(t+p) \Rightarrow x + y - 4 = 2f + 4 = 2(f+2)\Rightarrow 2$ divides $(x+y , 4)$

My Question:

My solution is definitely inadequate. Can someone help me out?

HINT:

$x$ has to be one of the forms $:4t,4t+1,4t+2,4t+3$ where $t$ is some integer

As $(x,4)=2,x=4t+2$

• Hi , @labbhattacharjee , but is x not only divisible by 2 . That means x mod 2 = 0 or 1 i.e. x is of the form 2t or 2t+1 . Why is x of the form 4t , 4t+1 etc. ? Jan 18, 2015 at 4:45
• @pranav, As we have $(x,4)=2$ Jan 18, 2015 at 4:46
• (x,4) = 2 means that the gcd of x & 4 is 2 . I do not think it implies that x is divisible by 4 . Am I right or wrong ? Jan 18, 2015 at 4:47
• @pranav, Is $x=4t+2$ divisible by $2$ or by $4?$ Jan 18, 2015 at 4:51
• @pranav, $x$ is either $2u,2u+1$ But $(2u+1,4)=1$ So, $x=2u\implies(2u,4)=2\implies2(u,2)=2\iff(u,2)=1\implies u$ must be odd $=2v+1$(say) Jan 18, 2015 at 4:55

You know that $x=2a$ and $y=2b$, with odd $a$ and $b$. Thus $$x+y=2(a+b)$$ and $a+b$ is even. Thus $x+y$ is divisible by $4$.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}