# GCD Proof With Squares

• Oct 25th 2009, 02:43 PM
Reindeer Floatilla
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!
• Oct 25th 2009, 03:01 PM
Bruno J.
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)\$.
• Oct 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) ...
• Oct 25th 2009, 04:53 PM
Reindeer Floatilla
Excellent! Your suggestions gave me what I needed to continue. Thank you!