Zaara 2 years ago if a and b are two integers with gcd(a,b)=1, then show that gcd(a-b, a^2+ab+b^2)=1 or 3

• This Question is Open
1. Zaara

@experimentX

2. amistre64

i wonder a-b = c a^2+ab+b^2 = d a-b+ab = c +ab a^2+ab+ab+b^2 = d +ab a-b+ab = c +ab (a+b)^2 = d +ab

3. Zaara

then how to show gcd equals 1 or 3??????

4. amistre64

.... still looking at it :)

5. amistre64

wondering if a euclidean algorithm would pan out a^2+ab+b^2 = (a-b)(q) + r ...

6. satellite73

i am going to make a guess that it has something to do with $a^3-b^2=(a-b)(a^2+ab+b^2)$ just a guess though

7. satellite73

not a solution by any means, i just thought it might be the hook in to the problem i have no idea how to solve it

8. ParthKohli

9. Zaara

@ParthKohli thats it!!!

10. Zaara

better if the whole thing is explained....

11. amistre64

a^2+ab+b^2 = (a-b)(q) + r a^2+ab+b^2 - r= (a-b)(q) (a^2+ab+b^2 - r)(a-b) = q i was wondering if there was a method we could employ there; give that r=1 or 3, and gcd(a,b) = 1

12. Callisto

*bookmark*

13. ParthKohli

:-\ $\dfrac{(a^2 + ab + b^2 - r)}{a - b} = q$

14. ParthKohli

Can anyone explain?

15. amistre64

$c|d~\iff~d=cn~;~n \in Z$ $p = kq+r~\to \frac{p-r}{k}=q~,~q\in Z$

16. amistre64

the euclidean algorithm has alot of recurrsive:$a=bq+r$ if $a=bq+r\\b = r(b)+0$then gcd(a,b)=r

17. amistre64

hmmm, so if we can show that: a = r(b^2+1) or a/(b^2+1) = r it looks good to me :) is there a flaw in my thought perhaps? if not then: $\frac{a^2+ab+b^2}{(a-b)^2+1}=1~or~3$should do it :)

18. amistre64

pffft, misread my own thoughts lol if b=rb then a = rbq+r a = r(bq+1) for q in Z