2
$\begingroup$

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?

1 Answers 1

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.

  • 0
    OK 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