GCD Proof With Squares

Printable View

October 25th 2009, 02: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!
October 25th 2009, 03: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)$ .
October 25th 2009, 03: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) ...
October 25th 2009, 04:53 PM
Reindeer Floatilla

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