If $\gcd(m,n)=1$, find $\gcd(m+n,m^2-mn+n^2)$? If $\gcd(m,n)=1$, find $\gcd(m+n,m^2-mn+n^2)$, I don't know how to find it, I tried with linear combination $-(m+n)*(m+n)+m^2-mn+n^2=-3mn $, but it doesn't help me...
 A: As you have seen, $\gcd(m+n,m^2-mn+n^2)=\gcd(m+n,-3mn)$. If a prime $p\mid\gcd(m+n,-3mn)$, then $p\mid-3mn$, which leads to:  
(i) $p\mid 3$, that is $p=3$. This happens whenever $3\mid m+n$.
(ii) $p\mid m$, then $p\mid n$, which is impossible.
(iii) $p\mid n$, then $p\mid m$, which is again impossible.  
Hence, we conclude that, if $3\mid m+n$, then $\gcd(m+n,m^2-mn+n^2)=3$; otherwise, $\gcd(m+n,m^2-mn+n^2)=1$.
A: $\gcd(m+n, m^2-mn+n^2)=d$.
$d \mid m+n$ and $d \mid m^2-mn+n^2$.
$d \mid m+n \Rightarrow d \mid (m+n)^2=m^2+2mn+n^2$
$d \mid m+n \Rightarrow d \mid (m+n)(m-n)=m^2-n^2$
$\Rightarrow d \mid m^2+2mn+n^2-m^2+n^2=2mn+2n^2=2n(m+n)$
$d \mid m^2+2mn+n^2+m^2-n^2=2mn+2m^2=2m(n+m)$
$d \mid gcd(2n(m+n), 2m(n+m)) \Rightarrow d \mid 2(n+m) gcd(m,n)=2(n+m)$
I hope this helps bozo99.
A: ${\rm mod}\ m\!+\!n\!:\,\ \color{#c00}{m\equiv -n}\,\Rightarrow\,f(\color{#c00}m)= m^2\!-mn+n^2\equiv\, f(\color{#c00}{-n})\,\equiv\, \color{#0a0}{3n^2}$
By Euclid, $\ (m\!+\!n,f(m)) = (m\!+\!n,\, f(m)\ {\rm mod}\ m\!+\!n) = (m\!+\!n, \color{#0a0}{3n^2})$
and $\,(m\!+\!n,n)=(m,n)=1\,\Rightarrow\, (m\!+\!n,n^2)=1\,\Rightarrow\,(m\!+\!n,3n^2) = (m\!+\!n,3)$
Note $\ d = (m\!+\!n,3) = 3\ $ if $\ 3\mid m\!+\!n\ $ else $\ d=1,\ $ by $\,d\mid 3\iff d=3\,$ or $\,d=1.$
