Here's the question you clicked on:

## Zaara Group Title 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 one year ago one year ago

• This Question is Open
1. Zaara Group Title

@experimentX

2. amistre64 Group Title

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 Group Title

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

4. amistre64 Group Title

.... still looking at it :)

5. amistre64 Group Title

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

6. satellite73 Group Title

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 Group Title

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 Group Title

STOP RIGHT THERE. http://openstudy.com/study#/updates/512f5747e4b098bb5fbd07fa

9. Zaara Group Title

@ParthKohli thats it!!!

10. Zaara Group Title

better if the whole thing is explained....

11. amistre64 Group Title

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 Group Title

*bookmark*

13. ParthKohli Group Title

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

14. ParthKohli Group Title

Can anyone explain?

15. amistre64 Group Title

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

16. amistre64 Group Title

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 Group Title

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 Group Title

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