Let $x$ and $y$ be positive integers and let $\gcd(x,y)=6$. How do we find all the values for $\gcd(x^2,y^3)$? How can we show that these are the only possibilities?
Possible values of $\gcd(x^2, y^3)$ when $\gcd(x,y)=6$
2
$\begingroup$
elementary-number-theory
1 Answers
7
Hint:
If $gcd(x,y)=5$, then one of $x$ or $y$ has a single 5 in its prime factorisation and the other has one or more 5s. They have no other prime factors in common.
So $x^2$ must have at least two 5s and $y^3$ at least three 5s. But either $x^2$ has no more than two 5s or $y^3$ has no more than three 5s. So $gcd(x^2,y^3)$ is either $5^2=25$ or $5^3=125$.
In your problem you have 6 not 5, which makes the problem twice as complicated. See what you can do.
-
0OK now I see that $gcd(60,54)=6$. 60 can be factored into $2^2*3*5$ and 54 can be factored into $2*3^3$. So the GCD equals the multiplication of the smallest powers of each of the factors. So one of $x$ or $y$ must have one power of 2 while the other has more, and one must have one power of 3 while the other has more. So then would we have to apply the above argument to both 2 and 3? – 2011-10-21