0
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

2
$\begingroup$

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$

$\endgroup$
8
  • $\begingroup$ 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. ? $\endgroup$
    – pranav
    Jan 18, 2015 at 4:45
  • 1
    $\begingroup$ @pranav, As we have $(x,4)=2$ $\endgroup$ Jan 18, 2015 at 4:46
  • $\begingroup$ (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 ? $\endgroup$
    – pranav
    Jan 18, 2015 at 4:47
  • 1
    $\begingroup$ @pranav, Is $x=4t+2$ divisible by $2$ or by $4?$ $\endgroup$ Jan 18, 2015 at 4:51
  • 1
    $\begingroup$ @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) $\endgroup$ Jan 18, 2015 at 4:55
1
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .