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

@experimentX

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

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

.... still looking at it :)

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

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

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

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

@ParthKohli thats it!!!

better if the whole thing is explained....

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

*bookmark*

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

Can anyone explain?

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

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

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 :)

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

Join our real-time social learning platform and learn together with your friends!