# 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…

#### Solutions Collecting From Web of "If $\gcd(m,n)=1$, find $\gcd(m+n,m^2-mn+n^2)$?"

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$.

${\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.$

$\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.