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

  • $\begingroup$ $\gcd(a,4)=2$ tells you more than just $2 \mid a$, it tells you that no higher power of $2$ divides $a$. Therefore the $k,j$ you determined must be odd, then the conclusion follows easily. $\endgroup$ – dxiv Feb 5 '17 at 1:16
  • 1
    $\begingroup$ Okay, so this means: 2|a so a=2k and k must be odd k=2q+1 , 2|b so b=2j and j must be odd so j=2h+1 adding these equations together we get 4p+4h+4 so we can factor 4 and thats the answer? i just want to make sure I get it. $\endgroup$ – Jamie John Feb 5 '17 at 1:23
  • $\begingroup$ Right, that's it. FWIW it's the same as Ethan Bolker's hint. $\endgroup$ – dxiv Feb 5 '17 at 1:24
  • $\begingroup$ Thank you guys so much@Ethan @dxiv. It seems like there is no need for division algorithm after all. $\endgroup$ – Jamie John Feb 5 '17 at 1:33

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

  • $\begingroup$ Thank you so much. I am not sure why my professor suggested i use D.A. I think that if a and b are even then we can factor out a 2 out of them? $\endgroup$ – Jamie John Feb 5 '17 at 1:01
  • $\begingroup$ Yes, but you can't take out two $2$s. $\endgroup$ – Ethan Bolker Feb 5 '17 at 1:08
  • $\begingroup$ is there a way to do it using D.A? $\endgroup$ – Jamie John Feb 5 '17 at 1:09
  • $\begingroup$ @HananIbraheim I don't think so. You would start by writing $a+b = 4q +r$ and figuring out the remainder $r$. To do that you would have to solve the problem first. $\endgroup$ – Ethan Bolker Feb 5 '17 at 1:11
  • $\begingroup$ how did you write a+b=4q+1 like why? $\endgroup$ – Jamie John Feb 5 '17 at 1:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.