# Number Theory

• Jul 9th 2008, 02:41 PM
JCIR
Number Theory
Let $a,b \in \mathbb{Z} .$ with (a,4)=2 and (b,4)=2. find (a+b, 4) and prove that your answer is correct.
• Jul 9th 2008, 04:20 PM
Reckoner
Quote:

Originally Posted by JCIR
Let $a,b \in \mathbb{Z} .$ with (a,4)=2 and (b,4)=2. find (a+b, 4) and prove that your answer is correct.

$(a + b,\,4) = 4$

$\emph{Proof: }$ First, note that the only possible divisors of 4 are 1, 2, and 4, so we only need show that $4\mid(a + b)$

$(a,\,4) = 2\text{ and }(b,\,4)=2\Rightarrow2\mid a\text{ and }2\mid b\Rightarrow\exists p,\,q\in\mathbb{Z},\;a = 2p,\,b = 2q$

$\Rightarrow a + b = 2(p + q)$

But $2\nmid p$, for if so, $\exists m\in\mathbb{Z},\;a = 2(2m) = 4m\Rightarrow4\mid a$ and so $(a,\,4) = 4$ and not 2 as required. Similarly, $2\nmid q$.

Thus $p$ and $q$ are odd so their sum $p + q$ must be even (i.e., $\exists s,\,t\in\mathbb{Z},\;p = 2s + 1\text{ and }q = 2t + 1$ $\Rightarrow p + q = 2s + 2t + 2 = 2(s + t + 1)$ with $s + t + 1\in\mathbb{Z}$). So $4\mid2(p + q)\Rightarrow4\mid(a + b)$ as required to show that $(a + b,\,4) = 4\quad\square$