Question Number 226513 by aba_math last updated on 01/Dec/25
$${Find}\:{gcd}\left({a}^{\mathrm{2}} +{ab}+{b}^{\mathrm{2}} ,{ab}\right)\:{if}\:{gcd}\left({a},{b}\right)=\mathrm{1} \\ $$
Answered by peace2 last updated on 02/Dec/25
$${a}={dx};{b}={dy};{gcd}\left({x},{y}\right)=\mathrm{1} \\ $$$${gcd}\left({a}^{\mathrm{2}} +{b}^{\mathrm{2}} ;{ab}\right)={d}^{\mathrm{2}} {gcd}\left({x}^{\mathrm{2}} +{y}^{\mathrm{2}} ;{xy}\right) \\ $$$${let}\:{p}\:{prim}\:{factor}\:{of}\:{gcd}\left({x}^{\mathrm{2}} +{y}^{\mathrm{2}} ;{xy}\right) \\ $$$$\Rightarrow\:{p}\mid{xy}\Rightarrow{p}\mid{x}\vee{p}\mid{y};{p}\mid{x}\Rightarrow{p}\mid\left({x}^{\mathrm{2}} +{y}^{\mathrm{2}} \right)\Rightarrow{p}\mid{y} \\ $$$${or}\:{gcd}\left({x},{y}\right)=\mathrm{1}\Rightarrow{p}=\mathrm{1}\:{absurd} \\ $$$$\Rightarrow{gcd}\left({x}^{\mathrm{2}} +{y}^{\mathrm{2}} ;{xy}\right)=\mathrm{1} \\ $$$${gcd}\left({a}^{\mathrm{2}} +{b}^{\mathrm{2}} +{ab};{ab}\right)=\mathrm{1}^{\mathrm{2}} =\mathrm{1} \\ $$
Answered by A5T last updated on 03/Dec/25
![Lemma: gcd(a,b)=gcd(a+b,b) Proof: Let d=gcd(a,b) and gcd(a+b,b)=k d∣a ∧ d∣b ⇒ d∣a+b ⇒ d∣ gcd(a+b,b) ⇒ d∣k k∣a+b and k∣b ⇒ k∣(a+b−b)⇒k∣a ⇒k∣(a,b) ⇒k∣d k∣d and d∣k ⇒ d=k ■ ⇒g=gcd(a^2 +ab+b^2 ,ab)=gcd((a+b)^2 ,ab) gcd(a,b)=1⇒gcd(a+b,b)=1 ⇒a+b=1∙x and b=1∙y⇒ gcd(x,y)=gcd(x+y,y)=1 ⇒(a+b)^2 =x^2 and ab=(x−y)y=xy−y^2 ⇒ g =gcd(x^2 ,xy−y^2 ) Then g ∣x^2 y−x(xy−y^2 )=xy^2 ⇒g∣xy^2 −y(xy−y^2 )=y^3 g∣(a+b)^2 ⇒d∣x^2 ⇒d∣x^3 ⇒g∣ gcd(x^3 ,y^3 )=[gcd(x,y)]^3 =1 g∣1 ⇒ g=1](https://www.tinkutara.com/question/Q226540.png)
$$\mathrm{Lemma}:\:\mathrm{gcd}\left(\mathrm{a},\mathrm{b}\right)=\mathrm{gcd}\left(\mathrm{a}+\mathrm{b},\mathrm{b}\right) \\ $$$$\mathrm{Proof}:\: \\ $$$$\mathrm{Let}\:\mathrm{d}=\mathrm{gcd}\left(\mathrm{a},\mathrm{b}\right)\:\mathrm{and}\:\mathrm{gcd}\left(\mathrm{a}+\mathrm{b},\mathrm{b}\right)=\mathrm{k} \\ $$$$\:\mathrm{d}\mid\mathrm{a}\:\wedge\:\mathrm{d}\mid\mathrm{b}\:\Rightarrow\:\mathrm{d}\mid\mathrm{a}+\mathrm{b}\:\Rightarrow\:\mathrm{d}\mid\:\mathrm{gcd}\left(\mathrm{a}+\mathrm{b},\mathrm{b}\right)\:\Rightarrow\:\mathrm{d}\mid\mathrm{k} \\ $$$$\mathrm{k}\mid\mathrm{a}+\mathrm{b}\:\mathrm{and}\:\mathrm{k}\mid\mathrm{b}\:\Rightarrow\:\mathrm{k}\mid\left(\mathrm{a}+\mathrm{b}−\mathrm{b}\right)\Rightarrow\mathrm{k}\mid\mathrm{a}\:\Rightarrow\mathrm{k}\mid\left(\mathrm{a},\mathrm{b}\right) \\ $$$$\Rightarrow\mathrm{k}\mid\mathrm{d}\: \\ $$$$\mathrm{k}\mid\mathrm{d}\:\mathrm{and}\:\mathrm{d}\mid\mathrm{k}\:\Rightarrow\:\mathrm{d}=\mathrm{k}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\blacksquare \\ $$$$ \\ $$$$\Rightarrow\mathrm{g}=\mathrm{gcd}\left(\mathrm{a}^{\mathrm{2}} +\mathrm{ab}+\mathrm{b}^{\mathrm{2}} ,\mathrm{ab}\right)=\mathrm{gcd}\left(\left(\mathrm{a}+\mathrm{b}\right)^{\mathrm{2}} ,\mathrm{ab}\right) \\ $$$$\mathrm{gcd}\left(\mathrm{a},\mathrm{b}\right)=\mathrm{1}\Rightarrow\mathrm{gcd}\left(\mathrm{a}+\mathrm{b},\mathrm{b}\right)=\mathrm{1} \\ $$$$\Rightarrow\mathrm{a}+\mathrm{b}=\mathrm{1}\centerdot\mathrm{x}\:\mathrm{and}\:\mathrm{b}=\mathrm{1}\centerdot\mathrm{y}\Rightarrow\:\mathrm{gcd}\left(\mathrm{x},\mathrm{y}\right)=\mathrm{gcd}\left(\mathrm{x}+\mathrm{y},\mathrm{y}\right)=\mathrm{1} \\ $$$$\Rightarrow\left(\mathrm{a}+\mathrm{b}\right)^{\mathrm{2}} =\mathrm{x}^{\mathrm{2}} \:\mathrm{and}\:\mathrm{ab}=\left(\mathrm{x}−\mathrm{y}\right)\mathrm{y}=\mathrm{xy}−\mathrm{y}^{\mathrm{2}} \\ $$$$\Rightarrow\:\mathrm{g}\:=\mathrm{gcd}\left(\mathrm{x}^{\mathrm{2}} ,\mathrm{xy}−\mathrm{y}^{\mathrm{2}} \right) \\ $$$$\mathrm{Then}\:\mathrm{g}\:\mid\mathrm{x}^{\mathrm{2}} \mathrm{y}−\mathrm{x}\left(\mathrm{xy}−\mathrm{y}^{\mathrm{2}} \right)=\mathrm{xy}^{\mathrm{2}} \\ $$$$\Rightarrow\mathrm{g}\mid\mathrm{xy}^{\mathrm{2}} −\mathrm{y}\left(\mathrm{xy}−\mathrm{y}^{\mathrm{2}} \right)=\mathrm{y}^{\mathrm{3}} \\ $$$$\mathrm{g}\mid\left(\mathrm{a}+\mathrm{b}\right)^{\mathrm{2}} \Rightarrow\mathrm{d}\mid\mathrm{x}^{\mathrm{2}} \Rightarrow\mathrm{d}\mid\mathrm{x}^{\mathrm{3}} \\ $$$$\Rightarrow\mathrm{g}\mid\:\mathrm{gcd}\left(\mathrm{x}^{\mathrm{3}} ,\mathrm{y}^{\mathrm{3}} \right)=\left[\mathrm{gcd}\left(\mathrm{x},\mathrm{y}\right)\right]^{\mathrm{3}} =\mathrm{1} \\ $$$$\mathrm{g}\mid\mathrm{1}\:\Rightarrow\:\mathrm{g}=\mathrm{1} \\ $$