2

My attempt: I tried to use the property $\gcd(a,b)=\gcd(a,b-a)$ but ended up with a meaningless expression. I also tried assuming that if $a$ is of the form $2k_1$ then $b$ must be of the form $2k_2+1$ where $k_1$ and $k_2$ are integers, but this approach didn't work. Finally I deduced that $d=\gcd(a+b,a^2+b^2)|2ab.$ I am interested in knowing how this particular line of reasoning can be extended in order to solve this problem.

Note: I have read the answers to this problem here. My question is different in that it asks one to specifically use the fact that $d|2ab$ to prove that $d=1$ or $2$. Although there is an answer with the exact reasoning provided in that link, I am not sure whether the argument is logically sound. In particular I would like to know whether the following claim $d|2ab\Rightarrow d=1,2$ or $d|a$ or $d|b$ is true or false.

Community
  • 1
Student
  • 9,196
  • 8
  • 35
  • 81

4 Answers4

3

Notice how $(a+b)^2=a^2+b^2+2ab$, so we have: $$\gcd(a+b,a^2+b^2)=\gcd(a+b,(a+b)^2-2ab)=\gcd(a+b,-2ab)=\gcd(a+b,2ab)$$ Now for all primes $p$ such that $p\mid ab$, we have: $$(p\mid a\implies p\nmid b\implies p\nmid a+b)\vee(p\mid b\implies p\nmid a\implies p\nmid a+b)$$ Hence $\gcd(a+b,ab)=1$ and therefore $\gcd(a+b,2ab)=\gcd(a+b,2)$, which is obviously equal to $1$ or $2$.

Mastrem
  • 8,331
3

If $d$ divides both $a+b$ and $a^2+b^2$

$d$ must divide $a^2+b^2+(a+b)(a-b)=2a^2$

and $a^2+b^2-(a+b)(a-b)=2b^2$

$d$ must divide $(2a^2,2b^2)=2(a^2,b^2)$

As $(a,b)=1,(a^2,b^2)=1$

Finally, $(a+b,a^2+b^2)=2$ if $a+b$ is even as $a^2+b^2=(a+b)^2-2ab$ will also be even in that condition

Else $(a+b,a^2+b^2)=1$

lab bhattacharjee
  • 274,582
1

Let $p$ be a prime divisor of $d$. If $p \mid a$ then as it divides $a+b$ we have that it divides $a+b-a=b$. But this means that $p=1$, as $gcd(a,b) = 1$

Now similarly we can consider the cases $p \mid b$ or $p \mid 2$

Stefan4024
  • 35,843
  • Then saying that $d|2ab\Rightarrow d=1,2$ or $d|a$ or $d|b$ is incorrect, right? – Student Nov 02 '16 at 09:12
  • @Shrey Aryan Yeah, as for example $12 \mid 2 \cdot 3 \cdot 4$, but divides neither of $2,3$. So therefore we must take a prime divisor of $d$ and by the definition of primes we must have that $p$ must divide at least one of the factors on the RHS. – Stefan4024 Nov 02 '16 at 09:15
  • So, if we know that $d|2ab$, then a prime divisor $p$ must divide either $2$, $a$ or $b$. – Student Nov 02 '16 at 09:59
  • @ShreyAryan Yes, if $p \mid d$ then we know that $d \mid 2ab \implies p \mid 2ab$. But as $p$ is prime we must have that $p$ divides $2,a,b$. – Stefan4024 Nov 02 '16 at 10:01
  • One more thing, Does $(a^n,b^n)={(a,b)}^n$ in general? – Student Nov 02 '16 at 10:18
  • @ShreyAryan What is ${(a,b)}^n$? If you meant that $d^n$, where $d=(a,b)$ then you're right. – Stefan4024 Nov 02 '16 at 10:19
  • Yes, I meant $d^n$. Thank you very much for helping me. – Student Nov 02 '16 at 10:43
0

Using Bézout's lemma: There exists $x$ and $y$ such that $ax+by=1$.

Then $(a^2+b^2)\left((x-y)^2\right)+(a+b)\left(a (x^2+2 x y-y^2)+b (y^2+2 x y-x^2)\right) = 2(ax+by)^2=2$.

Hence $\gcd(a^2+b^2,a+b) \mid 2$

jjagmath
  • 18,214