Question

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

Answer 1

@experimentX

Answer 2

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

Answer 3

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

Answer 4

.... still looking at it :)

Answer 5

wondering if a euclidean algorithm would pan out


a^2+ab+b^2 = (a-b)(q) + r ...

Answer 6

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

Answer 7

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

Answer 8

STOP RIGHT THERE.

http://openstudy.com/study#/updates/512f5747e4b098bb5fbd07fa

Answer 9

@ParthKohli thats it!!!

Answer 10

better if the whole thing is explained....

Answer 11

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

Answer 12

*bookmark*

Answer 13

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

Answer 14

Can anyone explain?

Answer 15

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

Answer 16

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

Answer 17

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

Answer 18

pffft, misread my own thoughts lol

if b=rb then a = rbq+r

a = r(bq+1) for q in Z