# GCD Proof With Squares

• Oct 25th 2009, 03:43 PM
Reindeer Floatilla
GCD Proof With Squares
Prove:
If $gcd(a,b)=gcd(a,c)$
, then $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 $a$
and $b$ is the least positive integer that is a linear combination of $a$ and $b$.

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

Assume
$gcd(a,b)=gcd(a,c)$.
Let
$d=gcd(a,b)=gcd(a,c)$.
Then
$d$ divides $a$, $b$, and $c$.
So
$a=dk$, $b=dl$, and $c=dm$ for some integers $k$, $l$, and $m$.
Let
$e=gcd(a^2,b^2)$.
Then
$e$ divides $a^2$ and $b^2$.
So $a^2=ex$ and $b^2=ey$ for some integers $x$ and $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!
• Oct 25th 2009, 04:01 PM
Bruno J.
Welcome to the forum!

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

$a=dk,\ b=dl$

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

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

Setting $d=(a,b)=(a,c)$ you have $(a^2,b^2)=d^2$ and $(a^2, c^2)=d^2$, so $(a^2,b^2)=(a^2,c^2)$.
• Oct 25th 2009, 04:04 PM
Bingk
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) ...
• Oct 25th 2009, 05:53 PM
Reindeer Floatilla
Excellent! Your suggestions gave me what I needed to continue. Thank you!