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!
Oct 25th 2009, 03:01 PM
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 .
Oct 25th 2009, 03:04 PM
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
Excellent! Your suggestions gave me what I needed to continue. Thank you!