# Tricky GCD problem

Say we have two integers, $x$ and $y$. If $\gcd(x,y)=5$, how can we find every value for $\gcd(x^2,y)$? If you can find a list of every value, can you prove that this list is complete?

-

Here is something to consider: Can $\gcd(x^2,y)$ be divisible by any primes other than 5? (Note that if $p$ is any prime number, then $p$ divides $x^2$ if and only if $p$ divides $x$.)

Do you think $5^{100000}$ is a possible value for $\gcd(x^2,y)$? Why or why not? If you try to make your intuition precise about this, that should take you the rest of the way.

-
I think I see what your'e saying. So if $y$ is prime and $y|x$, then necessarily $gcd(x^2,y)=5$. Otherwise, if $y$ is prime and $y$ does not divide $x$, $gcd(x^2,y)=1$. – johnnymath Oct 14 '11 at 2:41
I'm not saying anything about $y$ being prime. In fact, if $y$ is prime, then necessarily $y=5$. I'm talking about what primes go into both $x^2$ and $y$, i.e., which primes go into $\gcd(x^2,y)$. – Zev Chonoles Oct 14 '11 at 2:42
Ok, then I need to think more about this. Going back to your original question, I would say that $5^{100000}$ could not be a possible value for $gcd(x^2,y)$ because if that were true, then $gcd(x,y)$ would certainly have to be larger than 5. I think this because when we change our equation, $x$ gets squared but $y$ remains the same. Thinking this way, I still think the only answer could be 5 – johnnymath Oct 14 '11 at 2:52
How about if $x=5$ and $y=25$? – Zev Chonoles Oct 14 '11 at 2:55

HINT $\rm\quad (x,\:y)\ |\ (x^2,\:y)\ |\ (x,\:y)^2\! = (x^2,\:x\:y,\:y^2)$

-

If $(x,y)=5$, then $5$ is the only common prime in the factorizations of $x$ and $y$. So $5$ has order $1$, (that means it's power in the factorization is $1$) in at least one of the factorizations. If the order were greater in both, then $(x,y)$ would be greater than $5$. If $5$ has order $1$ in $y$, then squaring $x$ is not going to introduce any new factors of $5$ in $y$, so $(x^2,y)=5$ again. If $5$ has order $1$ in $x$, then it has order $2$ in $x^2$. So depending on the order of $5$ in $y$, $(x^2,y)$ could be $5$ or $25$.

-