# Thread: GCD Proof With Squares

1. ## GCD Proof With Squares

Prove:
If $\displaystyle gcd(a,b)=gcd(a,c)$
, then $\displaystyle gcd(a^2,b^2)=gcd(a^2,c^2)$.

My knowledge of the greatest common factor (GCD) is rather limited, but I'm thinking this will involve representing GCD expressions with linear combinations. Here is what I know:

The greatest common divisor of the nonzero integers $\displaystyle a$
and $\displaystyle b$ is the least positive integer that is a linear combination of $\displaystyle a$ and $\displaystyle b$.

And the trivial assumption:
$\displaystyle gcd(a,b)$ implies there exists a number that is a common divisor of $\displaystyle a$ and $\displaystyle b$.

Assume
$\displaystyle gcd(a,b)=gcd(a,c)$.
Let
$\displaystyle d=gcd(a,b)=gcd(a,c)$.
Then
$\displaystyle d$ divides $\displaystyle a$, $\displaystyle b$, and $\displaystyle c$.
So
$\displaystyle a=dk$, $\displaystyle b=dl$, and $\displaystyle c=dm$ for some integers $\displaystyle k$, $\displaystyle l$, and $\displaystyle m$.
Let
$\displaystyle e=gcd(a^2,b^2)$.
Then
$\displaystyle e$ divides $\displaystyle a^2$ and $\displaystyle b^2$.
So $\displaystyle a^2=ex$ and $\displaystyle b^2=ey$ for some integers $\displaystyle x$ and $\displaystyle y$.

(Now what?)

If this is even the correct start to this proof, I would be amazed. I imagine the next steps would involve substitution, but I'm not sure how to proceed. Any help would be appreciated!

2. Welcome to the forum!

You are not completely on the wrong track. When you say

$\displaystyle a=dk,\ b=dl$

it is important to mention that $\displaystyle (k,l)=1$. But if $\displaystyle (k,l)=1$ then $\displaystyle (k^2,l^2)=1$ (Prove this! Hint : write $\displaystyle k$ and $\displaystyle l$ as products of prime powers. Then what does it mean for them to be relatively prime?)

So $\displaystyle (a^2,b^2)=(d^2k^2,d^2l^2)=d^2(k^2,l^2)=d^2$.

Setting $\displaystyle d=(a,b)=(a,c)$ you have $\displaystyle (a^2,b^2)=d^2$ and $\displaystyle (a^2, c^2)=d^2$, so $\displaystyle (a^2,b^2)=(a^2,c^2)$.

3. a = kd => a^2 =(kd)^2 = ex ... similar for b ... does that help?

Actually ... you can try showing this first (a,b)=d then (a^2,b^2)=d^2 so if (a,b)=(a,c), then (a^2,b^2)=(a^2,c^2) ...

4. Excellent! Your suggestions gave me what I needed to continue. Thank you!