Welcome to our community

Be a part of something great, join today!

Number Theory gcd

Alexmahone

Active member
Jan 26, 2012
268
Show that if $(a, b)=1$ then $(a+b,\ a^2-ab+b^2)=1\text{ or }3$.

My attempt:

$(a+b,\ a^2-ab+b^2)=(a+b,\ a^2-ab+b^2-(a+b)(a+b))=(a+b,\ -3ab)=(a+b,\ 3ab)$

$(a,\ a+b)=(b,\ a+b)=1$

$\therefore (a+b,\ ab)=1$

Consider 2 cases:

1) $(a+b,\ 3)=1 \implies(a+b,\ 3ab)=1$

2) $(a+b,\ 3)=3\implies 3|a+b$

$\displaystyle (a+b,\ ab)=1\implies\left(\frac{a+b}{3},\ ab\right)=1$

$\displaystyle (a+b,\ 3ab)=3\left(\frac{a+b}{3},\ ab\right)=3$

Is that ok?
 
Last edited:

caffeinemachine

Well-known member
MHB Math Scholar
Mar 10, 2012
832
Show that if $(a, b)=1$ then $(a+b,\ a^2-ab+b^2)=1\text{ or }3$.

My attempt:

$(a+b,\ a^2-ab+b^2)=(a+b,\ a^2-ab+b^2-(a+b)(a+b))=(a+b,\ -3ab)=(a+b,\ 3ab)$

$(a,\ a+b)=(b,\ a+b)=1$

$\therefore (a+b,\ ab)=1$

Consider 2 cases:

1) $(a+b,\ 3)=1 \implies(a+b,\ 3ab)=1$

2) $(a+b,\ 3)=3\implies 3|a+b$

$\displaystyle (a+b,\ ab)=1\implies\left(\frac{a+b}{3},\ ab\right)=1$

$\displaystyle (a+b,\ 3ab)=3\left(\frac{a+b}{3},\ ab\right)=3$

Is that ok?
Yes. Perfect.
 

PaulRS

Member
Jan 26, 2012
37
You might be interested in the following approach:

Let $d$ be a common divisor of $a+b$ and $a^2-ab+b^2$. Then $ d|(a+b)$ and this can be rewritten as $ a \equiv - b (\bmod. d)$

And so $0\equiv a^2-ab+b^2 \equiv (-b)^2 - (-b) \cdot b + b^2 = 3 b^2 (\bmod. d)$ . But we must have $(d,b) = 1$ since $(a,b)=1$ and $d | (a+b)$ (because any common divisor of $b$ and $d$ will also divide $a$).

Thus $0 \equiv 3 (\bmod. d)$ ...