GCD Proof With Squares
If , then .
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 and is the least positive integer that is a linear combination of and .
And the trivial assumption: implies there exists a number that is a common divisor of and .
Then divides , , and .
So , , and for some integers , , and .
Then divides and .
So and for some integers and .
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!
Welcome to the forum!
You are not completely on the wrong track. When you say
it is important to mention that . But if then (Prove this! Hint : write and as products of prime powers. Then what does it mean for them to be relatively prime?)
Setting you have and , so .
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) ...
Excellent! Your suggestions gave me what I needed to continue. Thank you!